[Boost-users] EqualityComparable of unordered containers

From: Daniel Krügler (dsp_at_[hidden])
Date: 2008-08-18 06:00:40

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#unordered.rationale.equality_operators

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 <boost/unordered_set.hpp>

typedef boost::unordered_set<char, std::size_t(*)(char), bool (*)(char, 
char)> MySet;

std::size_t hash_char(char c) {
        return static_cast<std::size_t>(c);
}

bool eq_char(char c1, char c2) {
        return c1 == c2;
}

std::size_t hash_char_ic(char c) {
        return static_cast<std::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();
}