C++ 如何在 map 和 unordered_map 之间进行选择？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/13799593/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to choose between map and unordered_map?
提问by StackHeapCollision
Suppose I wanted to map data with a string as the key.
What container should I have chosen, mapor unordered_map? unordered_maptakes up more memory so let's suppose memory isn't an issue, and the concern is speed.
假设我想用一个字符串作为键来映射数据。我应该选择什么容器，map或者unordered_map？unordered_map占用更多内存，所以让我们假设内存不是问题，关注的是速度。
unordered_mapshould generally give average complexity of O(1) with the worst case of O(n).
In what cases would it get to O(n)?
When does a mapget more time efficient than unordered_map? Does it happen when n is small?
unordered_map通常应该给出 O(1) 的平均复杂度，最坏的情况是 O(n)。在什么情况下它会达到 O(n)？什么时候 a mapget 比unordered_map? 当n很小时会发生吗？
Assuming I would use STL unordered_mapwith the default haser Vs. map. string is the key.
假设我将 STLunordered_map与默认的 haser Vs 一起使用。地图。字符串是关键。
If I'm going to iterate over the elements rather than access an individual element each time, should I prefer map?
如果我要迭代元素而不是每次访问单个元素，我应该更喜欢map吗？
采纳答案by ypnos
In practice, if memory is no issue, unordered_mapis always faster if you want single element access.
在实践中，如果内存没有问题，unordered_map如果你想要单元素访问总是更快。
The worst case is theoretical and bound to a single hash accounting for all of the elements. This is not of practical relevance. The unordered_mapgets slower as soon as you have at least log N elements belonging to the same hash. This is also not of practical relevance. In some special scenarios you could use a specific hashing algorithm that ensures a more uniform distribution. For ordinary strings that don't share a specific pattern, the generic hash functions coming with unordered_mapare just as good.
最坏的情况是理论上的，并且绑定到所有元素的单个哈希值。这没有实际意义。将unordered_map尽快慢，你必须在属于相同的散列至少数N个元素得到。这也没有实际意义。在某些特殊情况下，您可以使用特定的散列算法来确保更均匀的分布。对于不共享特定模式的普通字符串，附带的通用哈希函数unordered_map也一样好。
If you want to traverse the map (using iterators) in a sorted fashion, you cannot use unordered_map. On the contrary, mapnot only allows that, but also can provide you with the next element in a map based on an approximation of the key (see lower_boundand upper_boundmethods).
如果要以排序方式遍历地图（使用迭代器），则不能使用unordered_map. 相反，map不仅允许这样做，而且还可以根据键的近似值（请参阅lower_bound和upper_bound方法）为您提供映射中的下一个元素。
回答by
| map | unordered_map
---------------------------------------------------------
element ordering | strict weak | n/a
| |
common implementation | balanced tree | hash table
| or red-black tree|
| |
search time | log(n) | O(1) if there are no hash collisions
| | Up to O(n) if there are hash collisions
| | O(n) when hash is the same for any key
| |
Insertion time | log(n)+rebalance | Same as search
| |
Deletion time | log(n)+rebalance | Same as search
| |
needs comparators | only operator < | only operator ==
| |
needs hash function | no | yes
| |
common use case | when good hash is| In most other cases.
| not possible or |
| too slow. Or when|
| order is required|
回答by Pubby
What container should I have chosen, map or unordered_map? unordered_map takes up more memory so let's suppose memory isn't an issue, and the concern is speed.
我应该选择哪个容器，map 还是 unordered_map？unordered_map 占用更多内存，所以让我们假设内存不是问题，关注的是速度。
Profile and then decide. unordered_mapis generally faster, but it varies per case.
配置文件，然后决定。unordered_map通常更快，但因情况而异。
In what cases would it get to O(n)?
在什么情况下它会达到 O(n)？
When the hashing isn't good and a bunch of elements are being assigned to the same bins.
当散列不好并且一堆元素被分配到相同的 bin 时。
When does a map get more time efficient than unordered_map? Does it happaen when n is small?
什么时候地图比 unordered_map 更有时间效率？当 n 小时它会发生吗？
Probably not, but profile it if you really care. Having a container with a small size be the bottleneck of your program seems extremely unlikely. Anyway, a simple vectorwith linear search may be faster for such cases.
可能不是，但如果您真的关心，请对其进行分析。让一个小尺寸的容器成为你程序的瓶颈似乎是极不可能的。无论如何，vector对于这种情况，简单的线性搜索可能会更快。
The most important thing when deciding is the requirements of ordering and lack of iterator invalidation. If you need either, you pretty much have to use map. Otherwise, unordered_map.
决定时最重要的是排序要求和缺少迭代器失效。如果你需要，你几乎必须使用map. 否则，unordered_map。
回答by zaufi
In what cases would it get to O(n)?
在什么情况下它会达到 O(n)？
if you have such a badhash function which produces the same hash value for all input stirngs (i.e. produce collisions)...
如果你有这样一个糟糕的散列函数，它为所有输入搅拌产生相同的散列值（即产生冲突）......
What container should I have chosen, map or unordered_map?
我应该选择哪个容器，map 还是 unordered_map？
It is always the questions of requirements and kind/amount of data do you have.
始终是要求和您拥有的数据种类/数量的问题。
When does a map get more time efficient than unordered_map?
什么时候地图比 unordered_map 更有时间效率？
It is just different structures. You'd better to make a chiose to use one of them depending on your typical use cases (takeing in account what kind of data do you have and its amount)
它只是不同的结构。您最好根据您的典型用例选择使用其中一个（考虑到您拥有什么样的数据及其数量）
Does it hppaen when n is small?
当 n 小时它是 hppaen 吗？
In case of small data amount everything depends on particular STL implementation... So sometimes even a plain vector/array could be faster than associative containers...
在小数据量的情况下，一切都取决于特定的 STL 实现......所以有时即使是普通的向量/数组也可能比关联容器更快......
