96

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

unordered_map通常应该给出 O(1) 的平均复杂度，最坏的情况是 O(n)。在什么情况下会达到 O(n)？amap什么时候比 得到更多的时间效率unordered_map？当 n 很小时会发生这种情况吗？

假设我会将 STLunordered_map与默认的 haser Vs 一起使用。地图。字符串是关键。

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

4

5 回答 5

228 
                       | 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|
于 2012-12-10T11:16:33.087 回答
72

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

最坏的情况是理论上的，并且绑定到一个包含所有元素的哈希值。这没有实际意义。unordered_map只要您至少有 log N 个属于同一哈希的元素，速度就会变慢。这也没有实际意义。在某些特殊情况下，您可以使用特定的哈希算法来确保更均匀的分布。对于不共享特定模式的普通字符串，随附的通用哈希函数unordered_map同样出色。

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

于 2012-12-10T11:07:14.263 回答
8

我应该选择什么容器，map 还是 unordered_map？unordered_map 占用更多内存，所以让我们假设内存不是问题，关注的是速度。

配置文件然后决定。unordered_map通常更快，但因情况而异。

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

当散列不好并且一堆元素被分配到相同的垃圾箱时。

什么时候地图比 unordered_map 更省时？当 n 很小时会发生这种情况吗？

可能不是，但如果你真的在乎的话，可以分析一下。让一个小尺寸的容器成为你程序的瓶颈似乎是极不可能的。无论如何，对于这种情况，简单vector的线性搜索可能会更快。

决定时最重要的是排序要求和迭代器失效的缺乏。如果你需要任何一个，你几乎必须使用map. 否则，unordered_map。

于 2012-12-10T11:09:10.937 回答
7

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

如果你有一个如此糟糕的哈希函数，它为所有输入搅拌产生相同的哈希值（即产生冲突）......

我应该选择什么容器，map 还是 unordered_map？

始终是您拥有的要求和数据种类/数量的问题。

什么时候地图比 unordered_map 更省时？

只是结构不同而已。您最好根据您的典型用例选择使用其中一个（考虑到您拥有什么样的数据及其数量）

当 n 小时它会发生吗？

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

于 2012-12-10T11:07:04.730 回答
0

std::map 在内部将元素存储在平衡的 BST 中。因此，元素将按键的排序顺序存储。

std::unordered_map 使用哈希表存储元素。因此，元素不会以任何排序顺序存储。它们将以任意顺序存储。

内存使用情况 ：

与 map 相比，unordered_map 的内存使用量更多，因为 unordered_map 也需要空间来存储哈希表。

搜索元素的时间复杂度：

在 std::map 中搜索元素的时间复杂度为 O(log n)。即使在最坏的情况下，它也会是 O(log n)，因为元素在内部存储为平衡二叉搜索树 (BST)。

而在 std::unordered_map 中，搜索的最佳情况时间复杂度是 O(1)。其中，如果哈希码函数不好，那么最坏情况的复杂度可能是 O(n)

于 2020-12-21T13:15:54.163 回答