set和unordered_set在C ++中有什么区别？
遇到这个很好的问题，这是相似的，但由于它具有不同的哈希表的实现，因为它具有同步的访问器/ mutators HashMap和Hashtable之间的差异，因为它谈论Java是相似的但是完全不一样？
那么set和unordered_set的C ++实现有什么区别呢？ 这个问题可以扩展到map vs unordered_map等其他C ++容器。
这是我的初步评估
set ：虽然标准并没有明确地要求它被实现为树，但是时间复杂性约束被要求为find / insert操作，意味着它总是被实现为树。 通常作为高度平衡的RB树（如在GCC 4.8中所见）。 由于它们是高度平衡的，它们对于find（）具有可预测的时间复杂度，
优点：紧凑（与其他DS相比）
Con：访问时间复杂度是O（lg n）
unordered_set ：虽然标准没有明确地要求它被实现为树，但是时间复杂性约束要求它的查找/插入操作，意味着它总是被实现为散列表。
优点：
- 更快（承诺O（1）分期付款）
- 与树DS相比，易于将基本原语转换为线程安全的
缺点：
- 查找不保证是O（1）最坏的情况是O（n）
- 不像树那么紧凑。 （为了实际的目的，加载因子从不是1）
注意：散列表的O（1）来自于没有碰撞的假设。 即使使用0.5的载荷系数，每第二次可变插入也会导致碰撞。 可以观察到，哈希表的负载因子与访问其中的元素所需的操作的数量成反比。 更多的我们减less#operations，更稀疏的哈希表。 当存储的元素的大小与指针相当时，开销是非常重要的。
编辑：由于大多数人说的问题包含了足够的答案，所以我将这个问题改为“我错过了地图/设置性能分析之间的任何区别，应该知道的区别？
我想你通常会回答你自己的问题，但是，这是：
不像树那么紧凑。 （为了实际的目的，加载因子从不是1）
不一定是真的。 对于typesT ，树的每个节点（我们假设它是一棵红黑树）利用等于至less2 * pointer_size + sizeof(T) + sizeof(bool) 。 这可能是3 * pointer size取决于树是否包含每个树节点的parent指针。
将它与哈希映射进行比较：由于load factor < 1 ，所以每个哈希映射都会有浪费的数组空间。 但是，假设哈希映射使用单链表进行链接（实际上，没有真正的理由），插入的每个元素只用sizeof(T) + pointer size 。
请注意，此分析忽略可能来自alignment使用的额外空间的任何开销。
对于小尺寸的任何元素T （所以，任何基本types），指针的大小和其他开销占主导地位。 在负载因子> 0.5 （例如） std::unordered_set的确可以占用比等效的std::set更less的内存。
另外一个重要的缺点是，通过std::set迭代可以保证根据给定的比较函数产生一个从最小到最大的sorting，而迭代std::unordered_set会返回一个“random “命令。
另一个区别（尽pipe不是性能相关的）是set插入不会使迭代器失效，而unordered_set插入可以触发rehash。 在实践中，这是一个很小的问题，因为对实际元素的引用仍然有效。
