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

小编典典

algorithm

遇到了一个好问题，这个问题是相似的，但根本不同，因为它谈论的是Java，因为它具有同步的访问器/
mutators，因此具有不同的哈希表实现方式。

那么C 实现set和unordered_set有什么区别？当然，这个问题可以扩展到map与unordered_map等等，对于其他C 容器也是如此。

这是我的初步评估

set
：虽然standard并未明确要求将其实现为树，但是时间复杂性约束要求对其进行查找/插入操作，这意味着它将始终以树的形式实现。通常是高度平衡的RB树（如GCC4.8中所示）。由于它们是高度平衡的，因此它们对于find（）具有可预测的时间复杂性

优点：紧凑（与其他DS相比）

缺点：访问时间复杂度为O（lg n）

unordered_set
：尽管standard并没有明确要求将其实现为树，但是时间复杂性约束要求对其进行查找/插入操作，这意味着它将始终作为哈希表实现。

优点：

缺点：

注意：哈希表的O（1）来自没有冲突的假设。即使负载因子为.5，每隔两个变量插入也会导致碰撞。可以看出，哈希表的负载因子与访问其中的元素所需的操作数量成反比。更重要的是，我们减少了#operations，稀疏哈希表。当存储的元素的大小可与指针相比时，那么开销将非常可观。

编辑：由于大多数人都说问题包含足够的答案，所以我将问题更改为“我是否错过了性能分析的映射/集之间的任何区别？

阅读 1025

2020-07-28

共1个答案

小编典典

我认为您通常已经回答了自己的问题，但是，这是：

不像树那么紧凑。（出于实际目的，负载系数永远不会为1）

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

将此与哈希图进行比较：由于load factor < 1您所说的事实，每个哈希图都会浪费数组空间。但是，假设哈希图使用单链表进行链接（实际上，没有理由不这样做），则插入的每个元素仅取sizeof(T) + pointer size。

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

对于任何T具有较小大小的元素（因此，任何基本类型），指针的大小和其他开销都是主要的。在的负载因子> 0.5（例如）的std::unordered_set可能确实占用更少的内存比等效std::set。

另一个重大遗漏的事实std::set是，根据给定的比较函数，通过a进行迭代保证可以产生从最小到最大的顺序，而通过a进行迭代std::unordered_set将以“随机”顺序返回值。

2020-07-28