Re: [PATCH] Add unordered containers heterogeneous lookup

[Jonathan Wakely <jwakely@redhat.com>]

On 25/01/21 19:21 +0100, François Dumont via Libstdc++ wrote:
>I think I never got a clear answer that we'll wait for stage 1 to 
>consider this patch so here is a ping.

My concern with this patch is that it alters the existing code used
for non-heterogeneous lookups in C++11/14/17. I think if we're going
to do thatk, it needs to wait for stage 1.

If the new C++20 code was added with new _M_find_before_node and
_M_find_node_tr members (duplicating the existing code) then it would
be safe to add now, because it wouldn't touch the stable C++11/14/17
code.


>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
>>
>