From d2b1a6842c35c6e790a61291ca1a6aad3333a523 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Fran=C3=A7ois=20Dumont?= Date: Mon, 30 Nov 2020 20:57:16 +0100 Subject: [PATCH] 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. --- libstdc++-v3/include/bits/hashtable.h | 201 +++++++++++++++++++++ libstdc++-v3/include/bits/hashtable_policy.h | 22 +++ libstdc++-v3/include/bits/stl_function.h | 15 ++ libstdc++-v3/include/bits/stl_tree.h | 15 -- libstdc++-v3/include/bits/unordered_map.h | 94 ++++++++++ libstdc++-v3/include/bits/unordered_set.h | 99 ++++++++++ libstdc++-v3/include/debug/unordered_map | 84 +++++++++ libstdc++-v3/include/debug/unordered_set | 84 +++++++++ .../23_containers/unordered_map/operations/1.cc | 168 +++++++++++++++++ .../unordered_multimap/operations/1.cc | 135 ++++++++++++++ .../unordered_multiset/operations/1.cc | 135 ++++++++++++++ .../23_containers/unordered_set/operations/1.cc | 186 +++++++++++++++++++ 12 files changed, 1223 insertions(+), 15 deletions(-) create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_map/operations/1.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multimap/operations/1.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_multiset/operations/1.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_set/operations/1.cc diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index bc7ec92..fa80675 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -724,6 +724,38 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION std::pair equal_range(const key_type& __k) const; +#if __cplusplus > 201702L + template, + typename = __has_is_transparent_t<_Equal, _Kt>> + iterator + _M_find_tr(const _Kt& __k); + + template, + typename = __has_is_transparent_t<_Equal, _Kt>> + const_iterator + _M_find_tr(const _Kt& __k) const; + + template, + typename = __has_is_transparent_t<_Equal, _Kt>> + size_type + _M_count_tr(const _Kt& __k) const; + + template, + typename = __has_is_transparent_t<_Equal, _Kt>> + pair + _M_equal_range_tr(const _Kt& __k); + + template, + typename = __has_is_transparent_t<_Equal, _Kt>> + pair + _M_equal_range_tr(const _Kt& __k) const; +#endif + private: // Bucket index computation helpers. size_type @@ -739,6 +771,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __node_base_ptr _M_find_before_node(size_type, const key_type&, __hash_code) const; + template + __node_base_ptr + _M_find_before_node_tr(size_type, const _Kt&, __hash_code) const; + __node_ptr _M_find_node(size_type __bkt, const key_type& __key, __hash_code __c) const @@ -749,6 +785,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return nullptr; } + template + __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 + template + 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 + template + 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 201703L + template + template + 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 201703L + template + template + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_equal_range_tr(const _Kt& __k) + -> pair + { + __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 + template + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_equal_range_tr(const _Kt& __k) const + -> pair + { + __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 + template + 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 void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index 999147a..90797f8 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 + __hash_code + _M_hash_code_tr(const _Kt& __k) const + { + static_assert(__is_invocable{}, + "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 + bool + _M_equals_tr(const _Kt& __k, __hash_code __c, + const _Hash_node_value<_Value, + __hash_cached::value>& __n) const + { + static_assert( + __is_invocable{}, + "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 dac005d..073018d 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> + struct __has_is_transparent + { }; + + template + struct __has_is_transparent<_Func, _SfinaeType, + __void_t> + { typedef void type; }; + + template + 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 a75591d..550195a 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> - struct __has_is_transparent - { }; - - template - struct __has_is_transparent<_Cmp, _SfinaeType, - __void_t> - { typedef void type; }; - - template - using __has_is_transparent_t - = typename __has_is_transparent<_Cmp, _SfinaeType>::type; -#endif - #if __cplusplus > 201402L template struct _Rb_tree_merge_helper { }; diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h index 70ce6ab..d617d2d9 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 + 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 + 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 + 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 + 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 + 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 equal_range(const key_type& __x) const { return _M_h.equal_range(__x); } + +#if __cplusplus > 201703L + template + 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 + 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 + 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 + 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 + 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 + 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 equal_range(const key_type& __x) const { return _M_h.equal_range(__x); } + +#if __cplusplus > 201703L + template + 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 5bc31a2..63c1a7e 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 + 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 + 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 + 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 + 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 + 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 equal_range(const key_type& __x) const { return _M_h.equal_range(__x); } + +#if __cplusplus > 201703L + template + 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 + 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 + 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 + 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 + 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 + 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 equal_range(const key_type& __x) const { return _M_h.equal_range(__x); } + +#if __cplusplus > 201703L + template + 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 7e71f29..bb697d3 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 = 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 = std::__has_is_transparent_t<_Pred, _Kt>> + const_iterator + find(const _Kt& __k) const + { return { _Base::find(__k), this }; } +#endif + std::pair equal_range(const key_type& __key) { @@ -556,6 +574,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair + equal_range(const _Kt& __k) + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + std::pair 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 = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair + 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 = 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 = std::__has_is_transparent_t<_Pred, _Kt>> + const_iterator + find(const _Kt& __k) const + { return { _Base::find(__k), this }; } +#endif + std::pair equal_range(const key_type& __key) { @@ -1168,6 +1228,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair + equal_range(const _Kt& __k) + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + std::pair 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 = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair + 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 39198a8..c259109 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 = 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 = std::__has_is_transparent_t<_Pred, _Kt>> + const_iterator + find(const _Kt& __k) const + { return { _Base::find(__k), this }; } +#endif + std::pair equal_range(const key_type& __key) { @@ -441,6 +459,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair + equal_range(const _Kt& __k) + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + std::pair 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 = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair + 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 = 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 = std::__has_is_transparent_t<_Pred, _Kt>> + const_iterator + find(const _Kt& __k) const + { return { _Base::find(__k), this }; } +#endif + std::pair equal_range(const key_type& __key) { @@ -1013,6 +1073,18 @@ namespace __debug return { { __res.first, this }, { __res.second, this } }; } +#if __cplusplus > 201703L + template, + typename = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair + equal_range(const _Kt& __k) + { + auto __res = _Base::equal_range(__k); + return { { __res.first, this }, { __res.second, this } }; + } +#endif + std::pair 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 = std::__has_is_transparent_t<_Pred, _Kt>> + std::pair + 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 0000000..4f2df72 --- /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 +// . + +// { dg-do run { target c++20 } } + +#include +#include + +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; + +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::value, + "find returns iterator"); + static_assert(std::is_same::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; + static_assert(std::is_same::value, + "equal_range returns pair"); + using cpair = std::pair; + static_assert(std::is_same::value, + "const equal_range returns pair"); +} + +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 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 0000000..16940db --- /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 +// . + +// { dg-do run { target c++20 } } + +#include +#include + +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; + +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::value, + "find returns iterator"); + static_assert(std::is_same::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; + static_assert(std::is_same::value, + "equal_range returns pair"); + using cpair = std::pair; + static_assert(std::is_same::value, + "const equal_range returns pair"); +} + + +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 0000000..81b82fc --- /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 +// . + +// { dg-do run { target c++20 } } + +#include +#include + +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; + +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::value, + "find returns iterator"); + static_assert(std::is_same::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; + static_assert(std::is_same::value, + "equal_range returns pair"); + using cpair = std::pair; + static_assert(std::is_same::value, + "const equal_range returns pair"); +} + + +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 0000000..34414d2 --- /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 +// . + +// { dg-do run { target c++20 } } + +#include +#include + +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; + +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::value, + "find returns iterator"); + static_assert(std::is_same::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; + static_assert(std::is_same::value, + "equal_range returns pair"); + using cpair = std::pair; + static_assert(std::is_same::value, + "const equal_range returns pair"); +} + +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 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 s{ 1, 2, 3, 4, 5 }; + + auto n = s.count(E::Partition{}); + VERIFY( n == 2 ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); + test05(); +} -- 2.7.4