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

[Jonathan Wakely]

On 14/01/20 22:25 +0100, François Dumont wrote:
>On 1/13/20 10:53 PM, Jonathan Wakely wrote:
>>On 13/01/20 22:41 +0100, François Dumont wrote:
>>>
>>>For the multi-keys we could still avoid redundant comparisons when 
>>>_Equal is just doing == on the key type. On unordered_multiset we 
>>>could just avoids the call to is_permuation and on the 
>>>unordered_multimap we could check the is_permutation only on the 
>>>associated value rather than on the std::pair.
>>>
>>I don't think that's necessary, or helpful.
>>
>>The idea of https://gcc.gnu.org/ml/libstdc++/2020-01/msg00070.html is
>>that you shouldn't be using _Equal at all, and therefore it doesn't
>>matter whether it's std::equal_to or not.
>>
>>
>And it was indeed possible.

Nice!

>    PR libstdc++/91223
>    * include/bits/hashtable.h (_Hashtable<>): Make _Equality<> friend.
>    * include/bits/hashtable_policy.h: Include <bits/stl_algo.h>.
>    (_Equality_base): Remove.
>    (_Equality<>::_M_equal): Review implementation. Use 
>std::is_permutation.
>    * testsuite/23_containers/unordered_multiset/operators/1.cc
>    (Hash, Equal, test02, test03): New.
>    * testsuite/23_containers/unordered_set/operators/1.cc
>    (Hash, Equal, test02, test03): New.
>
>Tested under Linux x86_64.
>
>Ok to commit ?

Yes, OK for trunk (we're in stage4 but your patch was posted in stage3
and fixes a pretty nasty performance bug, so is OK now).

N.B. GCC has moved to Git instead of Subversion. If you don't have Git
access set up let me know and I can commit the patch for you.