Re: [Boost-users] EqualityComparable of unordered containers

From: Daniel James (daniel_james_at_[hidden])
Date: 2008-08-18 06:26:41

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.

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

thanks,

Daniel