Re: [Boost-users] EqualityComparable of unordered containers

From: David Abrahams (dave_at_[hidden])
Date: 2008-08-18 06:37:52

on Mon Aug 18 2008, Daniel Krügler <dsp-AT-bdal.de> wrote:

> 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.

I suggest requiring that the predicates themselves be equality
comparable, and that equal predicates perform the same computation.
Containers with unequal predicates would not be considered equal.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com