Unordered_set questions

Question

任何人都可以解釋無序集合是如何工作的嗎？我也不確定一個集合是如何工作的。我的主要問題是它的查找功能的效率是多少。

例如，這個總的大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]; 
     } 
    } 

Answer 1

所有的std :: unordered _ *（）數據類型都使用散列來執行查找。看看Boost關於這個主題的文檔，我想你會很快得到一個理解。

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

Answer 2

unordered_set和所有其他​​數據結構使用散列，如通過@Sean提及。散列涉及到插入的分期恆定時間，並且接近恆定的查找時間。散列函數本質上需要一些信息並從中產生一個數字。從某種意義上講，相同的輸入必須產生相同的輸出。但是，不同的輸入會導致相同的輸出，導致所謂的碰撞。查找將被確保爲「完美散列函數」的恆定時間，也就是說，沒有碰撞。在實踐中，輸入數字來自您在結構中存儲的元素（比如它是一個原始類型的值），並將其映射到數據結構中的一個位置。因此，對於一個給定的鍵，該函數將把你帶到存儲元素的地方，而不需要進行任何遍歷或搜索（爲簡單起見，忽略碰撞），因此時間不變。這些結構有不同的實現（開放尋址，鏈接等）。請參見hash table,hash function。我也推薦Skiena的The Algorithm Design Manual的第3.7節。現在，關於大O的複雜性，你是對的，你有O（n）+ O（n）+ O（重疊的大小）。由於重疊不能大於m和n中的較小者，因此總體複雜度可以表示爲O（kN），其中N是m和n之間的最大值。所以，O（N）。再次，這是「最好的情況」，沒有碰撞，並與完美的哈希。

set和multi_set另一方面使用二叉樹，所以插入和查找通常是O（logN）。哈希結構與二叉樹的實際性能取決於N，所以最好嘗試兩種方法並在真實的運行場景中對它們進行分析。