Can not compare std::unorded_set with custom KeyEqual

Question

The following program does not compile. But If I do not comment out operator==, it compiles. Why operator== is still needed when I already provide FooEqual

#include <cstddef>
#include <unordered_set>

struct Foo {
};

struct FooHasher {
  size_t operator()(const Foo&) const {
    return 1;
  }
};

struct FooEqual {
  bool operator()(const Foo& lhs, const Foo& rhs) const {
    return true;
  }
};

// bool operator==(const Foo& lhs, const Foo& rhs) {
//   return true;
// }

int main() {
  std::unordered_set<Foo, FooHasher, FooEqual> s1;
  std::unordered_set<Foo, FooHasher, FooEqual> s2;
  (void)(s1 == s2);
  return 0;
}

Must be a bug in the implementation ... unless the spec says that `KeqEqual` is only used for insertion/lookup and that `std::unordered_set::operator==` checks whether two sets are equal based on whether the individual elements compare equal? Might need a C++ language lawyer here. — dreamlax, Mar 23 '16 at 00:59

score 4 · Answer 1 · answered Mar 23 '16 at 01:05

According to http://en.cppreference.com/w/cpp/container/unordered_set/operator_cmp you do in fact need the operator== for comparison (I don't have access to the standard right now - I'll try to update with the specific quote sometime tomorrow):

The behavior is undefined if Key is not EqualityComparable.

The behavior is also undefined if Hash and KeyEqual do not have the same behavior on lhs and rhs or if the equality comparison operator for Key is not a refinement of the partition into equivalent-key groups introduced by KeyEqual (that is, if two keys that compare equal fall into different partitions)

score 2 · Accepted Answer · answered Mar 23 '16 at 01:11

"23.2.5 Unordered associative containers" states:

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 distance(Ea1, Ea2) == distance(Eb1, Eb2) and is_permutation(Ea1, Ea2, Eb1) returns true.

Stripping this down, it all comes down to the equality of unordered containers being defined in terms of std::is_permutation().

The important part is that this references the three argument form of std::is_permutation(), and not the four argument form!

In other words, the whole house of cards ends up being reduced to the default operator==, for the contents of the unordered container, rather than the container's official comparison function.

That's my read on this.

Can not compare std::unorded_set with custom KeyEqual

2 Answers2

Linked