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

Question

我遇到了这个好问题，它很相似但完全不同，因为它讨论的是 Java，它具有不同的哈希表实现，凭借同步访问器/突变器: 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相比)

缺点:访问时间复杂度为 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/set 之间的任何差异？

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每个树节点的指针。

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

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

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

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