* [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).