Re: [Boost-users] EqualityComparable of unordered containers

From: Daniel Krügler (dsp_at_[hidden])
Date: 2008-08-18 07:33:36

Daniel and David,

Thank you very much for your replies!

I use Daniel's posting as the combined reply channel:

Daniel James wrote:
> 2008/8/18 Daniel Krügler <dsp_at_[hidden]>:
> 
>>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.
> 
> 
> Not at all, it's a good point. I should have written more about the
> potential issues (and perhaps by extension thought about them more).
> 
> I could have implemented this in a 'safer' way if I could compare the
> hash and equality functions, I could do that for function pointers,
> but not for function objects. Although with C++0x concepts, I think we
> might be able to detect if a function object if comparable.
> 
> We could do the comparison in both directions which would at least be
> symmetric. Although it would have still have surprising results for
> situations like the one you described and I don't think people would
> accept the efficiency hit.

David Abrahams wrote:
> 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.

Yes, this proposed resolution has also be given by Pablo Halpern
in a different mailing channnel. I totally agree that some tagging
technique (or concepts in C++0x) would be good idea. I had some 
resistance concerning requiring EqualityComparable for non-empty 
predicates (This was his very nice idea: Distinguish empty from
non-empty predicates and require EqualityComparable only for non-empty
ones), because I thought it would be too intrusive. Maybe I was to
strict in my position. The reason for my resistance is that in several
scenarios an object type with overloaded operator() has *more*
than one operator() overload and by requiring operator== this would
have the effect that we don't know, for *which* overload of
operator() this EqualityComparable concept would apply.
If a yet-to-be-defined concept would be used that would also
"encode" the argument types of the comparison, this would solve
this particular problem [Note: One might argue that Allocators
also provide operator==, but IMO it is a much rarer situation,
that an allocator *also* implements a *different* allocator].

Daniel James wrote:
> Anyway, I'll add something to the reference documentation and the
> custom hash function/equality operator section to explain the
> pitfalls.

IMO, this is an excellent idea.

- Daniel