SCIP in C++11 ― 3.3.2節その1

共有

Listの内部実装がSchemeのリストの図とはだいぶ違うので、、

set-to-wow!の振る舞いはz1とz2で同じになる(z2の方と同じ)。

これをSICPと同じにしようと頑張ってみたがどうもうまくいかない。

そもそもこれが問題になるのかどうかよくわからないので、

先にキューや表を作ってみてから考えてみよう。

というわけで問題3.15～3.20はパス。

キューと問題3.21

STLのqueueを使いたくなるが、まあ我慢しておこう。

キューの末尾に要素を追加する処理をΘ(1)にするために、

SICPのキューではrear-ptrを用意しているわけだが、

こっちのC++実装ではListは内部的にstd::listで、

Listの末尾に要素を代入的に加えるappend!（コードではappendf）では、

内部的にはend()イテレータのところからstd::spliceしている。

end()イテレータで末尾位置を知る動作はΘ(1)だと思うので、

rear-ptrはそもそも不要で、単に要素をappend!すればいいだけだ。

さらにSICPのキューではrear-ptrとキューのリストの末尾は共有されているから、

insert-queue!で空でないキューに要素を追加するときに、最初に

(set-cdr! (rear-ptr queue) new-pair)

するのだが、こっちのListの実装ではその共有ができてないので、

rear-ptrとキューのリストの末尾は全然違うオブジェクトになる。

要するにこっちの実装ではrear-ptrの存在意義は皆無で、

処理に関係しないオブジェクトがただメモリ食ってるだけ。

だから、reat-ptrは廃して、キューの表現は単にListでいい。

あとsetfが、コピー先がリストの時は実装していなかったので実装しなおし。

----

template<typename InType>

void setf(const InType& input, const List& destination)

{

    const List inList(makeLeaf(input));

    if(!inList->isList()){

        if(!inList->isFunction()){

            setItem(inList,const_cast<List&>(destination));

        }else{

            const_cast<List&>(destination)=List(inList);

        }

    }

    const_cast<List&>(destination)->removeAllElement();

    destination->append(inList);

}

//---------abstraction barrier---------

void setfFrontPointer(const List& queue,const List& item)

{return(setfCar(queue,item));}

const bool isEmptyQueue(const List& queue)

{return(isNull(queue));}

const List makeQueue(void)

{return(makeList());}

const List frontQueue(const List& queue)

{

    if(isEmptyQueue(queue)){

        cerr<<"FRONT called with an empty queue "<<listString(queue)<<endl;

        exit(1);

        return(makeList());

    }

    return(car(queue));

}

const List insertfQueue(const List& queue, const List& item)

{

    if(isEmptyQueue(queue)){

        setfFrontPointer(queue,item);

    }else{

        appendf(queue,makeList(item));

    }

    return(queue);

}

   

const List deletefQueue(const List& queue)

{

    if(isEmptyQueue(queue)){

        cerr<<"DELETE! called with an empty queue "<<listString(queue)<<endl;

        exit(1);

        return(makeList());

    }

    setf(cdr(queue),queue);

    return(queue);

}

void printQueue(const List& queue)

{cout<<listString(queue);}

//---------abstraction barrier---------

int main(int argc, char** argv)

{

    cout<<"Excersize 3.21:"<<endl;

    auto q1(makeQueue());

    printQueue(q1);cout<<endl;

    printQueue(insertfQueue(q1,makeLeaf("a")));cout<<endl;

    printQueue(insertfQueue(q1,makeLeaf("b")));cout<<endl;

    printQueue(insertfQueue(q1,makeLeaf("c")));cout<<endl;

    printQueue(deletefQueue(q1));cout<<endl;

    printQueue(deletefQueue(q1));cout<<endl;

    printQueue(insertfQueue(q1,makeLeaf("d")));cout<<endl;

    printQueue(deletefQueue(q1));cout<<endl;

    printQueue(deletefQueue(q1));cout<<endl;

    return(0);

}

----

出力

----

Excersize 3.21:

()

('a)

('a 'b)

('a 'b 'c)

('b 'c)

('c)

('c 'd)

('d)

()