使用std::equal比较两个std::unordered_map相等失败是什么原因？

问题原因 #

• std::equal的工作逻辑是按迭代器的遍历顺序逐位比对两个序列的对应位置元素，只要有一个位置的元素不匹配就返回false，它本身不处理无序序列的匹配逻辑。
• std::unordered_map是无序关联容器，内部元素的遍历顺序由哈希值、哈希冲突处理规则、元素插入顺序共同决定，和键的大小、插入顺序没有强制对应关系。示例代码中两个unordered_map插入元素的顺序不同，最终内部遍历顺序大概率不一致：遍历um1时第一个元素是{'f',1}，而遍历um2时第一个元素是{'o',1}，逐位比对直接失败，所以返回unequal。

正确实现方案 #

方案1：直接使用unordered_map内置的相等比较运算符（推荐） #

std::unordered_map已经重载了operator==，它的内部逻辑刚好符合需求：先判断两个容器大小相等，再判断每个在第一个容器中存在的键，在第二个容器中也存在且对应值完全相等，不用关心内部存储顺序。
修改后的代码如下：

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<char, int> um1, um2;
    um1['f'] = 1;
    um1['o'] = 1;
    um1['r'] = 1;

    um2['o'] = 1;
    um2['r'] = 1;
    um2['f'] = 1;

    if (um1 == um2) // 直接用内置比较逻辑
        std::cout << "equal" << std::endl;
    else
        std::cout << "unequal" << std::endl;
}

运行后会正常输出equal。

方案2：如果必须使用std::equal实现（不推荐，仅做原理演示） #

因为std::equal要求序列顺序一致，你可以先把unordered_map的元素转存到有序的std::map或者排序后的vector里，再用std::equal比对：

#include <iostream>
#include <unordered_map>
#include <map>
#include <algorithm>

int main() {
    std::unordered_map<char, int> um1, um2;
    um1['f'] = 1;
    um1['o'] = 1;
    um1['r'] = 1;

    um2['o'] = 1;
    um2['r'] = 1;
    um2['f'] = 1;

    // 转成有序map后遍历顺序固定，再用std::equal比较
    std::map<char, int> m1(um1.begin(), um1.end()), m2(um2.begin(), um2.end());
    if (um1.size() == um2.size() && std::equal(m1.begin(), m1.end(), m2.begin()))
        std::cout << "equal" << std::endl;
    else
        std::cout << "unequal" << std::endl;
}

这个方案会额外产生排序开销，性能远低于直接用unordered_map的内置operator==，仅做原理演示使用。

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