Re: [PATCH] Add unordered containers heterogeneous lookup
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.
Re: [PATCH] Add unordered containers heterogeneous lookup
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. 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 ? François On 03/02/21 12:24 pm, Jonathan Wakely wrote: On 03/02/21 11:23 +, Jonathan Wakely wrote: 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 s/_M_find_before_node/_M_find_before_node_tr/ _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. diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index bc7ec926155..fa80675ad91 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -724,6 +724,38 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION std::pair equal_range(const key_type& __k) const; +#if __cplusplus > 201702L + template, + typename = __has_is_transparent_t<_Equal, _Kt>> + iterator + _M_find_tr(const _Kt& __k); + + template, + typename = __has_is_transparent_t<_Equal, _Kt>> + const_iterator + _M_find_tr(const _Kt& __k) const; + + template, + typename = __has_is_transparent_t<_Equal, _Kt>> + size_type + _M_count_tr(const _Kt& __k) const; + + template, + typename = __has_is_transparent_t<_Equal, _Kt>> + pair + _M_equal_range_tr(const _Kt& __k); + + template, + typename = __has_is_transparent_t<_Equal, _Kt>> + pair + _M_equal_range_tr(const _Kt& __k) const; +#endif + private: // Bucket index computation helpers. size_type @@ -739,6 +771,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __node_base_ptr _M_find_before_node(size_type, const key_type&, __hash_code) const; + template + __node_base_ptr + _M_find_before_node_tr(size_type, const _Kt&, __hash_code) const; + __node_ptr _M_find_node(size_type __bkt, const key_type& __key,
Re: [PATCH] Add unordered containers heterogeneous lookup
On 03/02/21 11:23 +, Jonathan Wakely wrote: 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 s/_M_find_before_node/_M_find_before_node_tr/ _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.
Re: [PATCH] Add unordered containers heterogeneous lookup
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
Re: [PATCH] Add unordered containers heterogeneous lookup
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
[PATCH] Add unordered containers heterogeneous lookup
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
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 6c6c5edde0b..30d4ee58100 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -724,6 +724,38 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
std::pair
equal_range(const key_type& __k) const;
+#if __cplusplus > 201702L
+ template,
+ typename = __has_is_transparent_t<_Equal, _Kt>>
+ iterator
+ _M_find_tr(const _Kt& __k);
+
+ template,
+ typename = __has_is_transparent_t<_Equal, _Kt>>
+ const_iterator
+ _M_find_tr(const _Kt& __k) const;
+
+ template,
+ typename = __has_is_transparent_t<_Equal, _Kt>>
+ size_type
+ _M_count_tr(const _Kt& __k) const;
+
+ template,
+ typename = __has_is_transparent_t<_Equal, _Kt>>
+ pair
+ _M_equal_range_tr(const _Kt& __k);
+
+ template,
+ typename = __has_is_transparent_t<_Equal, _Kt>>
+ pair
+ _M_equal_range_tr(const _Kt& __k) const;
+#endif
+
private:
// Bucket index computation helpers.
size_type
@@ -736,12 +768,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// Find and insert helper functions and types
// Find the node before the one matching the criteria.
+ template
__node_base_ptr
- _M_find_before_node(size_type, const key_type&, __hash_code) const;
+ _M_find_before_node(size_type, const _Kt&, __hash_code) const;
+ template
__node_ptr
- _M_find_node(size_type __bkt, const key_type& __key,
- __hash_code __c) const
+ _M_find_node(size_type __bkt, const _Kt& __key, __hash_code __c) const
{
__node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c);
if (__before_n)
@@ -1532,6 +1565,40 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return const_iterator(_M_find_node(__bkt, __k, __code));
}
+#if __cplusplus > 201703L
+ template
+template
+ auto
+ _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
+ _M_find_tr(const _Kt& __k)
+ -> iterator
+ {
+ __hash_code __code
