为什么std::unordered_map的KeyEqual没有被它的operator==使用？

Question

在下面的代码中，我定义了模板参数

Hash

和

KeyEqual

为

unordered_map

。我期望输出是

1 1 1 1

，但实际上是

1 1 0 1

。为什么会出现这种情况？是因为与

std::equal_to<Base*>

比较地图时没有使用

==

吗？

#include <iostream>
#include <unordered_map>

using std::cout;
using std::endl;

class Base {
public:
    int x;
    Base(int _x) : x(_x) {}

    bool operator==(const Base& another) const {
        return x == another.x;
    }
    size_t hash() const {return x;}
};

template <>
struct std::hash<Base> {
    size_t operator()(const Base& r) const {
        return r.hash();
    }
};

template <>
struct std::hash<Base*> {
    size_t operator()(const Base *r) const {
        return r->hash();
    }
};

template <>
struct std::equal_to<Base*> {
    bool operator()(const Base *r1, const Base *r2) const {
        return (*r1) == (*r2);
    }
};

int main(int, char**){
    Base b1(1);
    Base b2(2);
    Base bb1(1);
    Base bb2(2);
    cout << (b1 == bb1) << endl;

    std::unordered_map<Base, int> map1;
    map1.emplace(b1, 1);
    map1.emplace(b2, 2);
    std::unordered_map<Base, int> map2;
    map2.emplace(bb1, 1);
    map2.emplace(bb2, 2);
    cout << (map1 == map2) << endl;

    std::unordered_map<Base*, int, std::hash<Base*>, std::equal_to<Base*>> map11;
    map11.emplace(&b1, 1);
    map11.emplace(&b2, 2);
    std::unordered_map<Base*, int, std::hash<Base*>, std::equal_to<Base*>> map22;
    map22.emplace(&bb1, 1);
    map22.emplace(&bb2, 2);
    cout << (map11 == map22) << endl;

    std::unordered_map<Base*, int, std::hash<Base*>, std::equal_to<Base*>> map33;
    map33.emplace(&b1, 1);
    map33.emplace(&b2, 2);
    cout << (map11 == map33) << endl;
}

Answer 1

operator==

绕过它们 KeyEqual 为

std::unordered_map

与直觉相反，

==

的

std::unordered_map

运算符并不关心

std::hash

或

std::key_equal

；它依赖于您类型的内置

==

运算符。

两个无序容器 a 和 b 比较相等，如果

a.size() == b.size()

并且，对于从

[Ea1, Ea2)

获得的每个等效键组

a.equal_range(Ea1)

，存在从

[Eb1, Eb2)

获得的等效键组

b.equal_range(Ea1)

，使得

is_permutation(Ea1, Ea2, Eb1, Eb2) 

返回

true

。

- [unord.req.general] p242

请注意，测试相等性的范围（在您的情况下，它们仅包含一个指针）如何不使用提供给容器的 KeyEqual。它是根据

is_permutation

定义的，没有 KeyEqual，仅使用内置

==

运算符。

你的代码也是直接的未定义行为：

在无序容器上使用

operator==

或

operator!=

的程序的行为是未定义的，除非 [KeyEqual] 函数对象对于两个容器具有相同的行为，并且 Key 的相等比较函数是将分区细化为由 [KeyEqual] 生成的等效密钥组。

这样做的理由是什么？！

此设计的动机似乎是通过有效比较具有不同等式的多个

std::unordered_map

（请注意，

operator==

允许这样做）。

一般来说，计算排列是二次运算。然而，给定两个无序 使用相同的哈希和键等价函数的容器，元素将被划分为 关键等价组使比较更加有效。

- N2986：无序容器的相等比较

假设两个容器具有相同的 KeyEqual ，可能存在一种特殊情况，但是 KeyEqual 只会在某些时候使用，这更加违反直觉。

---

另请参阅无法将 std::unorded_set 与自定义 KeyEqual 进行比较