为何unordered_set在此场景下维持插入逆序？是否可依赖该特性？

1. 为什么会出现插入逆序的遍历结果？ #

这是特定测试场景下的实现细节巧合：

• unordered_set底层基于哈希表实现，默认用链地址法处理冲突。对于int类型，多数编译器的默认哈希函数会直接返回数值本身（或与数值严格对应的映射值）。
• 假设你使用的编译器中，unordered_set初始桶数量为11，那么每个插入的整数i会被分配到i % 11对应的桶中：10→桶10，9→桶9，…，1→桶1。
• unordered_set的遍历逻辑是按桶的索引从小到大依次遍历，无冲突时每个桶仅存一个元素，所以遍历顺序就是桶1的1、桶2的2…桶10的10，刚好和倒序插入的顺序相反。
• 这个场景下没有哈希冲突，哈希函数稳定，所以多次运行结果一致。

2. 该行为是否可靠？能否依赖它提升效率？ #

绝对不能依赖这个特性，理由如下：

• C++标准明确规定，unordered_set不保证任何遍历顺序，当前的顺序只是特定编译器、版本、初始条件下的实现细节。
• 不同编译器（GCC/Clang/MSVC）的哈希函数、初始桶大小、扩容策略可能完全不同。比如若初始桶数为8，10会被分配到桶2，9到桶1，8到桶0，遍历顺序就会变成8、9、10、1、2…，和当前结果完全不符。
• 当插入元素数量触发哈希表扩容时，桶的数量变化，所有元素的哈希桶位置会重新计算，遍历顺序必然改变。
• 编译器版本更新也可能修改哈希表的实现逻辑，导致顺序变化。

依赖这种未被标准保证的行为，会让代码在不同环境下出现不可预期的错误，完全得不偿失。如果需要稳定的顺序，应该使用set（有序）或vector+手动去重等结构。

测试代码 #

unordered_set<int> nums;
for (int i=10; i>0; --i) {
    nums.insert(i);
}
nums.erase(4);
for (auto i : nums) {
    cout<< i<< endl;
}

输出结果 #

1
2
3
5
6
7
8
9
10

内容的提问来源于stack exchange，提问作者Priyanshu Sahani