[PATCH] Add unordered containers heterogeneous lookup

[Jonathan Wakely]

On 04/02/21 21:20 +0100, François Dumont wrote:
>    Considering that most of the code is already new code it doesn't 
>look like a major tradeoff duplicate some more code.
>
>    So here is a new proposal with only new code. However I left the 
>new few XXX_tr methods accessible even in C++11 because I'll use them 
>to propose a fix for PR 98066 when back in stage 1.

OK.

>    libstdc++: Add unordered containers heterogeneous lookup
>
>    Add unordered containers heterogeneous lookup member functions 
>find, count, contains and
>    equal_range in C++20. Those members are considered for overload 
>resolution only if hash and
>    equal functors used to instantiate the container have a nested 
>is_transparent type.
>
>    libstdc++-v3/ChangeLog:
>
>            * include/bits/stl_tree.h
>            (__has_is_transparent, __has_is_transparent_t): Move...
>            * include/bits/stl_function.h: ...here.
>            * include/bits/hashtable_policy.h 
>(_Hash_code_base<>::_M_hash_code_tr): New..
>            (_Hashtable_base<>::_M_equals_tr): New.
>            * include/bits/hashtable.h (_Hashtable<>::_M_find_tr, 
>_Hashtable<>::_M_count_tr,
>            _Hashtable<>::_M_equal_range_tr): New member function 
>templates to perform
>            heterogeneous lookup.
>            (_Hashtable<>::_M_find_before_node_tr): New.
>            (_Hashtable<>::_M_find_node_tr): New.
>            * include/bits/unordered_map.h (unordered_map::find<>, 
>unordered_map::count<>,
>            unordered_map::contains<>, unordered_map::equal_range<>): 
>New member function
>            templates to perform heterogeneous lookup.
>            (unordered_multimap::find<>, unordered_multimap::count<>,
>            unordered_multimap::contains<>, 
>unordered_multimap::equal_range<>): Likewise.
>            * include/bits/unordered_set.h (unordered_set::find<>, 
>unordered_set::count<>,
>            unordered_set::contains<>, unordered_set::equal_range<>): 
>Likewise.
>            (unordered_multiset::find<>, unordered_multiset::count<>,
>            unordered_multiset::contains<>, 
>unordered_multiset::equal_range<>): Likewise.
>            * include/debug/unordered_map
>            (unordered_map::find<>, unordered_map::equal_range<>): 
>Likewise.
>            (unordered_multimap::find<>, 
>unordered_multimap::equal_range<>): Likewise.
>            * include/debug/unordered_set
>            (unordered_set::find<>, unordered_set::equal_range<>): 
>Likewise.
>            (unordered_multiset::find<>, 
>unordered_multiset::equal_range<>): Likewise.
>            * testsuite/23_containers/unordered_map/operations/1.cc: 
>New test.
>            * 
>testsuite/23_containers/unordered_multimap/operations/1.cc: New test.
>            * 
>testsuite/23_containers/unordered_multiset/operations/1.cc: New test.
>            * testsuite/23_containers/unordered_set/operations/1.cc: 
>New test.
>
>New test run under Linux x86_64.
>
>Ok to commit if all tests pass ?

Yes, thanks for reworking it to only add new code.