如何在map和unordered_map之间进行选择？

Question

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

unordered_map通常应该给出O(1)的平均复杂度与O(n)的最坏情况.在什么情况下它会到达O(n)？什么时候map获得更多的时间效率unordered_map？当n很小时会发生吗？

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

如果我要迭代元素而不是每次访问单个元素,我应该更喜欢map吗？

Answer 1

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

Answer 2

实际上,如果内存没有问题,unordered_map如果您想要单个元素访问,则总是更快.

最坏的情况是理论上的,并且绑定到所有元素的单个哈希算法.这不具有实际意义.unordered_map一旦至少有属于同一个哈希的log N个元素,它就会变慢.这也没有实际意义.在某些特殊情况下,您可以使用特定的散列算法来确保更均匀的分布.对于不共享特定模式的普通字符串,随附的通用散列函数unordered_map也同样好.

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

Answer 3

在什么情况下它会到达O(n)？

如果你有这样一个糟糕的哈希函数,它为所有输入搅拌产生相同的哈希值(即产生碰撞)......

我应该选择哪个容器,map或unordered_map？

它总是存在需求和类型/数量的问题.

地图什么时候比unordered_map更有时间效率？

这只是不同的结构.根据您的典型用例,你最好让chiose使用其中一个(考虑到你有什么样的数据及其数量)

当n很小时它会起作用吗？

在数据量很小的情况下,一切都取决于特定的STL实现......所以有时即使是普通的矢量/数组也可能比关联容器更快......

Answer 4

我应该选择哪个容器,map或unordered_map？unordered_map占用更多内存所以让我们假设内存不是问题,关注的是速度.

简介然后决定.unordered_map通常更快,但每个案例都有所不同.

在什么情况下它会到达O(n)？

当散列不好并且将一堆元素分配给相同的bin时.

地图什么时候比unordered_map更有时间效率？当n很小时,它会幸福吗？

可能不是,但如果你真的在乎,可以描述一下.拥有一个小尺寸的容器是你的程序的瓶颈似乎是不太可能的.无论如何,vector对于这种情况,简单的线性搜索可能更快.

决定时最重要的是排序和缺少迭代器失效的要求.如果你需要,你几乎必须使用map.否则,unordered_map.