4

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;
}

1 Answer 1

3

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

Sign up to request clarification or add additional context in comments.

3 Comments

I customized the comparison by comparing the sizes of the maps and comparing the key-value pairs, and this works fine.
It seems like in this example, the equality comparison function IS a refinement of the partition generated by KeyEqual. That is a == b implies KeyEqual(a, b) for all possible keys.
@ChrisDodd you're right, so it's well-defined. It's just well-defined to have a surprising result.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.