[PATCH] Add unordered containers heterogeneous lookup

[François Dumont]

I think I never got a clear answer that we'll wait for stage 1 to 
consider this patch so here is a ping.


On 01/12/20 8:19 am, François Dumont wrote:
> Let me know if I need to reference a specific paper or any other 
> Standard reference here. Maybe P1690R1 I used here ?
>
> I tried to allow the same partition trick you can have on ordered 
> containers (see Partition in tests) even if here elements are not 
> ordered so I aren't sure there can be any usage of it.
>
>     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):
>             Use template key type.
>             (_Hashtable_base<>::_M_equals): Likewise.
>             * 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): Use template key type.
>             (_Hashtable<>::_M_find_node): Likewise.
>             * 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.
>
> Tested under Linux x86_64 normal and debug modes.
>
> François
>