* [PATCH] Add unordered containers heterogeneous lookup @ 2020-12-01 7:19 François Dumont 2021-01-25 18:21 ` François Dumont 0 siblings, 1 reply; 6+ messages in thread From: François Dumont @ 2020-12-01 7:19 UTC (permalink / raw) To: libstdc++, gcc-patches [-- Attachment #1: Type: text/plain, Size: 3273 bytes --] 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 [-- Attachment #2: heterogeneous_lookup.patch --] [-- Type: text/x-patch, Size: 45594 bytes --] 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<const_iterator, const_iterator> equal_range(const key_type& __k) const; +#if __cplusplus > 201702L + template<typename _Kt, + typename = __has_is_transparent_t<_Hash, _Kt>, + typename = __has_is_transparent_t<_Equal, _Kt>> + iterator + _M_find_tr(const _Kt& __k); + + template<typename _Kt, + typename = __has_is_transparent_t<_Hash, _Kt>, + typename = __has_is_transparent_t<_Equal, _Kt>> + const_iterator + _M_find_tr(const _Kt& __k) const; + + template<typename _Kt, + typename = __has_is_transparent_t<_Hash, _Kt>, + typename = __has_is_transparent_t<_Equal, _Kt>> + size_type + _M_count_tr(const _Kt& __k) const; + + template<typename _Kt, + typename = __has_is_transparent_t<_Hash, _Kt>, + typename = __has_is_transparent_t<_Equal, _Kt>> + pair<iterator, iterator> + _M_equal_range_tr(const _Kt& __k); + + template<typename _Kt, + typename = __has_is_transparent_t<_Hash, _Kt>, + typename = __has_is_transparent_t<_Equal, _Kt>> + pair<const_iterator, const_iterator> + _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<typename _Kt> __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<typename _Kt> __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<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> + template<typename _Kt, typename, typename> + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_find_tr(const _Kt& __k) + -> iterator + { + __hash_code __code = this->_M_hash_code(__k); + std::size_t __bkt = _M_bucket_index(__code); + return iterator(_M_find_node(__bkt, __k, __code)); + } + + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> + template<typename _Kt, typename, typename> + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_find_tr(const _Kt& __k) const + -> const_iterator + { + __hash_code __code = this->_M_hash_code(__k); + std::size_t __bkt = _M_bucket_index(__code); + return const_iterator(_M_find_node(__bkt, __k, __code)); + } +#endif + template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, typename _Hash, typename _RangeHash, typename _Unused, @@ -1561,6 +1628,37 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return __result; } +#if __cplusplus > 201703L + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> + template<typename _Kt, typename, typename> + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_count_tr(const _Kt& __k) const + -> size_type + { + __hash_code __code = this->_M_hash_code(__k); + std::size_t __bkt = _M_bucket_index(__code); + auto __n = _M_find_node(__bkt, __k, __code); + if (!__n) + return 0; + + // All equivalent values are next to each other, if we find a + // non-equivalent value after an equivalent one it means that we won't + // find any new equivalent value. + iterator __it(__n); + size_type __result = 1; + for (++__it; __it._M_cur && this->_M_equals(__k, __code, *__it._M_cur); + ++__it) + ++__result; + + return __result; + } +#endif + template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, typename _Hash, typename _RangeHash, typename _Unused, @@ -1615,16 +1713,75 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return { __beg, __ite }; } +#if __cplusplus > 201703L + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> + template<typename _Kt, typename, typename> + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_equal_range_tr(const _Kt& __k) + -> pair<iterator, iterator> + { + __hash_code __code = this->_M_hash_code(__k); + std::size_t __bkt = _M_bucket_index(__code); + auto __n = _M_find_node(__bkt, __k, __code); + iterator __ite(__n); + if (!__n) + return { __ite, __ite }; + + // All equivalent values are next to each other, if we find a + // non-equivalent value after an equivalent one it means that we won't + // find any new equivalent value. + auto __beg = __ite++; + while (__ite._M_cur && this->_M_equals(__k, __code, *__ite._M_cur)) + ++__ite; + + return { __beg, __ite }; + } + + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> + template<typename _Kt, typename, typename> + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_equal_range_tr(const _Kt& __k) const + -> pair<const_iterator, const_iterator> + { + __hash_code __code = this->_M_hash_code(__k); + std::size_t __bkt = _M_bucket_index(__code); + auto __n = _M_find_node(__bkt, __k, __code); + const_iterator __ite(__n); + if (!__n) + return { __ite, __ite }; + + // All equivalent values are next to each other, if we find a + // non-equivalent value after an equivalent one it means that we won't + // find any new equivalent value. + auto __beg = __ite++; + while (__ite._M_cur && this->_M_equals(__k, __code, *__ite._M_cur)) + ++__ite; + + return { __beg, __ite }; + } +#endif + // Find the node before the one whose key compares equal to k in the bucket // bkt. Return nullptr if no node is found. template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> + template<typename _Kt> auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_find_before_node(size_type __bkt, const key_type& __k, + _M_find_before_node(size_type __bkt, const _Kt& __k, __hash_code __code) const -> __node_base_ptr { diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index 28372979c87..340aaede50c 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -1211,10 +1211,11 @@ namespace __detail _Hash_code_base() = default; _Hash_code_base(const _Hash& __hash) : __ebo_hash(__hash) { } + template<typename _Kt> __hash_code - _M_hash_code(const _Key& __k) const + _M_hash_code(const _Kt& __k) const { - static_assert(__is_invocable<const _Hash&, const _Key&>{}, + static_assert(__is_invocable<const _Hash&, const _Kt&>{}, "hash function must be invocable with an argument of key type"); return _M_hash()(__k); } @@ -1597,11 +1598,14 @@ namespace __detail : __hash_code_base(__hash), _EqualEBO(__eq) { } + template<typename _Kt> bool - _M_equals(const _Key& __k, __hash_code __c, - const _Hash_node_value<_Value, __hash_cached::value>& __n) const + _M_equals(const _Kt& __k, __hash_code __c, + const _Hash_node_value<_Value, + __hash_cached::value>& __n) const { - static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{}, + static_assert( + __is_invocable<const _Equal&, const _Kt&, const _Key&>{}, "key equality predicate must be invocable with two arguments of " "key type"); return _S_equals(__c, __n) && _M_eq()(__k, _ExtractKey{}(__n._M_v())); diff --git a/libstdc++-v3/include/bits/stl_function.h b/libstdc++-v3/include/bits/stl_function.h index 77f8ccb051a..37dab358558 100644 --- a/libstdc++-v3/include/bits/stl_function.h +++ b/libstdc++-v3/include/bits/stl_function.h @@ -1385,6 +1385,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION /** @} */ +#if __cplusplus >= 201402L + template<typename _Func, typename _SfinaeType, typename = __void_t<>> + struct __has_is_transparent + { }; + + template<typename _Func, typename _SfinaeType> + struct __has_is_transparent<_Func, _SfinaeType, + __void_t<typename _Func::is_transparent>> + { typedef void type; }; + + template<typename _Func, typename _SfinaeType> + using __has_is_transparent_t + = typename __has_is_transparent<_Func, _SfinaeType>::type; +#endif + _GLIBCXX_END_NAMESPACE_VERSION } // namespace diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h index a51d6da4ae8..3f854ace63b 100644 --- a/libstdc++-v3/include/bits/stl_tree.h +++ b/libstdc++-v3/include/bits/stl_tree.h @@ -415,21 +415,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, _Rb_tree_node_base& __header) throw (); -#if __cplusplus >= 201402L - template<typename _Cmp, typename _SfinaeType, typename = __void_t<>> - struct __has_is_transparent - { }; - - template<typename _Cmp, typename _SfinaeType> - struct __has_is_transparent<_Cmp, _SfinaeType, - __void_t<typename _Cmp::is_transparent>> - { typedef void type; }; - - template<typename _Cmp, typename _SfinaeType> - using __has_is_transparent_t - = typename __has_is_transparent<_Cmp, _SfinaeType>::type; -#endif - #if __cplusplus > 201402L template<typename _Tree1, typename _Cmp2> struct _Rb_tree_merge_helper { }; diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h index 1aaa1a1a6ee..1a7bee28857 100644 --- a/libstdc++-v3/include/bits/unordered_map.h +++ b/libstdc++-v3/include/bits/unordered_map.h @@ -868,11 +868,26 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER find(const key_type& __x) { return _M_h.find(__x); } +#if __cplusplus > 201703L + template<typename _Kt> + auto + find(const _Kt& __x) -> decltype(_M_h._M_find_tr(__x)) + { return _M_h._M_find_tr(__x); } +#endif + const_iterator find(const key_type& __x) const { return _M_h.find(__x); } + +#if __cplusplus > 201703L + template<typename _Kt> + auto + find(const _Kt& __x) const -> decltype(_M_h._M_find_tr(__x)) + { return _M_h._M_find_tr(__x); } +#endif //@} + //@{ /** * @brief Finds the number of elements. * @param __x Key to count. @@ -887,6 +902,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return _M_h.count(__x); } #if __cplusplus > 201703L + template<typename _Kt> + auto + count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x)) + { return _M_h._M_count_tr(__x); } +#endif + //@} + +#if __cplusplus > 201703L + //@{ /** * @brief Finds whether an element with the given key exists. * @param __x Key of elements to be located. @@ -895,6 +919,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER bool contains(const key_type& __x) const { return _M_h.find(__x) != _M_h.end(); } + + template<typename _Kt> + auto + contains(const _Kt& __x) const + -> decltype(_M_h._M_find_tr(__x), void(), true) + { return _M_h._M_find_tr(__x) != _M_h.end(); } + //@} #endif //@{ @@ -910,9 +941,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER equal_range(const key_type& __x) { return _M_h.equal_range(__x); } +#if __cplusplus > 201703L + template<typename _Kt> + auto + equal_range(const _Kt& __x) + -> decltype(_M_h._M_equal_range_tr(__x)) + { return _M_h._M_equal_range_tr(__x); } +#endif + std::pair<const_iterator, const_iterator> equal_range(const key_type& __x) const { return _M_h.equal_range(__x); } + +#if __cplusplus > 201703L + template<typename _Kt> + auto + equal_range(const _Kt& __x) const + -> decltype(_M_h._M_equal_range_tr(__x)) + { return _M_h._M_equal_range_tr(__x); } +#endif //@} //@{ @@ -1764,11 +1811,26 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER find(const key_type& __x) { return _M_h.find(__x); } +#if __cplusplus > 201703L + template<typename _Kt> + auto + find(const _Kt& __x) -> decltype(_M_h._M_find_tr(__x)) + { return _M_h._M_find_tr(__x); } +#endif + const_iterator find(const key_type& __x) const { return _M_h.find(__x); } + +#if __cplusplus > 201703L + template<typename _Kt> + auto + find(const _Kt& __x) const -> decltype(_M_h._M_find_tr(__x)) + { return _M_h._M_find_tr(__x); } +#endif //@} + //@{ /** * @brief Finds the number of elements. * @param __x Key to count. @@ -1779,6 +1841,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return _M_h.count(__x); } #if __cplusplus > 201703L + template<typename _Kt> + auto + count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x)) + { return _M_h._M_count_tr(__x); } +#endif + //@} + +#if __cplusplus > 201703L + //@{ /** * @brief Finds whether an element with the given key exists. * @param __x Key of elements to be located. @@ -1787,6 +1858,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER bool contains(const key_type& __x) const { return _M_h.find(__x) != _M_h.end(); } + + template<typename _Kt> + auto + contains(const _Kt& __x) const + -> decltype(_M_h._M_find_tr(__x), void(), true) + { return _M_h._M_find_tr(__x) != _M_h.end(); } + //@} #endif //@{ @@ -1800,9 +1878,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER equal_range(const key_type& __x) { return _M_h.equal_range(__x); } +#if __cplusplus > 201703L + template<typename _Kt> + auto + equal_range(const _Kt& __x) + -> decltype(_M_h._M_equal_range_tr(__x)) + { return _M_h._M_equal_range_tr(__x); } +#endif + std::pair<const_iterator, const_iterator> equal_range(const key_type& __x) const { return _M_h.equal_range(__x); } + +#if __cplusplus > 201703L + template<typename _Kt> + auto + equal_range(const _Kt& __x) const + -> decltype(_M_h._M_equal_range_tr(__x)) + { return _M_h._M_equal_range_tr(__x); } +#endif //@} // bucket interface. diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h index 6cbfcb1f0b6..f5391e1bdf2 100644 --- a/libstdc++-v3/include/bits/unordered_set.h +++ b/libstdc++-v3/include/bits/unordered_set.h @@ -650,11 +650,28 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER find(const key_type& __x) { return _M_h.find(__x); } +#if __cplusplus > 201703L + template<typename _Kt> + auto + find(const _Kt& __k) + -> decltype(_M_h._M_find_tr(__k)) + { return _M_h._M_find_tr(__k); } +#endif + const_iterator find(const key_type& __x) const { return _M_h.find(__x); } + +#if __cplusplus > 201703L + template<typename _Kt> + auto + find(const _Kt& __k) const + -> decltype(_M_h._M_find_tr(__k)) + { return _M_h._M_find_tr(__k); } +#endif //@} + //@{ /** * @brief Finds the number of elements. * @param __x Element to located. @@ -669,6 +686,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return _M_h.count(__x); } #if __cplusplus > 201703L + template<typename _Kt> + auto + count(const _Kt& __k) const + -> decltype(_M_h._M_count_tr(__k)) + { return _M_h._M_count_tr(__k); } +#endif + //@} + +#if __cplusplus > 201703L + //@{ /** * @brief Finds whether an element with the given key exists. * @param __x Key of elements to be located. @@ -677,6 +704,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER bool contains(const key_type& __x) const { return _M_h.find(__x) != _M_h.end(); } + + template<typename _Kt> + auto + contains(const _Kt& __k) const + -> decltype(_M_h._M_find_tr(__k), void(), true) + { return _M_h._M_find_tr(__k) != _M_h.end(); } + //@} #endif //@{ @@ -692,9 +726,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER equal_range(const key_type& __x) { return _M_h.equal_range(__x); } +#if __cplusplus > 201703L + template<typename _Kt> + auto + equal_range(const _Kt& __k) + -> decltype(_M_h._M_equal_range_tr(__k)) + { return _M_h._M_equal_range_tr(__k); } +#endif + std::pair<const_iterator, const_iterator> equal_range(const key_type& __x) const { return _M_h.equal_range(__x); } + +#if __cplusplus > 201703L + template<typename _Kt> + auto + equal_range(const _Kt& __k) const + -> decltype(_M_h._M_equal_range_tr(__k)) + { return _M_h._M_equal_range_tr(__k); } +#endif //@} // bucket interface. @@ -1450,11 +1500,28 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER find(const key_type& __x) { return _M_h.find(__x); } +#if __cplusplus > 201703L + template<typename _Kt> + auto + find(const _Kt& __x) + -> decltype(_M_h._M_find_tr(__x)) + { return _M_h._M_find_tr(__x); } +#endif + const_iterator find(const key_type& __x) const { return _M_h.find(__x); } + +#if __cplusplus > 201703L + template<typename _Kt> + auto + find(const _Kt& __x) const + -> decltype(_M_h._M_find_tr(__x)) + { return _M_h._M_find_tr(__x); } +#endif //@} + //@{ /** * @brief Finds the number of elements. * @param __x Element to located. @@ -1465,6 +1532,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return _M_h.count(__x); } #if __cplusplus > 201703L + template<typename _Kt> + auto + count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x)) + { return _M_h._M_count_tr(__x); } +#endif + //@} + +#if __cplusplus > 201703L + //@{ /** * @brief Finds whether an element with the given key exists. * @param __x Key of elements to be located. @@ -1473,6 +1549,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER bool contains(const key_type& __x) const { return _M_h.find(__x) != _M_h.end(); } + + template<typename _Kt> + auto + contains(const _Kt& __x) const + -> decltype(_M_h._M_find_tr(__x), void(), true) + { return _M_h._M_find_tr(__x) != _M_h.end(); } + //@} #endif //@{ @@ -1486,9 +1569,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER equal_range(const key_type& __x) { return _M_h.equal_range(__x); } +#if __cplusplus > 201703L + template<typename _Kt> + auto + equal_range(const _Kt& __x) + -> decltype(_M_h._M_equal_range_tr(__x)) + { return _M_h._M_equal_range_tr(__x); } +#endif + std::pair<const_iterator, const_iterator> equal_range(const key_type& __x) const { return _M_h.equal_range(__x); } + +#if __cplusplus > 201703L + template<typename _Kt> + auto + equal_range(const _Kt& __x) const + -> decltype(_M_h._M_equal_range_tr(__x)) + { return _M_h._M_equal_range_tr(__x); } +#endif //@} // bucket interface. diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map index bae179b58ac..a9f7452f841 100644 --- a/libstdc++-v3/include/debug/unordered_map +++ b/libstdc++-v3/include/debug/unordered_map @@ -545,10 +545,28 @@ namespace __debug find(const key_type& __key) { return { _Base::find(__key), this }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + iterator + find(const _Kt& __k) + { return { _Base::find(__k), this }; } +#endif + const_iterator find(const key_type& __key) const { return { _Base::find(__key), this }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + const_iterator + find(const _Kt& __k) const + { return { _Base::find(__k), this }; } +#endif + std::pair<iterator, iterator> equal_range(const key_type& __key) { @@ -556,6 +574,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair<iterator, iterator> + equal_range(const _Kt& __k) + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + std::pair<const_iterator, const_iterator> equal_range(const key_type& __key) const { @@ -563,6 +593,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair<const_iterator, const_iterator> + equal_range(const _Kt& __k) const + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + size_type erase(const key_type& __key) { @@ -1157,10 +1199,28 @@ namespace __debug find(const key_type& __key) { return { _Base::find(__key), this }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + iterator + find(const _Kt& __k) + { return { _Base::find(__k), this }; } +#endif + const_iterator find(const key_type& __key) const { return { _Base::find(__key), this }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + const_iterator + find(const _Kt& __k) const + { return { _Base::find(__k), this }; } +#endif + std::pair<iterator, iterator> equal_range(const key_type& __key) { @@ -1168,6 +1228,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair<iterator, iterator> + equal_range(const _Kt& __k) + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + std::pair<const_iterator, const_iterator> equal_range(const key_type& __key) const { @@ -1175,6 +1247,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair<const_iterator, const_iterator> + equal_range(const _Kt& __k) const + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + size_type erase(const key_type& __key) { diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set index 97e6a74ebb4..6b7cb8b5108 100644 --- a/libstdc++-v3/include/debug/unordered_set +++ b/libstdc++-v3/include/debug/unordered_set @@ -430,10 +430,28 @@ namespace __debug find(const key_type& __key) { return { _Base::find(__key), this }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + iterator + find(const _Kt& __k) + { return { _Base::find(__k), this }; } +#endif + const_iterator find(const key_type& __key) const { return { _Base::find(__key), this }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + const_iterator + find(const _Kt& __k) const + { return { _Base::find(__k), this }; } +#endif + std::pair<iterator, iterator> equal_range(const key_type& __key) { @@ -441,6 +459,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair<iterator, iterator> + equal_range(const _Kt& __k) + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + std::pair<const_iterator, const_iterator> equal_range(const key_type& __key) const { @@ -448,6 +478,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair<const_iterator, const_iterator> + equal_range(const _Kt& __k) const + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + size_type erase(const key_type& __key) { @@ -1002,10 +1044,28 @@ namespace __debug find(const key_type& __key) { return { _Base::find(__key), this }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + iterator + find(const _Kt& __k) + { return { _Base::find(__k), this }; } +#endif + const_iterator find(const key_type& __key) const { return { _Base::find(__key), this }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + const_iterator + find(const _Kt& __k) const + { return { _Base::find(__k), this }; } +#endif + std::pair<iterator, iterator> equal_range(const key_type& __key) { @@ -1013,6 +1073,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair<iterator, iterator> + equal_range(const _Kt& __k) + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + std::pair<const_iterator, const_iterator> equal_range(const key_type& __key) const { @@ -1020,6 +1092,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair<const_iterator, const_iterator> + equal_range(const _Kt& __k) const + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + size_type erase(const key_type& __key) { diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/operations/1.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/operations/1.cc new file mode 100644 index 00000000000..df9dcd62478 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/operations/1.cc @@ -0,0 +1,168 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-do run { target c++20 } } + +#include <unordered_map> +#include <testsuite_hooks.h> + +struct Equal +{ + typedef void is_transparent; + + bool operator()(int i, long l) const { return i == l; } + bool operator()(long l, int i) const { return l == i; } + bool operator()(int i, int j) const { ++count; return i == j; } + + static int count; +}; + +int Equal::count = 0; + +struct Hash +{ + typedef void is_transparent; + + std::size_t operator()(int i) const { ++count; return i; } + std::size_t operator()(long l) const { return l; } + + static int count; +}; + +int Hash::count = 0; + +using test_type = std::unordered_map<int, char, Hash, Equal>; + +test_type x{ { 1, '2' }, { 3, '4' } }; +const test_type& cx = x; + +void +test01() +{ + Hash::count = 0; + Equal::count = 0; + + VERIFY( x.contains(1L) ); + + auto it = x.find(1L); + VERIFY( it != x.end() && it->second == '2' ); + it = x.find(2L); + VERIFY( it == x.end() ); + + auto cit = cx.find(3L); + VERIFY( cit != cx.end() && cit->second == '4' ); + cit = cx.find(2L); + VERIFY( cit == cx.end() ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); + + static_assert(std::is_same<decltype(it), test_type::iterator>::value, + "find returns iterator"); + static_assert(std::is_same<decltype(cit), test_type::const_iterator>::value, + "const find returns const_iterator"); +} + +void +test02() +{ + Hash::count = 0; + Equal::count = 0; + + auto n = x.count(1L); + VERIFY( n == 1 ); + n = x.count(2L); + VERIFY( n == 0 ); + + auto cn = cx.count(3L); + VERIFY( cn == 1 ); + cn = cx.count(2L); + VERIFY( cn == 0 ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); +} + +void +test03() +{ + Hash::count = 0; + Equal::count = 0; + + auto it = x.equal_range(1L); + VERIFY( it.first != it.second && it.first->second == '2' ); + it = x.equal_range(2L); + VERIFY( it.first == it.second && it.first == x.end() ); + + auto cit = cx.equal_range(1L); + VERIFY( cit.first != cit.second && cit.first->second == '2' ); + cit = cx.equal_range(2L); + VERIFY( cit.first == cit.second && cit.first == cx.end() ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); + + using pair = std::pair<test_type::iterator, test_type::iterator>; + static_assert(std::is_same<decltype(it), pair>::value, + "equal_range returns pair<iterator, iterator>"); + using cpair = std::pair<test_type::const_iterator, test_type::const_iterator>; + static_assert(std::is_same<decltype(cit), cpair>::value, + "const equal_range returns pair<const_iterator, const_iterator>"); +} + +void +test04() +{ + struct E + { + bool operator()(int l, int r) const { return l == r; } + + struct Partition { }; + + bool operator()(int l, Partition) const { return l < 6; } + bool operator()(Partition, int r) const { return 3 < r; } + + using is_transparent = void; + }; + + struct H + { + size_t + operator()(int x) const + { return 0; } + + size_t + operator()(E::Partition) const + { return 0; } + + using is_transparent = void; + }; + + std::unordered_map<int, int, H, E> m{ {1,0}, {2,0}, {3,0}, {4, 0}, {5, 0} }; + + auto n = m.count(E::Partition{}); + VERIFY( n == 2 ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/operations/1.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/operations/1.cc new file mode 100644 index 00000000000..28d8233076b --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/operations/1.cc @@ -0,0 +1,135 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-do run { target c++20 } } + +#include <unordered_map> +#include <testsuite_hooks.h> + +struct Equal +{ + typedef void is_transparent; + + bool operator()(int i, long l) const { return i == l; } + bool operator()(long l, int i) const { return l == i; } + bool operator()(int i, int j) const { ++count; return i == j; } + + static int count; +}; + +int Equal::count = 0; + +struct Hash +{ + typedef void is_transparent; + + std::size_t operator()(int i) const { ++count; return i; } + std::size_t operator()(long l) const { return l; } + + static int count; +}; + +int Hash::count = 0; + +using test_type = std::unordered_multimap<int, char, Hash, Equal>; + +test_type x{ { 1, '2' }, { 3, '4' }, { 3, '5' } }; +const test_type& cx = x; + +void +test01() +{ + Hash::count = 0; + Equal::count = 0; + + VERIFY( x.contains(1L) ); + + auto it = x.find(1L); + VERIFY( it != x.end() && it->second == '2' ); + it = x.find(2L); + VERIFY( it == x.end() ); + + auto cit = cx.find(3L); + VERIFY( cit != cx.end() && cit->second == '5' ); + cit = cx.find(2L); + VERIFY( cit == cx.end() ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); + + static_assert(std::is_same<decltype(it), test_type::iterator>::value, + "find returns iterator"); + static_assert(std::is_same<decltype(cit), test_type::const_iterator>::value, + "const find returns const_iterator"); +} + +void +test02() +{ + Hash::count = 0; + Equal::count = 0; + + auto n = x.count(1L); + VERIFY( n == 1 ); + n = x.count(2L); + VERIFY( n == 0 ); + + auto cn = cx.count(3L); + VERIFY( cn == 2 ); + cn = cx.count(2L); + VERIFY( cn == 0 ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); +} + +void +test03() +{ + Hash::count = 0; + Equal::count = 0; + + auto it = x.equal_range(1L); + VERIFY( it.first != it.second && it.first->second == '2' ); + it = x.equal_range(2L); + VERIFY( it.first == it.second && it.first == x.end() ); + + auto cit = cx.equal_range(3L); + VERIFY( cit.first != cit.second && cit.first->second == '5' ); + VERIFY( std::distance(cit.first, cit.second) == 2 ); + cit = cx.equal_range(2L); + VERIFY( cit.first == cit.second && cit.first == cx.end() ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); + + using pair = std::pair<test_type::iterator, test_type::iterator>; + static_assert(std::is_same<decltype(it), pair>::value, + "equal_range returns pair<iterator, iterator>"); + using cpair = std::pair<test_type::const_iterator, test_type::const_iterator>; + static_assert(std::is_same<decltype(cit), cpair>::value, + "const equal_range returns pair<const_iterator, const_iterator>"); +} + + +int +main() +{ + test01(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/operations/1.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/operations/1.cc new file mode 100644 index 00000000000..98a1c5b68de --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/operations/1.cc @@ -0,0 +1,135 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-do run { target c++20 } } + +#include <unordered_set> +#include <testsuite_hooks.h> + +struct Equal +{ + typedef void is_transparent; + + bool operator()(int i, long l) const { return i == l; } + bool operator()(long l, int i) const { return l == i; } + bool operator()(int i, int j) const { ++count; return i == j; } + + static int count; +}; + +int Equal::count = 0; + +struct Hash +{ + typedef void is_transparent; + + std::size_t operator()(int i) const { ++count; return i; } + std::size_t operator()(long l) const { return l; } + + static int count; +}; + +int Hash::count = 0; + +using test_type = std::unordered_multiset<int, Hash, Equal>; + +test_type x{ 1, 3, 3, 5 }; +const test_type& cx = x; + +void +test01() +{ + Hash::count = 0; + Equal::count = 0; + + VERIFY( x.contains(1L) ); + + auto it = x.find(1L); + VERIFY( it != x.end() && *it == 1 ); + it = x.find(2L); + VERIFY( it == x.end() ); + + auto cit = cx.find(3L); + VERIFY( cit != cx.end() && *cit == 3 ); + cit = cx.find(2L); + VERIFY( cit == cx.end() ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); + + static_assert(std::is_same<decltype(it), test_type::iterator>::value, + "find returns iterator"); + static_assert(std::is_same<decltype(cit), test_type::const_iterator>::value, + "const find returns const_iterator"); +} + +void +test02() +{ + Hash::count = 0; + Equal::count = 0; + + auto n = x.count(1L); + VERIFY( n == 1 ); + n = x.count(2L); + VERIFY( n == 0 ); + + auto cn = cx.count(3L); + VERIFY( cn == 2 ); + cn = cx.count(2L); + VERIFY( cn == 0 ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); +} + +void +test03() +{ + Hash::count = 0; + Equal::count = 0; + + auto it = x.equal_range(1L); + VERIFY( it.first != it.second && *it.first == 1 ); + it = x.equal_range(2L); + VERIFY( it.first == it.second && it.first == x.end() ); + + auto cit = cx.equal_range(3L); + VERIFY( cit.first != cit.second && *cit.first == 3 ); + VERIFY( std::distance(cit.first, cit.second) == 2 ); + cit = cx.equal_range(2L); + VERIFY( cit.first == cit.second && cit.first == cx.end() ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); + + using pair = std::pair<test_type::iterator, test_type::iterator>; + static_assert(std::is_same<decltype(it), pair>::value, + "equal_range returns pair<iterator, iterator>"); + using cpair = std::pair<test_type::const_iterator, test_type::const_iterator>; + static_assert(std::is_same<decltype(cit), cpair>::value, + "const equal_range returns pair<const_iterator, const_iterator>"); +} + + +int +main() +{ + test01(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/operations/1.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/operations/1.cc new file mode 100644 index 00000000000..3498198ff6e --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/operations/1.cc @@ -0,0 +1,186 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-do run { target c++20 } } + +#include <unordered_set> +#include <testsuite_hooks.h> + +struct Equal +{ + typedef void is_transparent; + + bool operator()(int i, long l) const { return i == l; } + bool operator()(long l, int i) const { return l == i; } + bool operator()(int i, int j) const { ++count; return i == j; } + + static int count; +}; + +int Equal::count = 0; + +struct Hash +{ + typedef void is_transparent; + + std::size_t operator()(int i) const { ++count; return i; } + std::size_t operator()(long l) const { return l; } + + static int count; +}; + +int Hash::count = 0; + +using test_type = std::unordered_set<int, Hash, Equal>; + +test_type x{ 1, 3, 5 }; +const test_type& cx = x; + +void +test01() +{ + Hash::count = 0; + Equal::count = 0; + + VERIFY( x.contains(1L) ); + + auto it = x.find(1L); + VERIFY( it != x.end() && *it == 1 ); + it = x.find(2L); + VERIFY( it == x.end() ); + + auto cit = cx.find(3L); + VERIFY( cit != cx.end() && *cit == 3 ); + cit = cx.find(2L); + VERIFY( cit == cx.end() ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); + + static_assert(std::is_same<decltype(it), test_type::iterator>::value, + "find returns iterator"); + static_assert(std::is_same<decltype(cit), test_type::const_iterator>::value, + "const find returns const_iterator"); +} + +void +test02() +{ + Hash::count = 0; + Equal::count = 0; + + auto n = x.count(1L); + VERIFY( n == 1 ); + n = x.count(2L); + VERIFY( n == 0 ); + + auto cn = cx.count(3L); + VERIFY( cn == 1 ); + cn = cx.count(2L); + VERIFY( cn == 0 ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); +} + +void +test03() +{ + Hash::count = 0; + Equal::count = 0; + + auto it = x.equal_range(1L); + VERIFY( it.first != it.second && *it.first == 1 ); + it = x.equal_range(2L); + VERIFY( it.first == it.second && it.first == x.end() ); + + auto cit = cx.equal_range(1L); + VERIFY( cit.first != cit.second && *cit.first == 1 ); + cit = cx.equal_range(2L); + VERIFY( cit.first == cit.second && cit.first == cx.end() ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); + + using pair = std::pair<test_type::iterator, test_type::iterator>; + static_assert(std::is_same<decltype(it), pair>::value, + "equal_range returns pair<iterator, iterator>"); + using cpair = std::pair<test_type::const_iterator, test_type::const_iterator>; + static_assert(std::is_same<decltype(cit), cpair>::value, + "const equal_range returns pair<const_iterator, const_iterator>"); +} + +void +test04() +{ + // https://gcc.gnu.org/ml/libstdc++/2015-01/msg00176.html + // Verify the new function template overloads do not cause problems + // when the comparison function is not transparent. + struct I + { + int i; + operator int() const { return i; } + }; + + std::unordered_set<int> s; + I i = { }; + s.find(i); +} + +void +test05() +{ + struct E + { + bool operator()(int l, int r) const { return l == r; } + + struct Partition { }; + + bool operator()(int l, Partition) const { return l < 6; } + bool operator()(Partition, int r) const { return r > 3; } + + using is_transparent = void; + }; + + struct H + { + size_t + operator()(int x) const + { return (size_t)(x / 10); } + + size_t + operator()(E::Partition) const + { return 0; } + + using is_transparent = void; + }; + + std::unordered_set<int, H, E> s{ 1, 2, 3, 4, 5 }; + + auto n = s.count(E::Partition{}); + VERIFY( n == 2 ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); + test05(); +} ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] Add unordered containers heterogeneous lookup 2020-12-01 7:19 [PATCH] Add unordered containers heterogeneous lookup François Dumont @ 2021-01-25 18:21 ` François Dumont 2021-02-03 11:23 ` Jonathan Wakely 0 siblings, 1 reply; 6+ messages in thread From: François Dumont @ 2021-01-25 18:21 UTC (permalink / raw) To: libstdc++, gcc-patches 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 > ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] Add unordered containers heterogeneous lookup 2021-01-25 18:21 ` François Dumont @ 2021-02-03 11:23 ` Jonathan Wakely 2021-02-03 11:24 ` Jonathan Wakely 0 siblings, 1 reply; 6+ messages in thread From: Jonathan Wakely @ 2021-02-03 11:23 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches 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 >> > ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] Add unordered containers heterogeneous lookup 2021-02-03 11:23 ` Jonathan Wakely @ 2021-02-03 11:24 ` Jonathan Wakely 2021-02-04 20:20 ` François Dumont 0 siblings, 1 reply; 6+ messages in thread From: Jonathan Wakely @ 2021-02-03 11:24 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches On 03/02/21 11:23 +0000, 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. ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] Add unordered containers heterogeneous lookup 2021-02-03 11:24 ` Jonathan Wakely @ 2021-02-04 20:20 ` François Dumont 2021-02-09 11:18 ` Jonathan Wakely 0 siblings, 1 reply; 6+ messages in thread From: François Dumont @ 2021-02-04 20:20 UTC (permalink / raw) To: Jonathan Wakely; +Cc: libstdc++, gcc-patches [-- Attachment #1: Type: text/plain, Size: 3996 bytes --] 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 +0000, 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. > [-- Attachment #2: heterogenous_lookup.patch --] [-- Type: text/x-patch, Size: 46427 bytes --] 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<const_iterator, const_iterator> equal_range(const key_type& __k) const; +#if __cplusplus > 201702L + template<typename _Kt, + typename = __has_is_transparent_t<_Hash, _Kt>, + typename = __has_is_transparent_t<_Equal, _Kt>> + iterator + _M_find_tr(const _Kt& __k); + + template<typename _Kt, + typename = __has_is_transparent_t<_Hash, _Kt>, + typename = __has_is_transparent_t<_Equal, _Kt>> + const_iterator + _M_find_tr(const _Kt& __k) const; + + template<typename _Kt, + typename = __has_is_transparent_t<_Hash, _Kt>, + typename = __has_is_transparent_t<_Equal, _Kt>> + size_type + _M_count_tr(const _Kt& __k) const; + + template<typename _Kt, + typename = __has_is_transparent_t<_Hash, _Kt>, + typename = __has_is_transparent_t<_Equal, _Kt>> + pair<iterator, iterator> + _M_equal_range_tr(const _Kt& __k); + + template<typename _Kt, + typename = __has_is_transparent_t<_Hash, _Kt>, + typename = __has_is_transparent_t<_Equal, _Kt>> + pair<const_iterator, const_iterator> + _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<typename _Kt> + __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, __hash_code __c) const @@ -749,6 +785,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return nullptr; } + template<typename _Kt> + __node_ptr + _M_find_node_tr(size_type __bkt, const _Kt& __key, + __hash_code __c) const + { + auto __before_n = _M_find_before_node_tr(__bkt, __key, __c); + if (__before_n) + return static_cast<__node_ptr>(__before_n->_M_nxt); + return nullptr; + } + // Insert a node at the beginning of a bucket. void _M_insert_bucket_begin(size_type, __node_ptr); @@ -1532,6 +1579,40 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return const_iterator(_M_find_node(__bkt, __k, __code)); } +#if __cplusplus > 201703L + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> + template<typename _Kt, typename, typename> + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_find_tr(const _Kt& __k) + -> iterator + { + __hash_code __code = this->_M_hash_code_tr(__k); + std::size_t __bkt = _M_bucket_index(__code); + return iterator(_M_find_node_tr(__bkt, __k, __code)); + } + + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> + template<typename _Kt, typename, typename> + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_find_tr(const _Kt& __k) const + -> const_iterator + { + __hash_code __code = this->_M_hash_code_tr(__k); + std::size_t __bkt = _M_bucket_index(__code); + return const_iterator(_M_find_node_tr(__bkt, __k, __code)); + } +#endif + template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, typename _Hash, typename _RangeHash, typename _Unused, @@ -1561,6 +1642,38 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return __result; } +#if __cplusplus > 201703L + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> + template<typename _Kt, typename, typename> + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_count_tr(const _Kt& __k) const + -> size_type + { + __hash_code __code = this->_M_hash_code_tr(__k); + std::size_t __bkt = _M_bucket_index(__code); + auto __n = _M_find_node_tr(__bkt, __k, __code); + if (!__n) + return 0; + + // All equivalent values are next to each other, if we find a + // non-equivalent value after an equivalent one it means that we won't + // find any new equivalent value. + iterator __it(__n); + size_type __result = 1; + for (++__it; + __it._M_cur && this->_M_equals_tr(__k, __code, *__it._M_cur); + ++__it) + ++__result; + + return __result; + } +#endif + template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, typename _Hash, typename _RangeHash, typename _Unused, @@ -1615,6 +1728,64 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return { __beg, __ite }; } +#if __cplusplus > 201703L + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> + template<typename _Kt, typename, typename> + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_equal_range_tr(const _Kt& __k) + -> pair<iterator, iterator> + { + __hash_code __code = this->_M_hash_code_tr(__k); + std::size_t __bkt = _M_bucket_index(__code); + auto __n = _M_find_node_tr(__bkt, __k, __code); + iterator __ite(__n); + if (!__n) + return { __ite, __ite }; + + // All equivalent values are next to each other, if we find a + // non-equivalent value after an equivalent one it means that we won't + // find any new equivalent value. + auto __beg = __ite++; + while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur)) + ++__ite; + + return { __beg, __ite }; + } + + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> + template<typename _Kt, typename, typename> + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_equal_range_tr(const _Kt& __k) const + -> pair<const_iterator, const_iterator> + { + __hash_code __code = this->_M_hash_code_tr(__k); + std::size_t __bkt = _M_bucket_index(__code); + auto __n = _M_find_node_tr(__bkt, __k, __code); + const_iterator __ite(__n); + if (!__n) + return { __ite, __ite }; + + // All equivalent values are next to each other, if we find a + // non-equivalent value after an equivalent one it means that we won't + // find any new equivalent value. + auto __beg = __ite++; + while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur)) + ++__ite; + + return { __beg, __ite }; + } +#endif + // Find the node before the one whose key compares equal to k in the bucket // bkt. Return nullptr if no node is found. template<typename _Key, typename _Value, typename _Alloc, @@ -1646,6 +1817,36 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return nullptr; } + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _Hash, typename _RangeHash, typename _Unused, + typename _RehashPolicy, typename _Traits> + template<typename _Kt> + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_find_before_node_tr(size_type __bkt, const _Kt& __k, + __hash_code __code) const + -> __node_base_ptr + { + __node_base_ptr __prev_p = _M_buckets[__bkt]; + if (!__prev_p) + return nullptr; + + for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);; + __p = __p->_M_next()) + { + if (this->_M_equals_tr(__k, __code, *__p)) + return __prev_p; + + if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt) + break; + __prev_p = __p; + } + + return nullptr; + } + template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, typename _Hash, typename _RangeHash, typename _Unused, diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index 999147a68d4..90797f8dbda 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -1217,6 +1217,15 @@ namespace __detail return _M_hash()(__k); } + template<typename _Kt> + __hash_code + _M_hash_code_tr(const _Kt& __k) const + { + static_assert(__is_invocable<const _Hash&, const _Kt&>{}, + "hash function must be invocable with an argument of key type"); + return _M_hash()(__k); + } + std::size_t _M_bucket_index(__hash_code __c, std::size_t __bkt_count) const { return _RangeHash{}(__c, __bkt_count); } @@ -1605,6 +1614,19 @@ namespace __detail return _S_equals(__c, __n) && _M_eq()(__k, _ExtractKey{}(__n._M_v())); } + template<typename _Kt> + bool + _M_equals_tr(const _Kt& __k, __hash_code __c, + const _Hash_node_value<_Value, + __hash_cached::value>& __n) const + { + static_assert( + __is_invocable<const _Equal&, const _Kt&, const _Key&>{}, + "key equality predicate must be invocable with two arguments of " + "key type"); + return _S_equals(__c, __n) && _M_eq()(__k, _ExtractKey{}(__n._M_v())); + } + bool _M_node_equals( const _Hash_node_value<_Value, __hash_cached::value>& __lhn, diff --git a/libstdc++-v3/include/bits/stl_function.h b/libstdc++-v3/include/bits/stl_function.h index dac005d7e2b..073018d522d 100644 --- a/libstdc++-v3/include/bits/stl_function.h +++ b/libstdc++-v3/include/bits/stl_function.h @@ -1385,6 +1385,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION /** @} */ +#if __cplusplus >= 201402L + template<typename _Func, typename _SfinaeType, typename = __void_t<>> + struct __has_is_transparent + { }; + + template<typename _Func, typename _SfinaeType> + struct __has_is_transparent<_Func, _SfinaeType, + __void_t<typename _Func::is_transparent>> + { typedef void type; }; + + template<typename _Func, typename _SfinaeType> + using __has_is_transparent_t + = typename __has_is_transparent<_Func, _SfinaeType>::type; +#endif + _GLIBCXX_END_NAMESPACE_VERSION } // namespace diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h index a75591db7b1..550195a2749 100644 --- a/libstdc++-v3/include/bits/stl_tree.h +++ b/libstdc++-v3/include/bits/stl_tree.h @@ -415,21 +415,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, _Rb_tree_node_base& __header) throw (); -#if __cplusplus >= 201402L - template<typename _Cmp, typename _SfinaeType, typename = __void_t<>> - struct __has_is_transparent - { }; - - template<typename _Cmp, typename _SfinaeType> - struct __has_is_transparent<_Cmp, _SfinaeType, - __void_t<typename _Cmp::is_transparent>> - { typedef void type; }; - - template<typename _Cmp, typename _SfinaeType> - using __has_is_transparent_t - = typename __has_is_transparent<_Cmp, _SfinaeType>::type; -#endif - #if __cplusplus > 201402L template<typename _Tree1, typename _Cmp2> struct _Rb_tree_merge_helper { }; diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h index 70ce6ab2aee..d617d2d923d 100644 --- a/libstdc++-v3/include/bits/unordered_map.h +++ b/libstdc++-v3/include/bits/unordered_map.h @@ -868,11 +868,26 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER find(const key_type& __x) { return _M_h.find(__x); } +#if __cplusplus > 201703L + template<typename _Kt> + auto + find(const _Kt& __x) -> decltype(_M_h._M_find_tr(__x)) + { return _M_h._M_find_tr(__x); } +#endif + const_iterator find(const key_type& __x) const { return _M_h.find(__x); } + +#if __cplusplus > 201703L + template<typename _Kt> + auto + find(const _Kt& __x) const -> decltype(_M_h._M_find_tr(__x)) + { return _M_h._M_find_tr(__x); } +#endif //@} + //@{ /** * @brief Finds the number of elements. * @param __x Key to count. @@ -887,6 +902,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return _M_h.count(__x); } #if __cplusplus > 201703L + template<typename _Kt> + auto + count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x)) + { return _M_h._M_count_tr(__x); } +#endif + //@} + +#if __cplusplus > 201703L + //@{ /** * @brief Finds whether an element with the given key exists. * @param __x Key of elements to be located. @@ -895,6 +919,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER bool contains(const key_type& __x) const { return _M_h.find(__x) != _M_h.end(); } + + template<typename _Kt> + auto + contains(const _Kt& __x) const + -> decltype(_M_h._M_find_tr(__x), void(), true) + { return _M_h._M_find_tr(__x) != _M_h.end(); } + //@} #endif //@{ @@ -910,9 +941,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER equal_range(const key_type& __x) { return _M_h.equal_range(__x); } +#if __cplusplus > 201703L + template<typename _Kt> + auto + equal_range(const _Kt& __x) + -> decltype(_M_h._M_equal_range_tr(__x)) + { return _M_h._M_equal_range_tr(__x); } +#endif + std::pair<const_iterator, const_iterator> equal_range(const key_type& __x) const { return _M_h.equal_range(__x); } + +#if __cplusplus > 201703L + template<typename _Kt> + auto + equal_range(const _Kt& __x) const + -> decltype(_M_h._M_equal_range_tr(__x)) + { return _M_h._M_equal_range_tr(__x); } +#endif //@} //@{ @@ -1764,11 +1811,26 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER find(const key_type& __x) { return _M_h.find(__x); } +#if __cplusplus > 201703L + template<typename _Kt> + auto + find(const _Kt& __x) -> decltype(_M_h._M_find_tr(__x)) + { return _M_h._M_find_tr(__x); } +#endif + const_iterator find(const key_type& __x) const { return _M_h.find(__x); } + +#if __cplusplus > 201703L + template<typename _Kt> + auto + find(const _Kt& __x) const -> decltype(_M_h._M_find_tr(__x)) + { return _M_h._M_find_tr(__x); } +#endif //@} + //@{ /** * @brief Finds the number of elements. * @param __x Key to count. @@ -1779,6 +1841,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return _M_h.count(__x); } #if __cplusplus > 201703L + template<typename _Kt> + auto + count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x)) + { return _M_h._M_count_tr(__x); } +#endif + //@} + +#if __cplusplus > 201703L + //@{ /** * @brief Finds whether an element with the given key exists. * @param __x Key of elements to be located. @@ -1787,6 +1858,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER bool contains(const key_type& __x) const { return _M_h.find(__x) != _M_h.end(); } + + template<typename _Kt> + auto + contains(const _Kt& __x) const + -> decltype(_M_h._M_find_tr(__x), void(), true) + { return _M_h._M_find_tr(__x) != _M_h.end(); } + //@} #endif //@{ @@ -1800,9 +1878,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER equal_range(const key_type& __x) { return _M_h.equal_range(__x); } +#if __cplusplus > 201703L + template<typename _Kt> + auto + equal_range(const _Kt& __x) + -> decltype(_M_h._M_equal_range_tr(__x)) + { return _M_h._M_equal_range_tr(__x); } +#endif + std::pair<const_iterator, const_iterator> equal_range(const key_type& __x) const { return _M_h.equal_range(__x); } + +#if __cplusplus > 201703L + template<typename _Kt> + auto + equal_range(const _Kt& __x) const + -> decltype(_M_h._M_equal_range_tr(__x)) + { return _M_h._M_equal_range_tr(__x); } +#endif //@} // bucket interface. diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h index 5bc31a2910e..63c1a7efd8a 100644 --- a/libstdc++-v3/include/bits/unordered_set.h +++ b/libstdc++-v3/include/bits/unordered_set.h @@ -650,11 +650,28 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER find(const key_type& __x) { return _M_h.find(__x); } +#if __cplusplus > 201703L + template<typename _Kt> + auto + find(const _Kt& __k) + -> decltype(_M_h._M_find_tr(__k)) + { return _M_h._M_find_tr(__k); } +#endif + const_iterator find(const key_type& __x) const { return _M_h.find(__x); } + +#if __cplusplus > 201703L + template<typename _Kt> + auto + find(const _Kt& __k) const + -> decltype(_M_h._M_find_tr(__k)) + { return _M_h._M_find_tr(__k); } +#endif //@} + //@{ /** * @brief Finds the number of elements. * @param __x Element to located. @@ -669,6 +686,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return _M_h.count(__x); } #if __cplusplus > 201703L + template<typename _Kt> + auto + count(const _Kt& __k) const + -> decltype(_M_h._M_count_tr(__k)) + { return _M_h._M_count_tr(__k); } +#endif + //@} + +#if __cplusplus > 201703L + //@{ /** * @brief Finds whether an element with the given key exists. * @param __x Key of elements to be located. @@ -677,6 +704,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER bool contains(const key_type& __x) const { return _M_h.find(__x) != _M_h.end(); } + + template<typename _Kt> + auto + contains(const _Kt& __k) const + -> decltype(_M_h._M_find_tr(__k), void(), true) + { return _M_h._M_find_tr(__k) != _M_h.end(); } + //@} #endif //@{ @@ -692,9 +726,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER equal_range(const key_type& __x) { return _M_h.equal_range(__x); } +#if __cplusplus > 201703L + template<typename _Kt> + auto + equal_range(const _Kt& __k) + -> decltype(_M_h._M_equal_range_tr(__k)) + { return _M_h._M_equal_range_tr(__k); } +#endif + std::pair<const_iterator, const_iterator> equal_range(const key_type& __x) const { return _M_h.equal_range(__x); } + +#if __cplusplus > 201703L + template<typename _Kt> + auto + equal_range(const _Kt& __k) const + -> decltype(_M_h._M_equal_range_tr(__k)) + { return _M_h._M_equal_range_tr(__k); } +#endif //@} // bucket interface. @@ -1450,11 +1500,28 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER find(const key_type& __x) { return _M_h.find(__x); } +#if __cplusplus > 201703L + template<typename _Kt> + auto + find(const _Kt& __x) + -> decltype(_M_h._M_find_tr(__x)) + { return _M_h._M_find_tr(__x); } +#endif + const_iterator find(const key_type& __x) const { return _M_h.find(__x); } + +#if __cplusplus > 201703L + template<typename _Kt> + auto + find(const _Kt& __x) const + -> decltype(_M_h._M_find_tr(__x)) + { return _M_h._M_find_tr(__x); } +#endif //@} + //@{ /** * @brief Finds the number of elements. * @param __x Element to located. @@ -1465,6 +1532,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return _M_h.count(__x); } #if __cplusplus > 201703L + template<typename _Kt> + auto + count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x)) + { return _M_h._M_count_tr(__x); } +#endif + //@} + +#if __cplusplus > 201703L + //@{ /** * @brief Finds whether an element with the given key exists. * @param __x Key of elements to be located. @@ -1473,6 +1549,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER bool contains(const key_type& __x) const { return _M_h.find(__x) != _M_h.end(); } + + template<typename _Kt> + auto + contains(const _Kt& __x) const + -> decltype(_M_h._M_find_tr(__x), void(), true) + { return _M_h._M_find_tr(__x) != _M_h.end(); } + //@} #endif //@{ @@ -1486,9 +1569,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER equal_range(const key_type& __x) { return _M_h.equal_range(__x); } +#if __cplusplus > 201703L + template<typename _Kt> + auto + equal_range(const _Kt& __x) + -> decltype(_M_h._M_equal_range_tr(__x)) + { return _M_h._M_equal_range_tr(__x); } +#endif + std::pair<const_iterator, const_iterator> equal_range(const key_type& __x) const { return _M_h.equal_range(__x); } + +#if __cplusplus > 201703L + template<typename _Kt> + auto + equal_range(const _Kt& __x) const + -> decltype(_M_h._M_equal_range_tr(__x)) + { return _M_h._M_equal_range_tr(__x); } +#endif //@} // bucket interface. diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map index 7e71f298df9..bb697d364ea 100644 --- a/libstdc++-v3/include/debug/unordered_map +++ b/libstdc++-v3/include/debug/unordered_map @@ -545,10 +545,28 @@ namespace __debug find(const key_type& __key) { return { _Base::find(__key), this }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + iterator + find(const _Kt& __k) + { return { _Base::find(__k), this }; } +#endif + const_iterator find(const key_type& __key) const { return { _Base::find(__key), this }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + const_iterator + find(const _Kt& __k) const + { return { _Base::find(__k), this }; } +#endif + std::pair<iterator, iterator> equal_range(const key_type& __key) { @@ -556,6 +574,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair<iterator, iterator> + equal_range(const _Kt& __k) + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + std::pair<const_iterator, const_iterator> equal_range(const key_type& __key) const { @@ -563,6 +593,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair<const_iterator, const_iterator> + equal_range(const _Kt& __k) const + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + size_type erase(const key_type& __key) { @@ -1157,10 +1199,28 @@ namespace __debug find(const key_type& __key) { return { _Base::find(__key), this }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + iterator + find(const _Kt& __k) + { return { _Base::find(__k), this }; } +#endif + const_iterator find(const key_type& __key) const { return { _Base::find(__key), this }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + const_iterator + find(const _Kt& __k) const + { return { _Base::find(__k), this }; } +#endif + std::pair<iterator, iterator> equal_range(const key_type& __key) { @@ -1168,6 +1228,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair<iterator, iterator> + equal_range(const _Kt& __k) + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + std::pair<const_iterator, const_iterator> equal_range(const key_type& __key) const { @@ -1175,6 +1247,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair<const_iterator, const_iterator> + equal_range(const _Kt& __k) const + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + size_type erase(const key_type& __key) { diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set index 39198a8b575..c25910946b7 100644 --- a/libstdc++-v3/include/debug/unordered_set +++ b/libstdc++-v3/include/debug/unordered_set @@ -430,10 +430,28 @@ namespace __debug find(const key_type& __key) { return { _Base::find(__key), this }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + iterator + find(const _Kt& __k) + { return { _Base::find(__k), this }; } +#endif + const_iterator find(const key_type& __key) const { return { _Base::find(__key), this }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + const_iterator + find(const _Kt& __k) const + { return { _Base::find(__k), this }; } +#endif + std::pair<iterator, iterator> equal_range(const key_type& __key) { @@ -441,6 +459,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair<iterator, iterator> + equal_range(const _Kt& __k) + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + std::pair<const_iterator, const_iterator> equal_range(const key_type& __key) const { @@ -448,6 +478,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair<const_iterator, const_iterator> + equal_range(const _Kt& __k) const + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + size_type erase(const key_type& __key) { @@ -1002,10 +1044,28 @@ namespace __debug find(const key_type& __key) { return { _Base::find(__key), this }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + iterator + find(const _Kt& __k) + { return { _Base::find(__k), this }; } +#endif + const_iterator find(const key_type& __key) const { return { _Base::find(__key), this }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + const_iterator + find(const _Kt& __k) const + { return { _Base::find(__k), this }; } +#endif + std::pair<iterator, iterator> equal_range(const key_type& __key) { @@ -1013,6 +1073,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair<iterator, iterator> + equal_range(const _Kt& __k) + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + std::pair<const_iterator, const_iterator> equal_range(const key_type& __key) const { @@ -1020,6 +1092,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template<typename _Kt, + typename = std::__has_is_transparent_t<_Hash, _Kt>, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair<const_iterator, const_iterator> + equal_range(const _Kt& __k) const + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + size_type erase(const key_type& __key) { diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/operations/1.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/operations/1.cc new file mode 100644 index 00000000000..4f2df728ebb --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/operations/1.cc @@ -0,0 +1,168 @@ +// Copyright (C) 2021 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-do run { target c++20 } } + +#include <unordered_map> +#include <testsuite_hooks.h> + +struct Equal +{ + typedef void is_transparent; + + bool operator()(int i, long l) const { return i == l; } + bool operator()(long l, int i) const { return l == i; } + bool operator()(int i, int j) const { ++count; return i == j; } + + static int count; +}; + +int Equal::count = 0; + +struct Hash +{ + typedef void is_transparent; + + std::size_t operator()(int i) const { ++count; return i; } + std::size_t operator()(long l) const { return l; } + + static int count; +}; + +int Hash::count = 0; + +using test_type = std::unordered_map<int, char, Hash, Equal>; + +test_type x{ { 1, '2' }, { 3, '4' } }; +const test_type& cx = x; + +void +test01() +{ + Hash::count = 0; + Equal::count = 0; + + VERIFY( x.contains(1L) ); + + auto it = x.find(1L); + VERIFY( it != x.end() && it->second == '2' ); + it = x.find(2L); + VERIFY( it == x.end() ); + + auto cit = cx.find(3L); + VERIFY( cit != cx.end() && cit->second == '4' ); + cit = cx.find(2L); + VERIFY( cit == cx.end() ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); + + static_assert(std::is_same<decltype(it), test_type::iterator>::value, + "find returns iterator"); + static_assert(std::is_same<decltype(cit), test_type::const_iterator>::value, + "const find returns const_iterator"); +} + +void +test02() +{ + Hash::count = 0; + Equal::count = 0; + + auto n = x.count(1L); + VERIFY( n == 1 ); + n = x.count(2L); + VERIFY( n == 0 ); + + auto cn = cx.count(3L); + VERIFY( cn == 1 ); + cn = cx.count(2L); + VERIFY( cn == 0 ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); +} + +void +test03() +{ + Hash::count = 0; + Equal::count = 0; + + auto it = x.equal_range(1L); + VERIFY( it.first != it.second && it.first->second == '2' ); + it = x.equal_range(2L); + VERIFY( it.first == it.second && it.first == x.end() ); + + auto cit = cx.equal_range(1L); + VERIFY( cit.first != cit.second && cit.first->second == '2' ); + cit = cx.equal_range(2L); + VERIFY( cit.first == cit.second && cit.first == cx.end() ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); + + using pair = std::pair<test_type::iterator, test_type::iterator>; + static_assert(std::is_same<decltype(it), pair>::value, + "equal_range returns pair<iterator, iterator>"); + using cpair = std::pair<test_type::const_iterator, test_type::const_iterator>; + static_assert(std::is_same<decltype(cit), cpair>::value, + "const equal_range returns pair<const_iterator, const_iterator>"); +} + +void +test04() +{ + struct E + { + bool operator()(int l, int r) const { return l == r; } + + struct Partition { }; + + bool operator()(int l, Partition) const { return l < 6; } + bool operator()(Partition, int r) const { return 3 < r; } + + using is_transparent = void; + }; + + struct H + { + size_t + operator()(int x) const + { return 0; } + + size_t + operator()(E::Partition) const + { return 0; } + + using is_transparent = void; + }; + + std::unordered_map<int, int, H, E> m{ {1,0}, {2,0}, {3,0}, {4, 0}, {5, 0} }; + + auto n = m.count(E::Partition{}); + VERIFY( n == 2 ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/operations/1.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/operations/1.cc new file mode 100644 index 00000000000..16940db559d --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/operations/1.cc @@ -0,0 +1,135 @@ +// Copyright (C) 2021 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-do run { target c++20 } } + +#include <unordered_map> +#include <testsuite_hooks.h> + +struct Equal +{ + typedef void is_transparent; + + bool operator()(int i, long l) const { return i == l; } + bool operator()(long l, int i) const { return l == i; } + bool operator()(int i, int j) const { ++count; return i == j; } + + static int count; +}; + +int Equal::count = 0; + +struct Hash +{ + typedef void is_transparent; + + std::size_t operator()(int i) const { ++count; return i; } + std::size_t operator()(long l) const { return l; } + + static int count; +}; + +int Hash::count = 0; + +using test_type = std::unordered_multimap<int, char, Hash, Equal>; + +test_type x{ { 1, '2' }, { 3, '4' }, { 3, '5' } }; +const test_type& cx = x; + +void +test01() +{ + Hash::count = 0; + Equal::count = 0; + + VERIFY( x.contains(1L) ); + + auto it = x.find(1L); + VERIFY( it != x.end() && it->second == '2' ); + it = x.find(2L); + VERIFY( it == x.end() ); + + auto cit = cx.find(3L); + VERIFY( cit != cx.end() && cit->second == '5' ); + cit = cx.find(2L); + VERIFY( cit == cx.end() ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); + + static_assert(std::is_same<decltype(it), test_type::iterator>::value, + "find returns iterator"); + static_assert(std::is_same<decltype(cit), test_type::const_iterator>::value, + "const find returns const_iterator"); +} + +void +test02() +{ + Hash::count = 0; + Equal::count = 0; + + auto n = x.count(1L); + VERIFY( n == 1 ); + n = x.count(2L); + VERIFY( n == 0 ); + + auto cn = cx.count(3L); + VERIFY( cn == 2 ); + cn = cx.count(2L); + VERIFY( cn == 0 ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); +} + +void +test03() +{ + Hash::count = 0; + Equal::count = 0; + + auto it = x.equal_range(1L); + VERIFY( it.first != it.second && it.first->second == '2' ); + it = x.equal_range(2L); + VERIFY( it.first == it.second && it.first == x.end() ); + + auto cit = cx.equal_range(3L); + VERIFY( cit.first != cit.second && cit.first->second == '5' ); + VERIFY( std::distance(cit.first, cit.second) == 2 ); + cit = cx.equal_range(2L); + VERIFY( cit.first == cit.second && cit.first == cx.end() ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); + + using pair = std::pair<test_type::iterator, test_type::iterator>; + static_assert(std::is_same<decltype(it), pair>::value, + "equal_range returns pair<iterator, iterator>"); + using cpair = std::pair<test_type::const_iterator, test_type::const_iterator>; + static_assert(std::is_same<decltype(cit), cpair>::value, + "const equal_range returns pair<const_iterator, const_iterator>"); +} + + +int +main() +{ + test01(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/operations/1.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/operations/1.cc new file mode 100644 index 00000000000..81b82fc1307 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/operations/1.cc @@ -0,0 +1,135 @@ +// Copyright (C) 2021 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-do run { target c++20 } } + +#include <unordered_set> +#include <testsuite_hooks.h> + +struct Equal +{ + typedef void is_transparent; + + bool operator()(int i, long l) const { return i == l; } + bool operator()(long l, int i) const { return l == i; } + bool operator()(int i, int j) const { ++count; return i == j; } + + static int count; +}; + +int Equal::count = 0; + +struct Hash +{ + typedef void is_transparent; + + std::size_t operator()(int i) const { ++count; return i; } + std::size_t operator()(long l) const { return l; } + + static int count; +}; + +int Hash::count = 0; + +using test_type = std::unordered_multiset<int, Hash, Equal>; + +test_type x{ 1, 3, 3, 5 }; +const test_type& cx = x; + +void +test01() +{ + Hash::count = 0; + Equal::count = 0; + + VERIFY( x.contains(1L) ); + + auto it = x.find(1L); + VERIFY( it != x.end() && *it == 1 ); + it = x.find(2L); + VERIFY( it == x.end() ); + + auto cit = cx.find(3L); + VERIFY( cit != cx.end() && *cit == 3 ); + cit = cx.find(2L); + VERIFY( cit == cx.end() ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); + + static_assert(std::is_same<decltype(it), test_type::iterator>::value, + "find returns iterator"); + static_assert(std::is_same<decltype(cit), test_type::const_iterator>::value, + "const find returns const_iterator"); +} + +void +test02() +{ + Hash::count = 0; + Equal::count = 0; + + auto n = x.count(1L); + VERIFY( n == 1 ); + n = x.count(2L); + VERIFY( n == 0 ); + + auto cn = cx.count(3L); + VERIFY( cn == 2 ); + cn = cx.count(2L); + VERIFY( cn == 0 ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); +} + +void +test03() +{ + Hash::count = 0; + Equal::count = 0; + + auto it = x.equal_range(1L); + VERIFY( it.first != it.second && *it.first == 1 ); + it = x.equal_range(2L); + VERIFY( it.first == it.second && it.first == x.end() ); + + auto cit = cx.equal_range(3L); + VERIFY( cit.first != cit.second && *cit.first == 3 ); + VERIFY( std::distance(cit.first, cit.second) == 2 ); + cit = cx.equal_range(2L); + VERIFY( cit.first == cit.second && cit.first == cx.end() ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); + + using pair = std::pair<test_type::iterator, test_type::iterator>; + static_assert(std::is_same<decltype(it), pair>::value, + "equal_range returns pair<iterator, iterator>"); + using cpair = std::pair<test_type::const_iterator, test_type::const_iterator>; + static_assert(std::is_same<decltype(cit), cpair>::value, + "const equal_range returns pair<const_iterator, const_iterator>"); +} + + +int +main() +{ + test01(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/operations/1.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/operations/1.cc new file mode 100644 index 00000000000..34414d2434a --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/operations/1.cc @@ -0,0 +1,186 @@ +// Copyright (C) 2021 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-do run { target c++20 } } + +#include <unordered_set> +#include <testsuite_hooks.h> + +struct Equal +{ + typedef void is_transparent; + + bool operator()(int i, long l) const { return i == l; } + bool operator()(long l, int i) const { return l == i; } + bool operator()(int i, int j) const { ++count; return i == j; } + + static int count; +}; + +int Equal::count = 0; + +struct Hash +{ + typedef void is_transparent; + + std::size_t operator()(int i) const { ++count; return i; } + std::size_t operator()(long l) const { return l; } + + static int count; +}; + +int Hash::count = 0; + +using test_type = std::unordered_set<int, Hash, Equal>; + +test_type x{ 1, 3, 5 }; +const test_type& cx = x; + +void +test01() +{ + Hash::count = 0; + Equal::count = 0; + + VERIFY( x.contains(1L) ); + + auto it = x.find(1L); + VERIFY( it != x.end() && *it == 1 ); + it = x.find(2L); + VERIFY( it == x.end() ); + + auto cit = cx.find(3L); + VERIFY( cit != cx.end() && *cit == 3 ); + cit = cx.find(2L); + VERIFY( cit == cx.end() ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); + + static_assert(std::is_same<decltype(it), test_type::iterator>::value, + "find returns iterator"); + static_assert(std::is_same<decltype(cit), test_type::const_iterator>::value, + "const find returns const_iterator"); +} + +void +test02() +{ + Hash::count = 0; + Equal::count = 0; + + auto n = x.count(1L); + VERIFY( n == 1 ); + n = x.count(2L); + VERIFY( n == 0 ); + + auto cn = cx.count(3L); + VERIFY( cn == 1 ); + cn = cx.count(2L); + VERIFY( cn == 0 ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); +} + +void +test03() +{ + Hash::count = 0; + Equal::count = 0; + + auto it = x.equal_range(1L); + VERIFY( it.first != it.second && *it.first == 1 ); + it = x.equal_range(2L); + VERIFY( it.first == it.second && it.first == x.end() ); + + auto cit = cx.equal_range(1L); + VERIFY( cit.first != cit.second && *cit.first == 1 ); + cit = cx.equal_range(2L); + VERIFY( cit.first == cit.second && cit.first == cx.end() ); + + VERIFY( Hash::count == 0 ); + VERIFY( Equal::count == 0 ); + + using pair = std::pair<test_type::iterator, test_type::iterator>; + static_assert(std::is_same<decltype(it), pair>::value, + "equal_range returns pair<iterator, iterator>"); + using cpair = std::pair<test_type::const_iterator, test_type::const_iterator>; + static_assert(std::is_same<decltype(cit), cpair>::value, + "const equal_range returns pair<const_iterator, const_iterator>"); +} + +void +test04() +{ + // https://gcc.gnu.org/ml/libstdc++/2015-01/msg00176.html + // Verify the new function template overloads do not cause problems + // when the comparison function is not transparent. + struct I + { + int i; + operator int() const { return i; } + }; + + std::unordered_set<int> s; + I i = { }; + s.find(i); +} + +void +test05() +{ + struct E + { + bool operator()(int l, int r) const { return l == r; } + + struct Partition { }; + + bool operator()(int l, Partition) const { return l < 6; } + bool operator()(Partition, int r) const { return r > 3; } + + using is_transparent = void; + }; + + struct H + { + size_t + operator()(int x) const + { return (size_t)(x / 10); } + + size_t + operator()(E::Partition) const + { return 0; } + + using is_transparent = void; + }; + + std::unordered_set<int, H, E> s{ 1, 2, 3, 4, 5 }; + + auto n = s.count(E::Partition{}); + VERIFY( n == 2 ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); + test05(); +} ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] Add unordered containers heterogeneous lookup 2021-02-04 20:20 ` François Dumont @ 2021-02-09 11:18 ` Jonathan Wakely 0 siblings, 0 replies; 6+ messages in thread From: Jonathan Wakely @ 2021-02-09 11:18 UTC (permalink / raw) To: François Dumont; +Cc: libstdc++, gcc-patches 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. ^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2021-02-09 11:18 UTC | newest] Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2020-12-01 7:19 [PATCH] Add unordered containers heterogeneous lookup François Dumont 2021-01-25 18:21 ` François Dumont 2021-02-03 11:23 ` Jonathan Wakely 2021-02-03 11:24 ` Jonathan Wakely 2021-02-04 20:20 ` François Dumont 2021-02-09 11:18 ` Jonathan Wakely
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).