What is KeyEqual in std::unordered_set for?

Question

What is the purpose of 3rd parameter KeyEqual in std::unordered_set? Isn't hash uniqueness enough?

template<
    class Key,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator<Key>
> class unordered_set;

Sorry if this question sounds naive. Moving to C++ from Python/PHP :)

For now my implementations of KeyEqual always duplicates Hash impl. So I was wonder if I do it correctly.

Answer 1

Let's take for example, a set of ints with a hash function that just does a simple mod % operation

struct IntMod {
    constexpr std::size_t operator()(int i) const { return i % 10; }
};

std::unordered_set<int, IntMod> s;

This can easily result in a hash collision, and when that happens you need to be able to compare the keys to know if a key is already present.

s.insert(25);  // hash == 5
s.insert(35);  // hash == 5
assert(*s.find(25) == 25);  // both 25 and 35 are present despite the same hash
assert(*s.find(35) == 35);

If we add a KeyEqual that just uses the hash function as well (like you suggest it do by default), it breaks on the second insertion.

struct IntEq {
  constexpr bool operator()(int a, int b) const {
    return IntMod{}(a) == IntMod{}(b);
  }
};

std::unordered_set<int, IntMod, IntEq> s;
s.insert(25);  // hash == 5
s.insert(35);  // hash == 5
assert(*s.find(25) == 25);
assert(*s.find(35) == 35);  // now this fails. s.find(35) returns iterator to 25