C++ unordered_multimap元素输出顺序异常原因咨询

首先明确核心规则：unordered系列容器的「无序」，指的是不按照key的比较规则做排序存储，完全不代表会保留元素的插入顺序。C++标准从未对unordered_multimap的遍历顺序做任何保证，你观察到的固定输出顺序只是当前使用的STL版本的内部实现副作用，不属于可依赖的稳定行为。

你看到E D C A B这个输出，是哈希表底层实现逻辑叠加的巧合，和容器的设计规则无关：

• unordered_multimap底层采用开链法实现哈希表：初始化时会预先分配固定数量的桶（bucket），每个桶本质是一个单链表，所有哈希值计算后落在该桶的元素都会存在这个链表里。
• 多数STL实现的桶内单链表采用头插法添加新元素：新元素直接挂在链表头部，时间复杂度为O(1)，不需要额外维护尾指针。同一桶内先插入的元素会被后续新元素挤到链表尾部，遍历从链表头部开始时，就会出现后插入的元素先被访问的倒序效果。
• 插入过程中会触发rehash（扩容）逻辑：当元素总数超过「桶数量 * 最大负载因子」（默认最大负载因子为1.0）时，哈希表会申请原大小2倍的新桶数组，把所有已有元素重新计算哈希位置后迁移到新桶。迁移过程中遍历旧桶的顺序、插入新桶的方式会翻转部分元素的相对顺序，剩余落在不同桶、或者未被迁移逻辑影响顺序的元素，就会保持插入时的正序，二者叠加刚好出现你测试时看到的前三个倒序、后两个正序的结果。
• 多次测试输出顺序完全一致，只是因为你的测试输入固定、当前STL的哈希规则、扩容阈值、插入逻辑都是固定的，只要换个STL版本、调整编译选项、甚至增减一两个元素触发不同的扩容时机，遍历顺序就会发生不可预测的变化。

你测试用的代码如下：

int main()
{
    unordered_multimap<char, int> window;
    window.insert(make_pair('A',1));
    window.insert(make_pair('B',1));
    window.insert(make_pair('C',1));
    window.insert(make_pair('D',1));
    window.insert(make_pair('E',1));
    for (unordered_multimap<char, int>::iterator it = window.begin(); it != window.end(); it++)
        cout<<it->first<<endl;
    return 0;
}

如果业务逻辑需要严格按照插入顺序遍历元素，不要依赖unordered系列容器的遍历顺序，这类容器的设计目标是提供平均O(1)时间复杂度的查找、插入性能，从未将遍历顺序的稳定性作为设计目标。

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