c++ - C++ 中的 set 和 unordered_set 有什么区别？

Question

我遇到了一个很好的问题，它很相似，但完全不一样，因为它谈到了 Java，它具有不同的哈希表实现，凭借同步的访问器/mutators: What are the differences between a HashMap and a Hashtable in Java?

那么set和unordered_set的C++实现有什么区别呢？这个问题当然可以扩展到 map vs unordered_map 等等其他 C++ 容器。

这是我的初步评估:

set:虽然标准没有明确要求将其实现为树，但时间复杂性约束要求其查找/插入操作，这意味着它将始终以树的形式实现.通常作为 RB 树(如 GCC 4.8 中所见)，它是高度平衡的。由于它们是高度平衡的，因此它们对于 find()

具有可预测的时间复杂度

优点:紧凑(与其他 DS 相比)

Con:访问时间复杂度为 O(lg n)

unordered_set:虽然标准没有明确要求将其实现为树，但时间复杂性约束要求其查找/插入操作，这意味着它将始终作为哈希实现-表。

优点:

1. 更快( promise 为搜索摊销 O(1))
2. 与 tree-DS 相比，易于将基本原语转换为线程安全的

缺点:

1. 查找不保证是 O(1)。理论上最坏的情况是 O(n)。
2. 不像树那么紧凑(实际上，负载因子永远不会是 1)。

注意:哈希表的 O(1) 来自没有冲突的假设。即使负载因子为 0.5，每第二个变量插入都会导致碰撞。可以观察到，哈希表的负载因子与访问其中元素所需的操作数成反比。我们减少了更多#operations，更稀疏的哈希表。当存储的元素的大小与指针相当时，开销是相当大的。

我是否错过了应该知道的用于性能分析的 map /集之间的任何区别？

Answer 1

我想你通常已经回答了你自己的问题，但是，这个:

Not as compact as tree. (for practical purposes load factors is never 1)

不一定是真的。类型为 T 的树的每个节点(我们假设它是红黑树)使用的空间至少等于 2 * pointer_size + sizeof(T) + sizeof(bool) .这可能是 3 * pointer size取决于树是否包含 parent每个树节点的指针。

将此与 HashMap 进行比较:每个 HashMap 都会浪费数组空间，因为 load factor < 1正如你所说。然而，假设 HashMap 使用单链表进行链接(实际上，没有真正的理由不这样做)，插入的每个元素只需要 sizeof(T) + pointer size .

请注意，此分析忽略了可能来自对齐使用的额外空间的任何开销。

对于任何元素 T它具有小尺寸(因此，任何基本类型)，指针的大小和其他开销占主导地位。负载系数为 > 0.5 (例如)std::unordered_set确实可能比等效的 std::set 消耗更少的内存.

另一个重要的缺失点是迭代 std::set保证根据给定的比较函数生成从最小到最大的排序，同时遍历 std::unordered_set将以“随机”顺序返回值。