SCIP in C++11 ― 2.3.3節その4

集合の探索と問題2.66

element-of-set?の実装と同じ。

順序付けられていない集合版

----

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

typedef List Record;

const List key(const Record& record)

{return(car(record));}

const Record lookup(const List& keyGiven,

                    const List& setOfRecords)

{

    if(isNull(setOfRecords)){return(makeList());}

    if(keyGiven==key(car(setOfRecords))){return(car(setOfRecords));}

    return(lookup(keyGiven,cdr(setOfRecords)));

}

template<typename ElementType>

const Record lookup(const ElementType& keyGiven,

                    const List& setOfRecords)

{return(lookup(makeLeaf(keyGiven),setOfRecords));}

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

int main(int argc, char** argv)

{

    const auto setOfRecords

        (makeList

         (makeList(1,"x"),

          makeList(2,"+"),

          makeList(3,"-")));

    const auto key1(2);

    cout<<"set-of-records = "<<listString(setOfRecords)<<endl;

    cout<<"(lookup "<<key1<<" "<<listString(setOfRecords)<<") = "

        <<listString(lookup(key1,setOfRecords))<<endl;

    return(0);

}

----

出力

----

set-of-records = ((1 'x) (2 '+) (3 '-))

(lookup 2 ((1 'x) (2 '+) (3 '-))) = (2 '+)

(lookup 0 ((1 'x) (2 '+) (3 '-))) = ()

問題2.66：順序づけられた集合版

----

typedef List Record;

const List key(const Record& record)

{return(car(record));}

const Record lookup(const List& keyGiven,

                    const List& setOfRecords)

{

    if(isNull(setOfRecords)){return(makeList());}

    if(keyGiven==key(car(setOfRecords))){return(car(setOfRecords));}

    if(keyGiven<key(car(setOfRecords))){return(makeList());}

    return(lookup(keyGiven,cdr(setOfRecords)));

}

template<typename ElementType>

const Record lookup(const ElementType& keyGiven,

                    const List& setOfRecords)

{return(lookup(makeLeaf(keyGiven),setOfRecords));}

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

int main(int argc, char** argv)

{

    const auto setOfRecords

        (makeList

         (makeList(1,"x"),

          makeList(2,"+"),

          makeList(4,"-")));

    const auto key1(2);

    cout<<"set-of-records = "<<listString(setOfRecords)<<endl;

    cout<<"(lookup "<<key1<<" "<<listString(setOfRecords)<<") = "

        <<listString(lookup(key1,setOfRecords))<<endl;

    const auto key2(3);

    cout<<"(lookup "<<key2<<" "<<listString(setOfRecords)<<") = "

        <<listString(lookup(key2,setOfRecords))<<endl;

    return(0);

}

----

出力

----

set-of-records = ((1 'x) (2 '+) (4 '-))

(lookup 2 ((1 'x) (2 '+) (4 '-))) = (2 '+)

(lookup 3 ((1 'x) (2 '+) (4 '-))) = ()