c++hashequalityunordered-set

How std::unordered_set correctly detects equal elements if Hash and KeyEqual are based on different subobjects?


Consider this snippet:

struct Foo
{
    int a, b;
};

template<>
struct std::hash<Foo>
{
    constexpr std::size_t operator()(const Foo& obj) const noexcept
    {
        return std::hash<int>{}(obj.a);
    }
};

template<>
struct std::equal_to<Foo>
{
    constexpr bool operator()(const Foo& lhs, const Foo& rhs) const noexpect
    {
        return std::equal_to<int>{}(lhs.b, rhs.b);
    }
}

Here I'm using different subobjects for Hash and KeyEqual. If std::unordered_set is checking for uniqueness only in the current bucket, then how can it correctly ensure uniqueness in this case?


Solution

  • It cannot ensure uniqueness, at all. This is completely undefined behavior.

    It is a requirement that if two objects are compared to be equal, the hash function must produce an equal hash value as well. Any other result is undefined behavior. Quoting the C++ standard:

    [unord.req]

    Two values k1 and k2 are considered equivalent if the container’s key equality predicate pred(k1, k2) is valid and returns true when passed those values. If k1 and k2 are equivalent, the container’s hash function shall return the same value for both.