0

順序付けられていないセットがどのように機能するかを誰か説明できますか? セットの仕組みもよくわかりません。私の主な質問は、検索機能の効率です。

たとえば、これのビッグ O 実行時間の合計は?

    vector<int> theFirst;
    vector<int> theSecond;
    vector<int> theMatch;

    theFirst.push_back( -2147483648 );
    theFirst.push_back(2);
    theFirst.push_back(44);


    theSecond.push_back(2);
    theSecond.push_back( -2147483648 );
    theSecond.push_back( 33 );


    //1) Place the contents into a unordered set that is O(m). 
    //2) O(n) look up so thats O(m + n). 
    //3) Add them to third structure so that's O(t)
    //4) All together it becomes O(m + n + t)
    unordered_set<int> theUnorderedSet(theFirst.begin(), theFirst.end());

    for(int i = 0; i < theSecond.size(); i++) 
    {
        if(theUnorderedSet.find(theSecond[i]) != theUnorderedSet.end()) 
        {
        theMatch.push_back( theSecond[i] );
        cout << theSecond[i];
        }
   }
4

2 に答える 2

2

すべての std::unordered_*() データ型は、ハッシュを使用してルックアップを実行します。この件に関する Boost のドキュメントを参照すると、すぐに理解できると思います。

http://www.boost.org/doc/libs/1_46_1/doc/html/unordered.html

于 2011-06-01T17:08:59.703 に答える