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？

回答

相关问题