[PATCH] libstdc++/91223 Improve unordered containers == operator

Jonathan Wakely jwakely@redhat.com
Sat Jan 11 01:19:00 GMT 2020


On 10/01/20 22:01 +0000, Jonathan Wakely wrote:
>On 10/01/20 18:54 +0100, François Dumont wrote:
>>Hi
>>
>>    Here is my attempt to improve == operator.
>>
>>    There is a small optimization for the std::unordered_mutiXXX 
>>containers but the main enhancement rely on some partial template 
>>specialization of the _Equality type. I limit it to usage of 
>>unordered containers with std::equal_to to be sure that the 
>>container _Equal functor is like the key type ==.
>
>I think we can assume that for any _Equal, not just std::equal_to:
>http://eel.is/c++draft/unord.req#12.sentence-5
>
>However ...
>
>>    Do I need to also consider user partial template specialization 
>>of std::equal_to ? It is a well know bad practice so I hope the 
>>Standard says that such a partial specialization leads to undefined 
>>behavior.
>
>It's certainly not undefined to specialize equal_to, and I'm not sure
>how to make your optimisations valid in that case.
>
>Consider:
>
>struct X
>{
>  int i;
>  int rounded() const { return i - (i % 10); }
>  bool operator==(X x) const { return i == x.i; }
>};
>
>template<> struct std::equal_to<X>
>{
>  bool operator()(X l, X r) const
>  { return l.rounded() == r.rounded(); }
>};
>
>template<> std::hash<X>
>{
>  bool operator()(X x) const { return hash<int>()(x.rounded()); }
>};
>
>std::unordered_multiset<X> u{ X{10}, X{11}, X{12} };
>std::unordered_multiset<X> v{ X{15}, X{16}, X{17} };
>bool b1 = u == v;
>bool b2 = std::is_permutation(u.begin(), u.end(), v.begin());
>assert(b1 == b2);
>
>I think the last new specialization in your patch would be used for
>this case, and because __x_count == v.count(*u.begin()) it will say
>they're equal. But the is_permutation call says they're not.
>
>So I think the assertion would fail, but the standard says it should
>pass. Am I mistaken?

I believe the optimization would still be valid if you do not use
__other.count(*__itx) to check for equivalent keys in the other
container. Your patch does:

+	  if (__x_count != __other.count(*__itx))
+	    return false;

This uses the _Equal predicate to count the equivalent elements in
__other. Instead you need to use operator== to count the **equal**
elements.

I think there's a similar problem in the _Equality specialization for
unordered_map (i.e. key-value pairs, unique keys):

+	  const auto __ity = __other.find(__itx->first);
+	  if (__ity == __other.end() || !bool(__ity->second == __itx->second))
+	    return false;

The call to __other.find(__itx->first) will return an element with
equivalent key, but that's not guaranteed to be equal. I think you
could fix this either by still using == to compare the keys after
__other.find(*__itx) returns an element (which doesn't fix the PR91263
bug) or by replacing find with a similar operation that looks up the
hash code and then uses == to test for equality (instead of using
_Equal pred to test for equivalent keys).

Basically, you can't use functions like find and count that rely on
equivalence of keys, you need to use handwritten lookups using ==.

And if you do that, then it doesn't matter whether _Equal is a
specialization of std::equal_to or not, and it doesn't matter whether
the user has defined their own specialization of std::equal_to. You
can do the optimizations for any _Equal, because you won't actually be
using it to test for equality.

Does that make sense?





More information about the Libstdc++ mailing list