什么时候应该使用 std::map / std::set 而不是 std::unordered_map / std::unordered_set？

Question

C++11 标准引入了

std::unordered_map

和

std::unordered_set

，它们使用 hash 函数，并且插入/删除/获取元素的复杂性（平均）恒定。

在我们不需要按特定顺序迭代集合的情况下，似乎没有理由使用“old”

std::map

或

std::set

。

还有其他情况/原因，

std::map

或

std::set

会是更好的选择吗？例如，它们是否会消耗更少的内存，或者排序是它们相对于“无序”版本的唯一优势？

Answer 1

它们是有序的，写

<

比写哈希和相等更容易。

永远不要低估易用性，因为 90% 的代码对代码的性能影响微乎其微。速度提高 10% 可以节省您为另一种类型编写哈希所花费的时间。

OTOH，一个好的哈希组合器只需编写一次，并且 get-state-as-tie 使

<

、

==

和

hash

几乎免费。

具有基于节点的操作的容器之间的拼接保证可能会更好，因为拼接到哈希映射中并不像良好的有序容器拼接那样免费。但我不确定。

最后，迭代器失效保证有所不同。盲目地用无序的喵喵声替换成熟的经过测试的喵喵声可能会产生错误。也许地图的失效功能对您来说是值得的。

Answer 2

std::set/std::map

和

std::unordered_set/std::unordered_map

用于非常不同的问题领域，并且不能互相替代。

1. std::set/std::map

   用于问题围绕元素顺序移动的情况，并且元素访问平均情况下的 O(log n) 时间是可以接受的。通过使用

   std::set/std::map

   还可以检索其他信息，例如查找大于给定元素的元素数量。

2. std::unordered_set/std::unordered_map

   用于平均情况下元素访问时间复杂度必须为 O(1) 且顺序并不重要的情况，例如，如果您想将整数键的元素保留在

   std::vector

   中，则意味着

   vec[10] = 10

   但这不是实用的方法，因为如果键非常大，例如一个键是

   20

   ，另一个键是

   50000

   ，那么只保留两个值，大小为

   std::vector

   的

   50001

   必须分配，如果您使用

   std::set/std::map 

   那么元素访问复杂度是 O(log n) 而不是 O(1)。在这个问题中，使用了

   std::unordered_set/std::unordered_map

   ，并且通过使用

   hashing

   ，在平均情况下提供了 O(1) 恒定时间复杂度，而无需分配较大的空间。

Answer 3

                | map                 | unordered_map
---------------------------------------------------------
Ordering        | increasing order    | no ordering
                | of keys(by default) |

Implementation  | Self balancing BST  | Hash Table
                | like Red-Black Tree | 

search time     | log(n)              | O(1) -> Average 
                |                     | O(n) -> Worst Case

Insertion time  | log(n) + Rebalance  | Same as search
                      
Deletion time   | log(n) + Rebalance  | Same as search

在某些场景下，BST 具有明显的优势：

• BST 本质上提供了通过简单的中序遍历按排序顺序检索所有键的能力，而哈希表需要额外的努力才能实现此功能。

• 使用 BST 可以轻松进行顺序统计、查找最接近的较小和较大元素、进行范围查询。与排序一样，这些操作并不是哈希表的自然操作。

• 可预测的性能：自平衡 BST 确保所有操作的一致 O(log n) 性能，而散列提供平均情况下的 O(1) 时间复杂度，但对于特定操作可能会恶化到 O(n)，特别是在表大小调整期间.

• 使用 BST 可以更有效地进行范围搜索。

• BST 允许多个键共享相同的值，而哈希表依靠唯一键来标识元素，无法容纳具有相同值的多个键。

• BST 在内存和计算复杂度方面的开销较低，而哈希表需要额外的内存来存储哈希值和处理冲突。

--

有关此主题的进一步讨论：此处。