何时应使用 std::map/std::set 而不是 std::unordered_map/std::unordered_set？

Question

在新标准中引入了 std::unordered_map/std::unordered_set ，它使用哈希函数，并且插入/删除/获取元素的平均复杂度恒定，以防我们不需要特别迭代集合顺序，似乎没有理由使用“旧”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^2)，特别是在调整表格大小。

• 与哈希表相比，BST 的内存效率更高。

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

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

• BST 在元素数量较少的小型数据集上表现良好，而哈希表不太适合元素数量较少的小型数据集。