Re: [Boost-users] EqualityComparable of unordered containers

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 :

...

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