Why is the KeyEqual of std::unordered_map not used by its operator==?

Question

In the following code, I have defined template arguments Hash and KeyEqual for unordered_map. I expect the output to be 1 1 1 1 but it is actually 1 1 0 1. Why does this happen? Is it because std::equal_to<Base*> is not used in comparing maps with ==?

#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== bypasses they KeyEqual for std::unordered_map

Contrary to intuition, the == operator for std::unordered_map does not care about std::hash or about std::key_equal; it relies on the built-in == operator for your type.

Two unordered containers a and b compare equal if a.size() == b.size() and, for every equivalent-key group [Ea1, Ea2) obtained from a.equal_range(Ea1), there exists an equivalent-key group [Eb1, Eb2) obtained from b.equal_range(Ea1), such that is_permutation(Ea1, Ea2, Eb1, Eb2) returns true.

- [unord.req.general] p242

Notice how the ranges which are tested for equality (in your case, they will simply contain one pointer each) do not use they KeyEqual provided to the container. It is defined in terms of is_permutation with no KeyEqual, which simply uses the built-in == operator.

What is the rationale for this?!

Containers in general don't consider the KeyEqual, Less (in the case of std::set), etc. which you provide to them. All comparison operators are simply forwarded to the contained elements, and this design is consistent, even though it's counter-intuitive.

For two std::unordered_maps with two (stateful) KeyEquals, there is another motivation:

In general, computing permutations is a quadratic operation. However, given two unordered containers that use the same hash and key-equivalence functions, the elements will be partitioned into key-equivalence groups that make comparison much more efficient.

- N2986: Equality Comparison for Unordered Containers

---

See also Can not compare std::unorded_set with custom KeyEqual