在 std::map 和 std::unordered_map 之间进行选择
现在 std 在 unordered_map 中有一个真正的哈希映射，为什么（或何时）我仍然想使用旧的 map 而不是 >unordered_map 在它实际存在的系统上？是否有任何我无法立即看到的明显情况？
Now that std has a real hash map in unordered_map, why (or when) would I still want to use the good old map over unordered_map on systems where it actually exists? Are there any obvious situations that I cannot immediately see?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
正如已经提到的，
map允许以排序的方式迭代元素，但unordered_map不允许。这在许多情况下非常重要，例如显示集合（例如地址簿）。这也体现在其他间接方式中，例如：(1) 从find()返回的迭代器开始迭代，或 (2) 存在诸如lower_bound()之类的成员函数。另外，我认为最坏情况搜索复杂性存在一些差异。
对于
map来说，时间复杂度为 O( lg N )对于
unordered_map< /code>，它是 O( N ) [当哈希函数不好导致太多哈希冲突时可能会发生这种情况。]这同样适用于最坏情况 删除 复杂性。
As already mentioned,
mapallows to iterate over the elements in a sorted way, butunordered_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 byfind(), or (2) existence of member functions likelower_bound().Also, I think there is some difference in the worst case search complexity.
For
map, it is O( lg N )For
unordered_map, it is O( N ) [This may happen when the hash function is not good leading to too many hash collisions.]The same is applicable for worst case deletion complexity.
除了上面的答案之外，您还应该注意，仅仅因为
unordered_map是恒定速度 (O(1)) 并不意味着它比map< /code> （顺序log(N)）。该常量可能大于log(N)，特别是因为N受 232（或 264）限制）。因此，除了其他答案（
map维护顺序和哈希函数可能很困难）之外，map的性能可能更高。例如，在我为博客文章运行的程序中 我发现对于 VS10，
std::unordered_map比std::map慢（尽管boost::unordered_map比两者都快）。注意第 3 至第 5 个栏。
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 thanmap(of orderlog(N)). The constant may be bigger thanlog(N)especially sinceNis limited by 232 (or 264).So in addition to the other answers (
mapmaintains order and hash functions may be difficult) it may be thatmapis more performant.For example in a program I ran for a blog post I saw that for VS10
std::unordered_mapwas slower thanstd::map(althoughboost::unordered_mapwas faster than both).Note 3rd through 5th bars.
部分基于 Chandler Carruth 的 CppCon 2014 演讲。
std::map（许多人认为）对于面向性能的工作没有用处：另外，
std::map是一棵平衡树；你必须非常频繁地穿越它，或者重新平衡它。这些分别是缓存杀手和缓存启示录操作...所以只需对std::map说“不”。您可能对关于高效哈希映射实现的这个SO问题感兴趣。
（PS -
std::unordered_map对缓存不友好，因为它使用链表作为存储桶。）Partly based on Chandler Carruth's CppCon 2014 talk.
std::mapis (considered by many to be) not useful for performance-oriented work:std::unorderded_maprather thanstd::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 tostd::map.You might be interested in this SO question on efficient hash map implementations.
(PS -
std::unordered_mapis cache-unfriendly because it uses linked lists as buckets.)我认为很明显，您需要使用
std::map来按排序顺序迭代映射中的项目。当您更愿意编写比较运算符（很直观）而不是哈希函数（通常非常不直观）时，也可以使用它。
I think it's obvious that you'd use the
std::mapyou need to iterate across items in the map in sorted order.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).
假设你有很大的钥匙，也许是很大的字符串。要为大字符串创建哈希值，您需要从头到尾遍历整个字符串。至少需要与密钥长度呈线性关系的时间。但是，当您仅使用键的
>运算符搜索二叉树时，每个字符串比较都会在发现第一个不匹配时返回。对于大字符串来说，这通常是非常早的。这个推理可以应用于
std::unordered_map和std::map的find函数。如果键的性质导致生成哈希所需的时间（在std::unordered_map的情况下）比使用二分搜索查找元素的位置所需的时间（在情况下std::map），在std::map中查找键应该更快。很容易想到这种情况的场景，但我相信在实践中这种情况很少见。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 ofstd::unordered_mapandstd::map. If the nature of the key is such that it takes longer to produce a hash (in the case ofstd::unordered_map) than it takes to find the location of an element using binary search (in the case ofstd::map), it should be faster to lookup a key in thestd::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.