libstdc++: Improve unordered containers == operator (PR 91263)
authorFrançois Dumont <fdumont@gcc.gnu.org>
Thu, 16 Jan 2020 08:34:21 +0000 (08:34 +0000)
committerJonathan Wakely <jwakely@redhat.com>
Thu, 16 Jan 2020 14:39:05 +0000 (14:39 +0000)
commitd916538965ea260c6bcdb1d46581f6d572017ce8
tree59517c6575a40c8df9eb7d343fb009c7cc7de1fe
parent8c197c851e7528baba7cb837f34c05ba2242f705
libstdc++: Improve unordered containers == operator (PR 91263)

Avoid comparing elements with operator== multiple times by replacing
uses of find and equal_range with equivalent inlined code that uses
operator== instead of the container's equality comparison predicate.
This is valid because the standard requires that operator== is a
refinement of the equality predicate.

Also replace the _S_is_permutation function with std::is_permutation,
which wasn't yet implemented when this code was first written.

PR libstdc++/91263
* 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.
libstdc++-v3/ChangeLog
libstdc++-v3/include/bits/hashtable.h
libstdc++-v3/include/bits/hashtable_policy.h
libstdc++-v3/testsuite/23_containers/unordered_multiset/operators/1.cc
libstdc++-v3/testsuite/23_containers/unordered_set/operators/1.cc