Visual C++實現std :: unordered_map只有一個std :: list？

我想實現類似於std的unordered_map。因此，我查看了Visual C++ 2013中的<unordered_map>和<xhash>中的源代碼。我發現實現在unordered_map構造函數中調用_Init函數。我發現，該函數的定義如下：Visual C++實現std :: unordered_map只有一個std :: list？

void _Init(size_type _Buckets = _Min_buckets) 
{ // initialize hash table with _Buckets buckets, leave list alone 
    _Vec.assign(2 * _Buckets, _Unchecked_end()); 
    _Mask = _Buckets - 1; 
    _Maxidx = _Buckets; 
}

功能_Unchecked_end()剛剛返回_List.Unchecked_end()：

_Unchecked_iterator _Unchecked_end() 
{ // return iterator for end of mutable sequence 
    return (_List._Unchecked_end()); 
}

而且std::unordered_map的begin()剛剛返回_List.begin() ...

我認爲僅具有一個列表的find()函數unordered_map在平均情況下不能滿足恆定的複雜度。

那麼...... VC++如何實現std::unordered_map？

對不起，我沒有說清楚。在我看來，執行unordered_map應該是一個帶有許多列表的向量（具有不同迭代器的初始值爲的不同std::list s）。但我只找到單個列表（Init與迭代器的一個std::list）。這纔是重點。

來源

2014-10-11 Cu2S

「只有一個列表」是什麼意思？你抱怨'std :: list'和'std :: unordered_map'具有不同的訪問複雜性;你知道他們是不同的數據結構嗎？ – 2014-10-11 13:50:31

如果你想實現你自己的'unordered_map'，首先閱讀[一個引用]（http：//en.cppreference。com/w/cpp/container/unordered_map），瞭解它的全部內容，理解它背後的概念（散列表和散列表），然後*不要*從高度優化的標準庫中讀取任何實現。這些標準庫不容易被閱讀和理解，但是如果你知道哈希表背後的概念，那麼你可以輕鬆地構建自己的實現。 – 2014-10-11 13:51:43

'_Vec'是描繪每個桶的迭代器（放入'_List'）的向量。所有的桶都鏈接在一起成爲一個鏈表，但每個桶都可以在一段時間內被訪問。 – 2014-10-11 13:57:21

哈希表的希望單獨鏈接的教科書實現是你說的：一個列表數組的排序，每個「桶」一個列表。

但是，如果你考慮一下，就不需要有大量的單獨列表 - 你可以只有一個！這可能會提高順序訪問性能（n.b.它是無序的，但您仍然可以對散列表中的每個元素執行操作）。所以想象一下使用一個鏈表：把所有的值放在那裏，併爲你的數組（矢量），直接使用指針/迭代器到一個鏈表中。如果你想知道一個桶開始的位置，這和教材解決方案是一樣的。要知道桶的結束位置，可以簡單地查看下一個桶的開始（在常量時間內）。

另一種看待這種情況的方法是，它是帶有一個修改的教科書實現：每個桶末尾的「下一個」指針指向下一個非空桶的開始。您將立即明白爲什麼這改善了順序訪問 - 它消除了遍歷空桶的成本（其中可能有負載，因爲實施並不需要縮小哈希表，只是增加它）。

有趣的故事：缺乏這種伎倆的是什麼原因導致GCC和Boost unordered_map有多年線性而不是常數時間erase(iterator)性能部分。對於GCC，請參閱https://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975。對於Boost，請參閱https://svn.boost.org/trac/boost/ticket/3693。

來源

2014-10-11 14:08:36

它也使迭代器實現微不足道。 – 2014-10-11 14:12:27

@ T.C：實際上，請參閱我添加的「趣味故事」，這就是當您的迭代器不是無足輕重地實現時發生的情況。 :) – 2014-10-11 14:15:46

OMG，謝謝!!!! 1 – Cu2S 2014-10-11 14:16:15

Visual C++實現std :: unordered_map只有一個std :: list？

回答

相關問題