Aje*_*nga 55 c++ algorithm data-structures c++11
遇到了这个很好的问题,这个问题类似但完全不同,因为它讨论了Java,它具有不同的哈希表实现,因为它具有同步访问器/ mutators HashMap和Hashtable之间的差异？
那么set和unordered_set的C++实现有什么不同呢？对于其他C++容器,这个问题可以扩展到map vs unordered_map等等.
这是我的初步评估
set:虽然标准并没有明确要求它实现为树,但时间复杂性约束要求查找/插入操作,这意味着它将始终实现为树.通常作为RB树(如GCC 4.8中所见),它是高度平衡的.由于它们是高度平衡的,因此它们具有可预测的find()时间复杂度
优点:紧凑(与其他DS相比)
Con:访问时间复杂度为O(lg n)
unordered_set:虽然标准并没有明确要求它实现为树,但时间复杂度约束要求查找/插入操作,这意味着它将始终实现为哈希表.
优点:
缺点:
注意:哈希表的O(1)来自假设没有冲突.即使负载系数为.5,每隔一次变量插入也会导致碰撞.可以观察到,散列表的负载因子与访问其中的元素所需的操作数成反比.我们减少了#operations,sparser hash-table.当存储的元素大小与指针相当时,开销非常重要.
编辑:由于大多数人都说问题中包含足够的答案,我正在将问题改为"我是否会错过地图/集合之间的任何区别,以便进行性能分析？"
Yuu*_*shi 27
我想你一般都回答了你自己的问题,但是,这个:
不像树一样紧凑.(出于实际目的,载荷因子永远不会是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将以"随机"顺序返回值.
dha*_*fey 11
另一个区别(虽然与性能无关)是set插入不会使迭代器无效,而unordered_set插入则可以触发重新哈希.在实践中,这是一个非常小的问题,因为对实际元素的引用仍然有效.