内容相同的两个unordered_set的迭代顺序是否保证一致?
问题描述
如果存在两个unordered_set变量,二者排序后的内容完全一致,但创建流程不同:第一个变量仅执行过元素插入操作,第二个变量则按不同顺序执行过插入、删除等操作,最终二者存储的所有元素完全相同。请问遍历这两个变量时,输出的元素顺序是否一致?
注:本问题与同类问题的区别在于,后者讨论的是对同一个unordered_set执行两次遍历的顺序一致性问题。
结论
遍历顺序不一定一致,C++标准没有给出任何一致性保证
原因说明
- C++标准对
unordered_set的顺序约束仅包含一点:同一个未被修改的unordered_set实例,多次遍历的顺序是固定的。从来没有要求过两个元素完全相同的unordered_set实例遍历顺序一致。 unordered_set底层采用哈希表实现,遍历逻辑是按桶的存储顺序逐个取出桶内元素,最终的遍历顺序会受多重因素影响:- 两个实例的创建流程不同,运行过程中触发动态扩容的时机可能不同,最终哈希表的总桶数可能存在差异,同一个元素的哈希值对总桶数取模的结果就会不一样,对应的存储桶位置不同,遍历顺序自然不同。
- 执行过删除操作的
unordered_set,哈希表中会残留用于处理线性探测等哈希冲突逻辑的墓碑节点,后续插入新元素时会优先占用墓碑节点的位置,而不是按普通哈希计算的位置存储,这也会导致相同元素的存储位置和仅做过插入操作的实例存在差异。
- 极端情况下,哪怕两个
unordered_set完全按相同顺序插入相同的元素,没有任何删除操作,不同编译器、不同标准库的实现逻辑差异,也可能导致二者的遍历顺序不同。
内容的提问来源于stack exchange,提问作者user2052436
相关产品推荐
相关产品推荐

