selectstd :: map和std :: unordered_map

现在， std在unordered_map有一个真正的哈希映射，为什么（或什么时候）我仍然想要在真正存在的系统map通过unordered_map使用好的旧map ？ 有什么明显的情况我不能马上看到？

Answer 1

如前所述 ， map允许以sorting的方式迭代元素，但unordered_map不会。 这在很多情况下非常重要，例如显示collections（例如地址簿）。 这也体现在其他间接方式上，如：（1）从find()返回的迭代器开始迭代，或者（2）存在像lower_bound()这样的成员函数。

另外，我认为在最坏的情况下 search的复杂性有一些差异。

• 对于map ，它是O（lg N）

• 对于unordered_map ，它是O（N）[当散列函数不好导致太多散列冲突时， 可能会发生这种情况。]

这同样适用于最坏情况的 删除复杂性。

Answer 2

除了上面的答案之外，还应该注意，因为unordered_map是恒定速度（ O(1) ）并不意味着它比map （order log(N) ）更快。 由于N受到2 ³² （或2 ⁶⁴ ）的限制，常数可能大于log(N) ）。

所以除了其他答案（ map维护顺序和散列函数可能很难），可能是map更高性能。

例如，在一个程序中，我跑了一个博客文章，我看到VS10 std::unordered_map比std::map慢（虽然boost::unordered_map比两者都快）。

请注意第3条至第5条。

Answer 3

我认为很明显，您将使用std::map来按照sorting顺序遍历地图中的项目。

你也可以使用它，当你想写一个比较运算符（这是直观的），而不是散列函数（这通常是非常不直观的）。

Answer 4

_{这是由于Google的Chandler Carruth在他2014年的CppCon讲座中}

std::map （被许多人认为是）对于面向性能的工作是无用的：如果你想O（1）-amortized访问，使用适当的关联数组（或缺less一个， std::unorderded_map ）; 如果你想sorting顺序访问，使用基于向量的东西。

而且， std::map是一个平衡树; 而且你必须经常地遍历它，或者重新平衡它。 这些分别是cache-killer和cache-apocalypse操作…所以对std::map说NO。

你可能会对这个有关哈希映射实现的问题感兴趣。

（PS – std::unordered_mapcaching不友好，因为它使用链表作为桶。）

Answer 5

假设你有非常大的键，也许是大的string。 要为大string创build散列值，您需要从头到尾遍历整个string。 密钥长度至less需要一定的时间。 但是，如果仅使用键的运算符search二叉树，则每find一个不匹配，每个string比较都会返回。 对于大型string，这通常很早。

这个推理可以应用于std::unordered_map和std::map的find函数。 如果密钥的性质使得产生散列需要更长的时间（在std::unordered_map的情况下）比使用二进制search（在std::map的情况下）find元素的位置要花费更多的时间，在std::map查找一个键应该会更快一些。 想想这种情况是很容易的，但是在实践中我相信它们是相当罕见的。