[Boost-users] EqualityComparable of unordered containers

Hello, I would like express my respect and congratulations for the provision of boost 1.36 (which had an impressive short release cycle)! One of the very promising new contributions is Boost.Unordered and I I would like to make a comment on the provision of operator==/operator!= as explained in http://www.boost.org/doc/libs/1_36_0/doc/html/unordered/rationale.html#unord... I totally agree that there exist valid and reasonable use-cases for EqualityComparable for unordered containers. In fact many unordered containers (usually named hash containers) exists in one or the other language or user-defined library which provide some form of "unordered" equality comparison, which reflects the unordered nature of the container itself and thus matches a typical user expectation. Nevertheless there exists an unfortunate side-effect of the current implementation of operator== and operator!=, which should be mentioned in the documentation IMO. To keep a long story short: Under some given conditions, EqualityComparable of Boost.Unordered containers will violate the very basic "symmetry" property of EqualityComparable. This can happen, if the equality predicate key_eq() is a runtime-predicate and if the actual comparison is done between two different runtime-comparators. Note that associative containers - even though they also support this kind of runtime/dynamic comparison - are *not* sensitive to this unexpected behaviour. The simple reason is that the implementation uses an asymmetric algorithm to realize the concept. The program provided at tghe end of this posting demonstrates this kind of violation of the usual symmetric property of EqualityComparable. The output should be: s1 == s2: 1 s2 == s1: 0 I hope this comment is not understood as some form of destructive criticism. AFAIK there does not exist any general valid algorithm which can realize a pure *symmetric* unordered equality comparison with an average linear complexitity. My point is, that I strongly propose to mention this unexpected property and/or to declare code as causing undefined behaviour if it attempts to use EqualityComparable of unordered containers if the predicate is dynamic and different between the compared containers. Greetings from Bremen, Daniel #include <cctype> #include <iostream> #include <ostream> #include typedef boost::unordered_set MySet; std::size_t hash_char(char c) { return static_caststd::size_t(c); } bool eq_char(char c1, char c2) { return c1 == c2; } std::size_t hash_char_ic(char c) { return static_caststd::size_t(std::tolower(c)); } bool eq_char_ic(char c1, char c2) { return std::tolower(c1) == std::tolower(c2); } int main() { MySet s1(1, hash_char, eq_char); s1.insert('A'); MySet s2(1, hash_char_ic, eq_char_ic); s2.insert('a'); bool t1 = s1 == s2; std::cout << "s1 == s2: " << t1 << std::endl; bool t2 = s2 == s1; std::cout << "s2 == s1: " << t2 << std::endl; std::cin.get(); }