C++ 在 std::map 和 std::unordered_map 之间进行选择

Choosing between std::map and std::unordered_map

提问by Johann Gerell

Now that stdhas a real hash map in unordered_map, why (or when) would I still want to use the good old mapover unordered_mapon systems where it actually exists? Are there any obvious situations that I cannot immediately see?

现在，std有一个真正的哈希表unordered_map，为什么（或者）我还是想用好老map了unordered_map就在那里确实存在系统？是否有任何我无法立即看到的明显情况？

采纳答案by Arun

As already mentioned, mapallows to iterate over the elements in a sorted way, but unordered_mapdoes not. This is very important in many situations, for example displaying a collection (e.g. address book). This also manifests in other indirect ways like: (1) Start iterating from the iterator returned by find(), or (2) existence of member functions like lower_bound().

正如已经提到的，map可以遍历以排序方式的元素，但unordered_map没有。这在许多情况下非常重要，例如显示集合（例如地址簿）。这也以其他间接方式表现出来，例如：（1）从 返回的迭代器开始迭代find()，或（2）存在像lower_bound().

Also, I think there is some difference in the worst casesearchcomplexity.

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

• For map, it is O( lg N )

• For unordered_map, it is O( N ) [This mayhappen when the hash function is not good leading to too many hash collisions.]

• 对于map，它是 O(lg N )

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

The same is applicable for worst casedeletioncomplexity.

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

回答by Motti

In addition to the answers above you should also note that just because unordered_mapis constant speed (O(1)) doesn't mean that it's faster than map(of order log(N)). The constant may be bigger than log(N)especially since Nis limited by 2³²(or 2⁶⁴).

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

So in addition to the other answers (mapmaintains order and hash functions may be difficult) it may be that mapis more performant.

因此，除了其他答案（map维护顺序和哈希函数可能很困难）之外，它的map性能可能更高。

For example in a program I ran for a blog postI saw that for VS10 std::unordered_mapwas slower than std::map(although boost::unordered_mapwas faster than both).

例如，在我为博客文章运行的程序中，我看到 VS10std::unordered_map比std::map（尽管boost::unordered_map比两者都快）慢。

Note 3rd through 5th bars.

注意第 3 到第 5 小节。

回答by einpoklum

_{This is due to Google's Chandler Carruth in his CppCon 2014 lecture}

_{这要归功于 Google 的 Chandler Carruth 在他的CppCon 2014 演讲中}

std::mapis (considered by many to be) not useful for performance-oriented work: If you want O(1)-amortized access, use a proper associative array (or for lack of one, std::unorderded_map); if you want sorted sequential access, use something based on a vector.

std::map是（被许多人认为是）对面向性能的工作没有用：如果您想要 O(1) 摊销访问，请使用适当的关联数组（或缺少一个，std::unorderded_map）；如果您想要排序的顺序访问，请使用基于向量的内容。

Also, std::mapis a balanced tree; and you have to traverse it, or re-balance it, incredibly often. These are cache-killer and cache-apocalypse operations respectively... so just say NO to std::map.

也是std::map一棵平衡树；你必须经常遍历它，或者重新平衡它。这些分别是 cache-killer 和 cache-apocalypse 操作......所以对std::map.

You might be interested in this SO questionon efficient hash map implementations.

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

(PS - std::unordered_mapis cache-unfriendly because it uses linked lists as buckets.)

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

回答by Ken Bloom

I think it's obvious that you'd use the std::mapyou need to iterate across items in the map in sorted order.

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

You might also use it when you'd prefer to write a comparison operator (which is intuitive) instead of a hash function (which is generally very unintuitive).

当您更喜欢编写比较运算符（直观）而不是散列函数（通常非常不直观）时，您也可以使用它。

回答by Martin G

Say you have very large keys, perhaps large strings. To create a hash value for a large string you need to go through the whole string from beginning to end. It will take at least linear time to the length of the key. However, when you only search a binary tree using the >operator of the key each string comparison can return when the first mismatch is found. This is typically very early for large strings.

假设您有非常大的键，可能是大字符串。要为大字符串创建哈希值，您需要从头到尾遍历整个字符串。密钥长度至少需要线性时间。但是，当您只使用>键的运算符搜索二叉树时，每个字符串比较都可以在找到第一个不匹配时返回。对于大字符串，这通常是非常早的。

This reasoning can be applied to the findfunction of std::unordered_mapand std::map. If the nature of the key is such that it takes longer to produce a hash (in the case of std::unordered_map) than it takes to find the location of an element using binary search (in the case of std::map), it should be faster to lookup a key in the std::map. It's quite easy to think of scenarios where this would be the case, but they would be quite rare in practice i believe.

这种推理可以应用到find的功能std::unordered_map和std::map。如果键的性质使得生成散列（在 的情况下std::unordered_map）比使用二分搜索（在 的情况下std::map）查找元素的位置所需的时间更长，则查找键应该更快在std::map. 很容易想到会出现这种情况的场景，但我相信它们在实践中很少见。