[Bug libstdc++/91263] unordered_map and unordered_set operator== double key comparison causes exponential behavior

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91263

--- Comment #4 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:d916538965ea260c6bcdb1d46581f6d572017ce8

commit r10-6005-gd916538965ea260c6bcdb1d46581f6d572017ce8
Author: Fran�ois Dumont <fdumont@gcc.gnu.org>
Date:   Thu Jan 16 08:34:21 2020 +0000

    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.