如何在map和unordered_map之间选择？ [英] How to choose between map and unordered_map?

问题描述

假设我想使用字符串作为键来映射数据。
我应该选择什么容器， map 或 unordered_map ？ unordered_map 占用更多的内存，所以让我们假设内存不是一个问题，关注的是速度。

code> unordered_map 通常应给出O（1）的平均复杂度与O（n）的最差情况。
在什么情况下它会得到O（n）？
映射何时比 unordered_map 获得更多的时间效率？

假设我将使用默认的haser vs使用STL unordered_map 。地图。

如果我要遍历元素而不是每次访问一个元素，我应该更喜欢 map ？

解决方案在实践中，如果内存没有问题， unordered_map 总是更快，如果你想要单元素访问。

最坏的情况是理论和绑定到一个哈希会计所有的元素。这不是实际的相关性。一旦你至少有log N个元素属于同一个哈希， unordered_map 会变慢。这也没有实际意义。在某些特殊情况下，您可以使用特定的散列算法，以确保更均匀的分布。对于不共享特定模式的普通字符串，带有 unordered_map 的通用哈希函数同样好。

如果要以排序方式遍历地图（使用迭代器），则不能使用 unordered_map 。相反， map 不仅允许，还可以基于键的近似值为您提供地图中的下一个元素（参见 lower_bound 和 upper_bound 方法）。

Suppose I wanted to map data with a string as the key. 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.

unordered_map should 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 map get more time efficient than unordered_map? Does it happen when n is small?

Assuming I would use STL unordered_map with the default haser Vs. map. string is the key.

If I'm going to iterate over the elements rather than access an individual element each time, should I prefer map?

解决方案

In practice, if memory is no issue, unordered_map is always faster if you want single element access.

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_map gets 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_map are just as good.

If you want to traverse the map (using iterators) in a sorted fashion, you cannot use unordered_map. On the contrary, map not only allows that, but also can provide you with the next element in a map based on an approximation of the key (see lower_bound and upper_bound methods).

这篇关于如何在map和unordered_map之间选择？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！