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

问题描述

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

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 通常应该给出 O(1) 的平均复杂度，最坏的情况是 O(n).在什么情况下它会达到 O(n)?map 什么时候比 unordered_map 获得更多的时间效率?n很小的时候会发生吗?

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?

假设我将使用 STL unordered_map 和默认的 haser Vs.地图.字符串是关键.

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

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

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

推荐答案

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

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

最坏的情况是理论上的，并且绑定到所有元素的单个哈希值.这没有实际意义.unordered_map 只要你有至少 log N 个属于同一个散列的元素，就会变慢.这也没有实际意义.在某些特殊情况下，您可以使用特定的散列算法来确保更均匀的分布.对于不共享特定模式的普通字符串，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_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.

如果您想以排序方式遍历地图(使用迭代器)，则不能使用 unordered_map.相反，map 不仅允许这样做，而且还可以根据键的近似值为您提供地图中的下一个元素(参见 lower_bound 和 upper_bound 方法).

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屋！