在 std: : map 和 std: : unorder_map 之间进行选择

我认为很明显，您需要使用 std::map来按照排序顺序对映射中的项目进行迭代。

当您希望编写比较运算符(这是直观的)而不是散列函数(这通常是非常不直观的)时，也可以使用它。

作为 已经说过了，map允许以排序的方式迭代元素，但是 unordered_map不允许。这在许多情况下非常重要，例如显示一个集合(例如地址簿)。这也表现在其他间接的方式，如: (1)从 find()返回的迭代器开始迭代，或者(2)存在像 lower_bound()这样的成员函数。

另外，我认为 最坏的情况 搜索的复杂性也有一些不同。

• 对于 map，是 O (lgN)

• 对于 unordered_map，它是 O (N)[这个 梅发生在哈希函数不好导致太多哈希冲突的时候。]

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

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

因此，除了其他答案(map维护顺序和散列函数可能是困难的) ，可能是因为 map的性能更好。

例如，在我运行的一个 博客文章程序中，我看到 VS10的 std::unordered_map比 std::map慢(尽管 boost::unordered_map比两者都快)。

注意第三到第五小节。

_{这是由于谷歌的钱德勒卡鲁斯在他的 全国政协2014年讲座}

许多人认为 std::map对于面向性能的工作没有用处: 如果你想要 O (1)-摊销访问，使用适当的关联数组(或者如果没有，使用 std::unorderded_map) ; 如果你想要排序的循序存取，使用基于向量的东西。

而且，std::map是一个平衡树，你必须遍历它，或者重新平衡它，这种情况经常发生。这些分别是缓存杀手和缓存启示操作... 所以只要对 std::map说不。

您可能对有关高效哈希映射实现的 这个所以问题感兴趣。

(PS-std::unordered_map对缓存不友好，因为它使用链表作为存储桶。)

假设你有一把很大的钥匙，也许是一根很大的弦。要为大字符串创建哈希值，您需要从头到尾遍历整个字符串。它至少需要线性时间的长度的关键。但是，当您只使用键的 >运算符搜索二叉树时，每个字符串比较可以在发现第一个不匹配时返回。对于大字符串来说，这通常是非常早的。

该推理可以应用于 std::unordered_map和 std::map的 find函数。如果键的性质使得生成散列(在 std::unordered_map中)比使用二进制搜索(在 std::map中)查找元素的位置所需的时间更长，那么在 std::map中查找键应该会更快。很容易想到这种情况的场景，但我相信在实践中这种情况很少见。