Equality of unordered containers violates Library requirements

[Daniel Krügler <daniel.kruegler@…>]

Both unordered sets and maps have operator==/!= implementations that violate the Library requirements of unordered containers. The following program makes this observable:

#include <iostream>
#include <cstring>
#include <boost/unordered_set.hpp>

struct CharIC {

  bool operator()(char c1, char c2) const {
    return std::toupper(c1) == std::toupper(c2);
  }

  std::size_t operator()(char c) const {
    return std::toupper(c);
  }

};

int main()
{
  boost::unordered_set<char, CharIC, CharIC> us1, us2;
  us1.insert('a');
  us2.insert('A');
  std::cout << "us1 == us1: " << (us1 == us1) << std::endl;
  std::cout << "us1 != us2: " << (us1 != us2) << std::endl;
}

The second output is:

us1 != us2: 0

instead of the expected

us1 != us2: 1

Reason for this deviation is that the current boost implementation does not additionally test for equality of the container key (which is the value_type for sets). But this is required as of FDIS, [unord.req] p11, where the semantics is defined in terms of the form of std::is_permutation that uses operator== of the iterator value_type. The proper usage of the key equality test is part of the reference implementation of N3068 as well. As far as I read boost/unordered/detail/equivalent.hpp correctly, the same defect applies to the non-unique containers.

[anonymous]

This is fixed on trunk. The equality implementation in the released version predates the specification, which is why it doesn't follow it.