在STD :: MAP和STD :: UNOREREDED_MAP [重复]之间选择

Question

这个问题在这里已经有一个答案：

• 在琐碎的密钥的情况下，使用地图比Unordered_map有任何优势吗？ 12个答案

现在 std 有一个真实的哈希地图 unordered_map, ，为什么（或何时）我仍然想使用好旧 map 超过 unordered_map 在实际存在的系统上？我看不到明显的情况吗？

Answer 1

作为 已经提到了, map 允许以分类的方式迭代元素，但是 unordered_map 才不是。这在许多情况下非常重要，例如显示集合（例如地址簿）。这也以其他间接方式表现出：（1）从返回的迭代器开始迭代 find(), ，或（2）成员函数的存在 lower_bound().

另外，我认为 最差的情况 搜索 复杂。

• 为了 map, ，是o（lg n）

• 为了 unordered_map, ，是o（n）[这个 可能 当哈希功能不好导致太多哈希碰撞时，就会发生。

同样适用于 最差的情况 删除 复杂。

Answer 2

除了上面的答案外，您还应该注意，仅仅是因为 unordered_map 是恒定速度（O(1)）并不意味着它比 map （订单 log(N)）。常数可能大于 log(N) 特别是从 N 受2限制³² （或2⁶⁴).

因此，除了其他答案之外map 保持顺序和哈希功能可能很困难）可能是 map 表现更多。

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

注意第3至第五条。

Answer 3

_{这是由于Google的Chandler Carruth在他的 CPPCON 2014演讲}

std::map （被许多人认为）对于以性能为导向的工作没有用：如果您想要o（1）损坏的访问，请使用适当的关联阵列（或缺少一个阵列， std::unorderded_map）；如果要排序的顺序访问，请使用基于向量的内容。

还， std::map 是一棵平衡的树；而且您必须经常穿越它或重新平衡它。这些分别是缓存杀手和缓存 - 过时的操作...因此 std::map.

您可能对 这个问题 在有效的哈希地图实现上。

（PS- std::unordered_map 由于使用链接列表作为存储桶而感到不友好。）

Answer 4

我认为很明显您会使用 std::map 您需要按排序顺序遍历地图中的项目。

当您希望编写比较操作员（直观）而不是哈希功能（通常非常直觉）时，您也可以使用它。

Answer 5

假设您有很大的钥匙，也许是大琴弦。要为大字符串创建哈希值，您需要从头到尾都通过整个字符串。至少需要线性时间到钥匙的长度。但是，当您仅使用The Binary树搜索时 > 当发现第一个不匹配时，键的操作员可以返回每个字符串比较。对于大琴弦来说，这通常很早。

这种推理可以应用于 find 功能 std::unordered_map 和 std::map. 。如果密钥的性质使得产生哈希需要更长的时间（就 std::unordered_map）比使用二进制搜索找到元素的位置（如果 std::map），在查找钥匙中应该更快 std::map. 。考虑到这种情况的情况很容易，但是我相信它们在实践中很少见。