Remaining to do:
* Add new declarations in debug headers too.
Implement C++23 P2077R3 "Heterogeneous erasure overloads for
associative containers". Adds template overloads for members
erase and extract to address elements using an alternative key
type, such as string_view for a container of strings, without
need to construct an actual key object.
The new overloads enforce concept __heterogeneous_tree_key or
__heterogeneous_hash_key to verify the function objects provided
meet requirements, and that the key supplied is not an iterator
or the native key.
libstdc++-v3/ChangeLog:
PR libstdc++/117404
* include/bits/version.def (associative_heterogeneous_erasure):
Define.
* include/bits/version.h: Regenerate.
* include/std/map: Request new feature from version.h.
* include/std/set: Same.
* include/std/unordered_map: Same.
* include/std/unordered_set: Same.
* include/bits/stl_map.h (extract, erase): Define overloads.
* include/bits/stl_set.h: Same.
* include/bits/stl_multimap.h: Same.
* include/bits/stl_multiset.h: Same.
* include/bits/unordered_map.h: Same, 2x.
* include/bits/unordered_set.h: Same, 2x.
* include/bits/stl_function.h (concepts __not_container_iterator,
__heterogeneous_key): Define.
* include/bits/hashtable.h (_M_find_before_node, _M_locate, extract):
Delegate to more-general _tr version.
(_M_find_before_node_tr, _M_locate_tr, _M_extract_tr, _M_erase_tr):
Add new members to support a heterogeneous key argument.
(_M_erase_some): Add new helper function.
(concept __heterogeneous_hash_key): Define.
* include/bits/stl_tree.h (_M_lower_bound_tr, _M_upper_bound_tr,
_M_erase_tr, _M_extract_tr): Add new members to support a
heterogeneous key argument.
(concept __heterogeneous_tree_key): Define.
* testsuite/23_containers/map/modifiers/hetero/erase.cc: New test.
* testsuite/23_containers/multimap/modifiers/hetero/erase.cc: Same.
* testsuite/23_containers/multiset/modifiers/hetero/erase.cc: Same.
* testsuite/23_containers/set/modifiers/hetero/erase.cc: Same.
* testsuite/23_containers/unordered_map/modifiers/hetero/erase.cc: Same.
* testsuite/23_containers/unordered_multimap/modifiers/hetero/erase.cc:
Same.
* testsuite/23_containers/unordered_multiset/modifiers/hetero/erase.cc:
Same.
* testsuite/23_containers/unordered_set/modifiers/hetero/erase.cc: Same.
---
libstdc++-v3/include/bits/hashtable.h | 241 +++++++++++-------
libstdc++-v3/include/bits/stl_function.h | 12 +
libstdc++-v3/include/bits/stl_map.h | 20 ++
libstdc++-v3/include/bits/stl_multimap.h | 15 ++
libstdc++-v3/include/bits/stl_multiset.h | 15 ++
libstdc++-v3/include/bits/stl_set.h | 18 ++
libstdc++-v3/include/bits/stl_tree.h | 75 +++++-
libstdc++-v3/include/bits/unordered_map.h | 28 ++
libstdc++-v3/include/bits/unordered_set.h | 28 ++
libstdc++-v3/include/bits/version.def | 8 +
libstdc++-v3/include/bits/version.h | 10 +
libstdc++-v3/include/std/map | 1 +
libstdc++-v3/include/std/set | 1 +
libstdc++-v3/include/std/unordered_map | 1 +
libstdc++-v3/include/std/unordered_set | 1 +
.../map/modifiers/hetero/erase.cc | 95 +++++++
.../multimap/modifiers/hetero/erase.cc | 95 +++++++
.../multiset/modifiers/hetero/erase.cc | 88 +++++++
.../set/modifiers/hetero/erase.cc | 88 +++++++
.../unordered_map/modifiers/hetero/erase.cc | 76 ++++++
.../modifiers/hetero/erase.cc | 75 ++++++
.../modifiers/hetero/erase.cc | 73 ++++++
.../unordered_set/modifiers/hetero/erase.cc | 73 ++++++
23 files changed, 1037 insertions(+), 100 deletions(-)
create mode 100644
libstdc++-v3/testsuite/23_containers/map/modifiers/hetero/erase.cc
create mode 100644
libstdc++-v3/testsuite/23_containers/multimap/modifiers/hetero/erase.cc
create mode 100644
libstdc++-v3/testsuite/23_containers/multiset/modifiers/hetero/erase.cc
create mode 100644
libstdc++-v3/testsuite/23_containers/set/modifiers/hetero/erase.cc
create mode 100644
libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/hetero/erase.cc
create mode 100644
libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/hetero/erase.cc
create mode 100644
libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/hetero/erase.cc
create mode 100644
libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/hetero/erase.cc
diff --git a/libstdc++-v3/include/bits/hashtable.h
b/libstdc++-v3/include/bits/hashtable.h
index c92b843bf0b..f7b8905d8ab 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -853,7 +853,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// Find the node before the one matching the criteria.
__node_base_ptr
- _M_find_before_node(size_type, const key_type&, __hash_code) const;
+ _M_find_before_node(
+ size_type __bkt, const key_type& __k, __hash_code __code) const
+ { return _M_find_before_node_tr<key_type>(__bkt, __k, __code); }
template<typename _Kt>
__node_base_ptr
@@ -902,8 +904,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// The _M_before pointer might point to _M_before_begin, so must not be
// cast to __node_ptr, and it must not be used to modify *_M_before
// except in non-const member functions, such as erase.
+
__location_type
- _M_locate(const key_type& __k) const;
+ _M_locate(const key_type& __k) const
+ { return _M_locate_tr<key_type>(__k); }
+
+ template <typename _Kt>
+ __location_type
+ _M_locate_tr(const _Kt& __k) const;
__node_ptr
_M_find_node(size_type __bkt, const key_type& __key,
@@ -1016,6 +1024,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
iterator
_M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n);
+ size_type
+ _M_erase_some(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n);
+
template<typename _InputIterator>
void
_M_insert_range_multi(_InputIterator __first, _InputIterator __last);
@@ -1163,6 +1174,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
size_type
erase(const key_type& __k);
+ template <typename _Kt>
+ size_type
+ _M_erase_tr(const _Kt& __k);
+
iterator
erase(const_iterator, const_iterator);
@@ -1274,14 +1289,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
/// Extract a node.
node_type
extract(const _Key& __k)
- {
- node_type __nh;
- __hash_code __code = this->_M_hash_code(__k);
- std::size_t __bkt = _M_bucket_index(__code);
- if (__node_base_ptr __prev_node = _M_find_before_node(__bkt, __k,
__code))
- __nh = _M_extract_node(__bkt, __prev_node);
- return __nh;
- }
+ { return _M_extract_tr<_Key>(__k); }
+
+ template <typename _Kt>
+ node_type
+ _M_extract_tr(const _Kt& __k)
+ {
+ node_type __nh;
+ __hash_code __code = this->_M_hash_code_tr(__k);
+ std::size_t __bkt = _M_bucket_index(__code);
+ if (__node_base_ptr __prev_node =
+ _M_find_before_node_tr(__bkt, __k, __code))
+ __nh = _M_extract_node(__bkt, __prev_node);
+ return __nh;
+ }
/// Merge from another container of the same type.
void
@@ -2194,35 +2215,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// 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>
- auto
- _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_find_before_node(size_type __bkt, const key_type& __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(__k, __code, *__p))
- return __prev_p;
-
- if (__builtin_expect (!__p->_M_nxt ||
_M_bucket_index(*__p->_M_next()) != __bkt, 0))
- break;
- __prev_p = __p;
- }
-
- return nullptr;
- }
-
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
typename _Hash, typename _RangeHash, typename _Unused,
@@ -2245,7 +2237,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (this->_M_equals_tr(__k, __code, *__p))
return __prev_p;
- if (__builtin_expect (!__p->_M_nxt ||
_M_bucket_index(*__p->_M_next()) != __bkt, 0))
+ if (__builtin_expect (
+ !__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt, 0))
break;
__prev_p = __p;
}
@@ -2257,37 +2250,38 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typename _ExtractKey, typename _Equal,
typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
- inline auto
- _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
- _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
- _M_locate(const key_type& __k) const
- -> __location_type
- {
- __location_type __loc;
- const auto __size = size();
+ template <typename _Kt>
+ inline auto
+ _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
+ _M_locate_tr(const _Kt& __k) const
+ -> __location_type
+ {
+ __location_type __loc;
+ const auto __size = size();
- if (__size <= __small_size_threshold())
- {
- __loc._M_before = pointer_traits<__node_base_ptr>::
- pointer_to(const_cast<__node_base&>(_M_before_begin));
- while (__loc._M_before->_M_nxt)
- {
- if (this->_M_key_equals(__k, *__loc._M_node()))
- return __loc;
- __loc._M_before = __loc._M_before->_M_nxt;
- }
- __loc._M_before = nullptr; // Didn't find it.
- }
+ if (__size <= __small_size_threshold())
+ {
+ __loc._M_before = pointer_traits<__node_base_ptr>::
+ pointer_to(const_cast<__node_base&>(_M_before_begin));
+ while (__loc._M_before->_M_nxt)
+ {
+ if (this->_M_key_equals_tr(__k, *__loc._M_node()))
+ return __loc;
+ __loc._M_before = __loc._M_before->_M_nxt;
+ }
+ __loc._M_before = nullptr; // Didn't find it.
+ }
- __loc._M_hash_code = this->_M_hash_code(__k);
- __loc._M_bucket_index = _M_bucket_index(__loc._M_hash_code);
+ __loc._M_hash_code = this->_M_hash_code_tr(__k);
+ __loc._M_bucket_index = _M_bucket_index(__loc._M_hash_code);
- if (__size > __small_size_threshold())
- __loc._M_before = _M_find_before_node(__loc._M_bucket_index, __k,
- __loc._M_hash_code);
+ if (__size > __small_size_threshold())
+ __loc._M_before = _M_find_before_node_tr(
+ __loc._M_bucket_index, __k, __loc._M_hash_code);
- return __loc;
- }
+ return __loc;
+ }
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
@@ -2598,6 +2592,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
+
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
typename _Hash, typename _RangeHash, typename _Unused,
@@ -2617,47 +2612,87 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto __bkt = __loc._M_bucket_index;
if (__bkt == size_type(-1))
__bkt = _M_bucket_index(*__n);
-
if constexpr (__unique_keys::value)
{
_M_erase(__bkt, __prev_n, __n);
return 1;
}
else
+ return _M_erase_some(__bkt, __prev_n, __n);
+ }
+
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
+ auto
+ _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
+ _M_erase_some(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n)
+ -> size_type
+ {
+ // _GLIBCXX_RESOLVE_LIB_DEFECTS
+ // 526. Is it undefined if a function in the standard changes
+ // in parameters?
+ // We use one loop to find all matching nodes and another to
+ // deallocate them so that the key stays valid during the first loop.
+ // It might be invalidated indirectly when destroying nodes.
+ __node_ptr __n_last = __n->_M_next();
+ while (__n_last && this->_M_node_equals(*__n, *__n_last))
+ __n_last = __n_last->_M_next();
+
+ std::size_t __n_last_bkt
+ = __n_last ? _M_bucket_index(*__n_last) : __bkt;
+
+ // Deallocate nodes.
+ size_type __result = 0;
+ do
{
- // _GLIBCXX_RESOLVE_LIB_DEFECTS
- // 526. Is it undefined if a function in the standard changes
- // in parameters?
- // We use one loop to find all matching nodes and another to
- // deallocate them so that the key stays valid during the first loop.
- // It might be invalidated indirectly when destroying nodes.
- __node_ptr __n_last = __n->_M_next();
- while (__n_last && this->_M_node_equals(*__n, *__n_last))
- __n_last = __n_last->_M_next();
-
- std::size_t __n_last_bkt
- = __n_last ? _M_bucket_index(*__n_last) : __bkt;
-
- // Deallocate nodes.
- size_type __result = 0;
- do
- {
- __node_ptr __p = __n->_M_next();
- this->_M_deallocate_node(__n);
- __n = __p;
- ++__result;
- }
- while (__n != __n_last);
-
- _M_element_count -= __result;
- if (__prev_n == _M_buckets[__bkt])
- _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
- else if (__n_last_bkt != __bkt)
- _M_buckets[__n_last_bkt] = __prev_n;
- __prev_n->_M_nxt = __n_last;
- return __result;
+ __node_ptr __p = __n->_M_next();
+ this->_M_deallocate_node(__n);
+ __n = __p;
+ ++__result;
}
+ while (__n != __n_last);
+
+ _M_element_count -= __result;
+ if (__prev_n == _M_buckets[__bkt])
+ _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
+ else if (__n_last_bkt != __bkt)
+ _M_buckets[__n_last_bkt] = __prev_n;
+ __prev_n->_M_nxt = __n_last;
+ return __result;
}
+
+ 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_erase_tr(const _Kt& __k)
+ -> size_type
+ {
+ auto __loc = _M_locate_tr(__k);
+ if (!__loc)
+ return 0;
+
+ __node_base_ptr __prev_n = __loc._M_before;
+ __node_ptr __n = __loc._M_node();
+ auto __bkt = __loc._M_bucket_index;
+ if (__bkt == size_type(-1))
+ __bkt = _M_bucket_index(*__n);
+ if constexpr (__unique_keys::value)
+ {
+ _M_erase(__bkt, __prev_n, __n);
+ return 1;
+ }
+ else
+ return _M_erase_some(__bkt, __prev_n, __n);
+ }
+
#pragma GCC diagnostic pop
template<typename _Key, typename _Value, typename _Alloc,
@@ -2977,6 +3012,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
= __enable_if_t<!__or_<is_integral<_Hash>,
__is_allocator<_Hash>>::value>;
#endif
+#ifdef __cpp_concepts
+template <typename _Kt, typename _Container>
+ concept __heterogeneous_hash_key =
+ __transparent_comparator<typename _Container::hasher> &&
+ __transparent_comparator<typename _Container::key_equal> &&
+ __heterogeneous_key<_Kt, _Container>;
+#endif
+
/// @endcond
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
diff --git a/libstdc++-v3/include/bits/stl_function.h
b/libstdc++-v3/include/bits/stl_function.h
index 0600de72b10..edbbfe11b96 100644
--- a/libstdc++-v3/include/bits/stl_function.h
+++ b/libstdc++-v3/include/bits/stl_function.h
@@ -1525,6 +1525,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
#endif
#endif
+#ifdef __cpp_concepts
+template <typename _Kt, typename _Container>
+ concept __not_container_iterator =
+ (!is_convertible_v<_Kt&&, typename _Container::iterator> &&
+ !is_convertible_v<_Kt&&, typename _Container::const_iterator>);
+
+template <typename _Kt, typename _Container>
+ concept __heterogeneous_key =
+ (!is_same_v<typename _Container::key_type, remove_cvref_t<_Kt>>) &&
+ __not_container_iterator<_Kt, _Container>;
+#endif
+
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace
diff --git a/libstdc++-v3/include/bits/stl_map.h
b/libstdc++-v3/include/bits/stl_map.h
index 6620bfee931..4cb0c982c3d 100644
--- a/libstdc++-v3/include/bits/stl_map.h
+++ b/libstdc++-v3/include/bits/stl_map.h
@@ -65,6 +65,7 @@
#if __glibcxx_containers_ranges // C++ >= 23
# include <bits/ranges_base.h> // ranges::begin, ranges::distance etc.
#endif
+// #include <stl_tree.h> // done in std/map
namespace std _GLIBCXX_VISIBILITY(default)
{
@@ -679,6 +680,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
extract(const key_type& __x)
{ return _M_t.extract(__x); }
+#ifdef __glibcxx_associative_heterogeneous_erasure // C++23
+ template <__heterogeneous_tree_key<map> _Kt>
+ node_type
+ extract(_Kt&& __key)
+ { return _M_t._M_extract_tr(__key); }
+#endif
+
/// Re-insert an extracted node.
insert_return_type
insert(node_type&& __nh)
@@ -1143,6 +1151,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
{ _M_t.erase(__position); }
#endif
+ ///@{
/**
* @brief Erases elements according to the provided key.
* @param __x Key of element to be erased.
@@ -1158,6 +1167,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
erase(const key_type& __x)
{ return _M_t._M_erase_unique(__x); }
+#ifdef __glibcxx_associative_heterogeneous_erasure // C++23
+ // Note that for some types _Kt this may erase more than
+ // one element, such as if _Kt::operator< checks only part
+ // of the key.
+ template <__heterogeneous_tree_key<map> _Kt>
+ size_type
+ erase(_Kt&& __x)
+ { return _M_t._M_erase_tr(__x); }
+#endif
+ ///@}
+
#if __cplusplus >= 201103L
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 130. Associative erase should return an iterator.
diff --git a/libstdc++-v3/include/bits/stl_multimap.h
b/libstdc++-v3/include/bits/stl_multimap.h
index ea68401a88c..6f4e425d771 100644
--- a/libstdc++-v3/include/bits/stl_multimap.h
+++ b/libstdc++-v3/include/bits/stl_multimap.h
@@ -63,6 +63,7 @@
#if __glibcxx_containers_ranges // C++ >= 23
# include <bits/ranges_base.h> // ranges::begin, ranges::distance etc.
#endif
+// #include <bits/stl_tree.h> // done in std/map
namespace std _GLIBCXX_VISIBILITY(default)
{
@@ -688,6 +689,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
extract(const key_type& __x)
{ return _M_t.extract(__x); }
+#ifdef __glibcxx_associative_heterogeneous_erasure // C++23
+ template <__heterogeneous_tree_key<multimap> _Kt>
+ node_type
+ extract(_Kt&& __key)
+ { return _M_t._M_extract_tr(__key); }
+#endif
+
/// Re-insert an extracted node.
iterator
insert(node_type&& __nh)
@@ -787,6 +795,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
erase(const key_type& __x)
{ return _M_t.erase(__x); }
+#ifdef __glibcxx_associative_heterogeneous_erasure // C++23
+ template <__heterogeneous_tree_key<multimap> _Kt>
+ size_type
+ erase(_Kt&& __key)
+ { return _M_t._M_erase_tr(__key); }
+#endif
+
#if __cplusplus >= 201103L
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 130. Associative erase should return an iterator.
diff --git a/libstdc++-v3/include/bits/stl_multiset.h
b/libstdc++-v3/include/bits/stl_multiset.h
index db950da50ea..64047ad7631 100644
--- a/libstdc++-v3/include/bits/stl_multiset.h
+++ b/libstdc++-v3/include/bits/stl_multiset.h
@@ -63,6 +63,7 @@
#if __glibcxx_containers_ranges // C++ >= 23
# include <bits/ranges_base.h> // ranges::begin, ranges::distance etc.
#endif
+// #include <bits/stl_tree.h> // done in std/set
namespace std _GLIBCXX_VISIBILITY(default)
{
@@ -621,6 +622,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
extract(const key_type& __x)
{ return _M_t.extract(__x); }
+#ifdef __glibcxx_associative_heterogeneous_erasure // C++23
+ template <__heterogeneous_tree_key<multiset> _Kt>
+ node_type
+ extract(_Kt&& __key)
+ { return _M_t._M_extract_tr(__key); }
+#endif
+
/// Re-insert an extracted node.
iterator
insert(node_type&& __nh)
@@ -712,6 +720,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
erase(const key_type& __x)
{ return _M_t.erase(__x); }
+#ifdef __glibcxx_associative_heterogeneous_erasure // C++23
+ template <__heterogeneous_tree_key<multiset> _Kt>
+ size_type
+ erase(_Kt&& __key)
+ { return _M_t._M_erase_tr(__key); }
+#endif
+
#if __cplusplus >= 201103L
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 130. Associative erase should return an iterator.
diff --git a/libstdc++-v3/include/bits/stl_set.h
b/libstdc++-v3/include/bits/stl_set.h
index 96089fb172d..d3a4c089110 100644
--- a/libstdc++-v3/include/bits/stl_set.h
+++ b/libstdc++-v3/include/bits/stl_set.h
@@ -63,6 +63,7 @@
#if __glibcxx_containers_ranges // C++ >= 23
# include <bits/ranges_base.h> // ranges::begin, ranges::distance etc.
#endif
+// #include <bits/stl_tree.h> // done in std/set
namespace std _GLIBCXX_VISIBILITY(default)
{
@@ -639,6 +640,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
extract(const key_type& __x)
{ return _M_t.extract(__x); }
+#ifdef __glibcxx_associative_heterogeneous_erasure // C++23
+ template <__heterogeneous_tree_key<set> _Kt>
+ node_type
+ extract(_Kt&& __key)
+ { return _M_t._M_extract_tr(__key); }
+#endif
+
/// Re-insert an extracted node.
insert_return_type
insert(node_type&& __nh)
@@ -730,6 +738,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
erase(const key_type& __x)
{ return _M_t._M_erase_unique(__x); }
+#ifdef __glibcxx_associative_heterogeneous_erasure // C++23
+ // Note that for some types _Kt this may erase more than
+ // one element, such as if _Kt::operator< checks only part
+ // of the key.
+ template <__heterogeneous_tree_key<set> _Kt>
+ size_type
+ erase(_Kt&& __key)
+ { return _M_t._M_erase_tr(__key); }
+#endif
+
#if __cplusplus >= 201103L
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 130. Associative erase should return an iterator.
diff --git a/libstdc++-v3/include/bits/stl_tree.h
b/libstdc++-v3/include/bits/stl_tree.h
index 8f0aa731c93..7a733241ec5 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -1400,7 +1400,7 @@ namespace __rb_tree
// Enforce this here with a user-friendly message.
static_assert(
__is_invocable<const _Compare&, const _Key&, const _Key&>::value,
- "comparison object must be invocable with two arguments of key type"
+ "comparison object must be invocable with arguments of key_type"
);
#endif
return _M_impl._M_key_compare(__k1, __k2);
@@ -1539,10 +1539,18 @@ namespace __rb_tree
_M_lower_bound(_Base_ptr __x, _Base_ptr __y,
const _Key& __k) const;
+ template <typename _Kt>
+ _Base_ptr
+ _M_lower_bound_tr(_Base_ptr __x, _Base_ptr __y, const _Kt& __k) const;
+
_Base_ptr
_M_upper_bound(_Base_ptr __x, _Base_ptr __y,
const _Key& __k) const;
+ template <typename _Kt>
+ _Base_ptr
+ _M_upper_bound_tr(_Base_ptr __x, _Base_ptr __y, const _Kt& __k) const;
+
public:
// allocation/deallocation
#if __cplusplus < 201103L
@@ -1850,6 +1858,10 @@ namespace __rb_tree
size_type
erase(const key_type& __x);
+ template <typename _Kt>
+ size_type
+ _M_erase_tr(const _Kt& __x);
+
size_type
_M_erase_unique(const key_type& __x);
@@ -2198,6 +2210,17 @@ namespace __rb_tree
return __nh;
}
+ template <typename _Kt>
+ node_type
+ _M_extract_tr(const _Kt& __k)
+ {
+ node_type __nh;
+ auto __pos = _M_find_tr(__k);
+ if (__pos != end())
+ __nh = extract(const_iterator(__pos));
+ return __nh;
+ }
+
template<typename _Compare2>
using _Compatible_tree
= _Rb_tree<_Key, _Val, _KeyOfValue, _Compare2, _Alloc>;
@@ -2612,6 +2635,21 @@ namespace __rb_tree
return __y;
}
+ template<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ template <typename _Kt>
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Base_ptr
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_lower_bound_tr(_Base_ptr __x, _Base_ptr __y, const _Kt& __k) const
+ {
+ while (__x)
+ if (!_M_key_compare(_S_key(__x), __k))
+ __y = __x, __x = _S_left(__x);
+ else
+ __x = _S_right(__x);
+ return __y;
+ }
+
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue,
@@ -2628,6 +2666,21 @@ namespace __rb_tree
return __y;
}
+ template<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ template <typename _Kt>
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Base_ptr
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_upper_bound_tr(_Base_ptr __x, _Base_ptr __y, const _Kt& __k) const
+ {
+ while (__x)
+ if (_M_key_compare(__k, _S_key(__x)))
+ __y = __x, __x = _S_left(__x);
+ else
+ __x = _S_right(__x);
+ return __y;
+ }
+
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
@@ -3142,6 +3195,19 @@ namespace __rb_tree
return __old_size - size();
}
+ template<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ template <typename _Kt>
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_erase_tr(const _Kt& __x)
+ {
+ pair<iterator, iterator> __p = _M_equal_range_tr(__x);
+ const size_type __old_size = size();
+ _M_erase_aux(__p.first, __p.second);
+ return __old_size - size();
+ }
+
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
@@ -3249,6 +3315,13 @@ namespace __rb_tree
};
#endif // C++17
+#ifdef __cpp_concepts
+template <typename _Kt, typename _Container>
+ concept __heterogeneous_tree_key =
+ __transparent_comparator<typename _Container::key_compare> &&
+ __heterogeneous_key<_Kt, _Container>;
+#endif
+
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace
diff --git a/libstdc++-v3/include/bits/unordered_map.h
b/libstdc++-v3/include/bits/unordered_map.h
index 36f5a8d91c3..9b74cba8675 100644
--- a/libstdc++-v3/include/bits/unordered_map.h
+++ b/libstdc++-v3/include/bits/unordered_map.h
@@ -501,6 +501,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
extract(const key_type& __key)
{ return _M_h.extract(__key); }
+#ifdef __glibcxx_associative_heterogeneous_erasure // C++23
+ template <__heterogeneous_hash_key<unordered_map> _Kt>
+ node_type
+ extract(_Kt&& __key)
+ { return _M_h._M_extract_tr(__key); }
+#endif
+
/// Re-insert an extracted node.
insert_return_type
insert(node_type&& __nh)
@@ -848,6 +855,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
erase(const key_type& __x)
{ return _M_h.erase(__x); }
+#ifdef __glibcxx_associative_heterogeneous_erasure // C++23
+ template <__heterogeneous_hash_key<unordered_map> _Kt>
+ size_type
+ erase(_Kt&& __key)
+ { return _M_h._M_erase_tr(__key); }
+#endif
+
/**
* @brief Erases a [__first,__last) range of elements from an
* %unordered_map.
@@ -1872,6 +1886,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
extract(const key_type& __key)
{ return _M_h.extract(__key); }
+#ifdef __glibcxx_associative_heterogeneous_erasure // C++23
+ template <__heterogeneous_hash_key<unordered_multimap> _Kt>
+ node_type
+ extract(_Kt&& __key)
+ { return _M_h._M_extract_tr(__key); }
+#endif
+
/// Re-insert an extracted node.
iterator
insert(node_type&& __nh)
@@ -1922,6 +1943,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
erase(const key_type& __x)
{ return _M_h.erase(__x); }
+#ifdef __glibcxx_associative_heterogeneous_erasure // C++23
+ template <__heterogeneous_hash_key<unordered_multimap> _Kt>
+ size_type
+ erase(_Kt&& __key)
+ { return _M_h._M_erase_tr(__key); }
+#endif
+
/**
* @brief Erases a [__first,__last) range of elements from an
* %unordered_multimap.
diff --git a/libstdc++-v3/include/bits/unordered_set.h
b/libstdc++-v3/include/bits/unordered_set.h
index 3a96229e1f5..22b2ad9caf4 100644
--- a/libstdc++-v3/include/bits/unordered_set.h
+++ b/libstdc++-v3/include/bits/unordered_set.h
@@ -581,6 +581,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
extract(const key_type& __key)
{ return _M_h.extract(__key); }
+#ifdef __glibcxx_associative_heterogeneous_erasure // C++23
+ template <__heterogeneous_hash_key<unordered_set> _Kt>
+ node_type
+ extract(_Kt&& __key)
+ { return _M_h._M_extract_tr(__key); }
+#endif
+
/// Re-insert an extracted node.
insert_return_type
insert(node_type&& __nh)
@@ -632,6 +639,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
erase(const key_type& __x)
{ return _M_h.erase(__x); }
+#ifdef __glibcxx_associative_heterogeneous_erasure // C++23
+ template <__heterogeneous_hash_key<unordered_set> _Kt>
+ size_type
+ erase(_Kt&& __key)
+ { return _M_h._M_erase_tr(__key); }
+#endif
+
/**
* @brief Erases a [__first,__last) range of elements from an
* %unordered_set.
@@ -1574,6 +1588,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
extract(const key_type& __key)
{ return _M_h.extract(__key); }
+#ifdef __glibcxx_associative_heterogeneous_erasure // C++23
+ template <__heterogeneous_hash_key<unordered_multiset> _Kt>
+ node_type
+ extract(_Kt&& __key)
+ { return _M_h._M_extract_tr(__key); }
+#endif
+
/// Re-insert an extracted node.
iterator
insert(node_type&& __nh)
@@ -1627,6 +1648,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
erase(const key_type& __x)
{ return _M_h.erase(__x); }
+#ifdef __glibcxx_associative_heterogeneous_erasure // C++23
+ template <__heterogeneous_hash_key<unordered_multiset> _Kt>
+ size_type
+ erase(_Kt&& __key)
+ { return _M_h._M_erase_tr(__key); }
+#endif
+
/**
* @brief Erases a [__first,__last) range of elements from an
* %unordered_multiset.
diff --git a/libstdc++-v3/include/bits/version.def
b/libstdc++-v3/include/bits/version.def
index ba0ef5aecfd..4b8e9d43ec2 100644
--- a/libstdc++-v3/include/bits/version.def
+++ b/libstdc++-v3/include/bits/version.def
@@ -1633,6 +1633,14 @@ ftms = {
};
};
+ftms = {
+ name = associative_heterogeneous_erasure;
+ values = {
+ v = 202110;
+ cxxmin = 23;
+ };
+};
+
ftms = {
name = is_scoped_enum;
values = {
diff --git a/libstdc++-v3/include/bits/version.h
b/libstdc++-v3/include/bits/version.h
index 74d1a28f75c..7602225cb6d 100644
--- a/libstdc++-v3/include/bits/version.h
+++ b/libstdc++-v3/include/bits/version.h
@@ -1801,6 +1801,16 @@
#endif /* !defined(__cpp_lib_invoke_r) */
#undef __glibcxx_want_invoke_r
+#if !defined(__cpp_lib_associative_heterogeneous_erasure)
+# if (__cplusplus >= 202100L)
+# define __glibcxx_associative_heterogeneous_erasure 202110L
+# if defined(__glibcxx_want_all) ||
defined(__glibcxx_want_associative_heterogeneous_erasure)
+# define __cpp_lib_associative_heterogeneous_erasure 202110L
+# endif
+# endif
+#endif /* !defined(__cpp_lib_associative_heterogeneous_erasure) */
+#undef __glibcxx_want_associative_heterogeneous_erasure
+
#if !defined(__cpp_lib_is_scoped_enum)
# if (__cplusplus >= 202100L)
# define __glibcxx_is_scoped_enum 202011L
diff --git a/libstdc++-v3/include/std/map b/libstdc++-v3/include/std/map
index 88e549411af..91612cf42c4 100644
--- a/libstdc++-v3/include/std/map
+++ b/libstdc++-v3/include/std/map
@@ -79,6 +79,7 @@
#define __glibcxx_want_node_extract
#define __glibcxx_want_nonmember_container_access
#define __glibcxx_want_tuple_like
+#define __glibcxx_want_associative_heterogeneous_erasure
#include <bits/version.h>
#if __cplusplus >= 201703L
diff --git a/libstdc++-v3/include/std/set b/libstdc++-v3/include/std/set
index af6d3814b4b..28eef1fc490 100644
--- a/libstdc++-v3/include/std/set
+++ b/libstdc++-v3/include/std/set
@@ -77,6 +77,7 @@
#define __glibcxx_want_generic_associative_lookup
#define __glibcxx_want_node_extract
#define __glibcxx_want_nonmember_container_access
+#define __glibcxx_want_associative_heterogeneous_erasure
#include <bits/version.h>
#if __cplusplus >= 201703L
diff --git a/libstdc++-v3/include/std/unordered_map
b/libstdc++-v3/include/std/unordered_map
index 9166f569ab1..f63be4104c5 100644
--- a/libstdc++-v3/include/std/unordered_map
+++ b/libstdc++-v3/include/std/unordered_map
@@ -56,6 +56,7 @@
#define __glibcxx_want_nonmember_container_access
#define __glibcxx_want_unordered_map_try_emplace
#define __glibcxx_want_tuple_like
+#define __glibcxx_want_associative_heterogeneous_erasure
#include <bits/version.h>
#if __cplusplus >= 201703L
diff --git a/libstdc++-v3/include/std/unordered_set
b/libstdc++-v3/include/std/unordered_set
index 157f72ce32d..45e6a915eb9 100644
--- a/libstdc++-v3/include/std/unordered_set
+++ b/libstdc++-v3/include/std/unordered_set
@@ -54,6 +54,7 @@
#define __glibcxx_want_generic_unordered_lookup
#define __glibcxx_want_node_extract
#define __glibcxx_want_nonmember_container_access
+#define __glibcxx_want_associative_heterogeneous_erasure
#include <bits/version.h>
#if __cplusplus >= 201703L
diff --git a/libstdc++-v3/testsuite/23_containers/map/modifiers/hetero/erase.cc
b/libstdc++-v3/testsuite/23_containers/map/modifiers/hetero/erase.cc
new file mode 100644
index 00000000000..20e0cbad261
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/map/modifiers/hetero/erase.cc
@@ -0,0 +1,95 @@
+// { dg-do run { target c++23 } }
+
+#include <map>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <compare>
+#include <cstring>
+#include <testsuite_hooks.h>
+
+struct X {
+ std::string s;
+ friend auto operator<=>(X const& a, X const& b) = default;
+};
+
+struct Y {
+ std::string_view s;
+ Y(std::string_view sv) : s(sv) {}
+ Y(std::string const& sv) : s(sv) {}
+ friend auto operator<=>(Y const& a, Y const& b) = default;
+ friend auto operator<=>(X const& a, Y const& b) { return a.s <=> b.s; }
+};
+
+using cmp = std::less<void>;
+
+// uniform erase
+void test1()
+{
+ std::map<X, int, cmp> amap{cmp{}};
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+ auto n = amap.erase(X{std::string{"def"}});
+ VERIFY(n == 1);
+ VERIFY(amap.size() == 2);
+}
+
+// heterogeneous erase
+void test2()
+{
+ std::map<X, int, cmp> amap{cmp{}};
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+ auto n = amap.erase(Y{std::string_view{"def"}});
+ VERIFY(n == 1);
+ VERIFY(amap.size() == 2);
+}
+
+// uniform extract
+void test3()
+{
+ std::map<X, int, cmp> amap{cmp{}};
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+ auto node = amap.extract(X{std::string{"def"}});
+ VERIFY(node.key().s == X{"def"}.s);
+ VERIFY(node.mapped() == 2);
+ VERIFY(amap.size() == 2);
+}
+
+// heterogeneous extract
+void test4()
+{
+ std::map<X, int, cmp> amap{cmp{}};
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+ auto node = amap.extract(Y{std::string_view{"def"}});
+ VERIFY(node.key().s == X{"def"}.s);
+ VERIFY(node.mapped() == 2);
+ VERIFY(amap.size() == 2);
+}
+
+struct Z {
+ std::string_view s;
+ friend auto operator<=>(X const& a, Z const& b) {
+ int cmp = std::memcmp(a.s.data(), b.s.data(), 3);
+ return cmp < 0 ? std::strong_ordering::less :
+ cmp == 0 ? std::strong_ordering::equal :
+ std::strong_ordering::greater;
+ }
+};
+
+void test5()
+{
+ std::map<X, int, cmp> amap{cmp{}};
+ amap.insert(
+ {{X{"abcdef"}, 1}, {X{"defghi"}, 2}, {X{"defjkl"}, 3}, {X{"jklmno"}, 4}});
+ auto n = amap.erase(Z{std::string_view{"def"}});
+ VERIFY(n == 2);
+ VERIFY(amap.size() == 2);
+}
+
+int main()
+{
+ test1();
+ test2();
+ test3();
+ test4();
+ test5();
+}
diff --git
a/libstdc++-v3/testsuite/23_containers/multimap/modifiers/hetero/erase.cc
b/libstdc++-v3/testsuite/23_containers/multimap/modifiers/hetero/erase.cc
new file mode 100644
index 00000000000..bd4a1520c2b
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multimap/modifiers/hetero/erase.cc
@@ -0,0 +1,95 @@
+// { dg-do run { target c++23 } }
+
+#include <map>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <compare>
+#include <cstring>
+#include <testsuite_hooks.h>
+
+struct X {
+ std::string s;
+ friend auto operator<=>(X const& a, X const& b) = default;
+};
+
+struct Y {
+ std::string_view s;
+ Y(std::string_view sv) : s(sv) {}
+ Y(std::string const& sv) : s(sv) {}
+ friend auto operator<=>(Y const& a, Y const& b) = default;
+ friend auto operator<=>(X const& a, Y const& b) { return a.s <=> b.s; }
+};
+
+using cmp = std::less<void>;
+
+// uniform erase
+void test1()
+{
+ std::multimap<X, int, cmp> amap{cmp{}};
+ amap.insert({{X{"abc"}, 0}, {X{"def"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+ auto n = amap.erase(X{std::string{"def"}});
+ VERIFY(n == 2);
+ VERIFY(amap.size() == 2);
+}
+
+// heterogeneous erase
+void test2()
+{
+ std::multimap<X, int, cmp> amap{cmp{}};
+ amap.insert({{X{"abc"}, 0}, {X{"def"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+ auto n = amap.erase(Y{std::string_view{"def"}});
+ VERIFY(n == 2);
+ VERIFY(amap.size() == 2);
+}
+
+// uniform extract
+void test3()
+{
+ std::multimap<X, int, cmp> amap{cmp{}};
+ amap.insert({{X{"abc"}, 0}, {X{"def"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+ const auto node = amap.extract(X{std::string{"def"}});
+ VERIFY(node.key().s == "def");
+ VERIFY(node.mapped() == 1);
+ VERIFY(amap.size() == 3);
+}
+
+// heterogeneous extract
+void test4()
+{
+ std::multimap<X, int, cmp> amap{cmp{}};
+ amap.insert({{X{"abc"}, 0}, {X{"def"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+ const auto node = amap.extract(Y{std::string_view{"def"}});
+ VERIFY(node.key().s == "def");
+ VERIFY(node.mapped() == 1);
+ VERIFY(amap.size() == 3);
+}
+
+struct Z {
+ std::string_view s;
+ friend auto operator<=>(X const& a, Z const& b) {
+ int cmp = std::memcmp(a.s.data(), b.s.data(), 3);
+ return cmp < 0 ? std::strong_ordering::less :
+ cmp == 0 ? std::strong_ordering::equal :
+ std::strong_ordering::greater;
+ }
+};
+
+void test5()
+{
+ std::map<X, int, cmp> amap{cmp{}};
+ amap.insert(
+ {{X{"abcdef"}, 1}, {X{"defghi"}, 2}, {X{"defjkl"}, 3}, {X{"jklmno"}, 4}});
+ auto n = amap.erase(Z{std::string_view{"def"}});
+ VERIFY(n == 2);
+ VERIFY(amap.size() == 2);
+}
+
+int main()
+{
+ test1();
+ test2();
+ test3();
+ test4();
+ test5();
+}
diff --git
a/libstdc++-v3/testsuite/23_containers/multiset/modifiers/hetero/erase.cc
b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/hetero/erase.cc
new file mode 100644
index 00000000000..8ebbc2604ba
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/hetero/erase.cc
@@ -0,0 +1,88 @@
+// { dg-do run { target c++23 } }
+
+#include <set>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <compare>
+#include <cstring>
+#include <testsuite_hooks.h>
+
+struct X {
+ std::string s;
+ friend auto operator<=>(X const& a, X const& b) = default;
+};
+
+struct Y {
+ std::string_view s;
+ Y(std::string_view sv) : s(sv) {}
+ Y(std::string const& sv) : s(sv) {}
+ friend auto operator<=>(Y const& a, Y const& b) = default;
+ friend auto operator<=>(X const& a, Y const& b) { return a.s <=> b.s; }
+};
+
+using cmp = std::less<void>;
+
+void test1() // uniform erase
+{
+ std::multiset<X, cmp> aset{cmp{}};
+ aset.insert({X{"abc"}, X{"def"}, X{"def"}, X{"ghi"}});
+ auto n = aset.erase(X{std::string{"def"}});
+ VERIFY(n == 2);
+ VERIFY(aset.size() == 2);
+}
+
+void test2() // heterogeneous erase
+{
+ std::multiset<X, cmp> aset{cmp{}};
+ aset.insert({X{"abc"}, X{"def"}, X{"def"}, X{"ghi"}});
+ auto n = aset.erase(Y{std::string_view{"def"}});
+ VERIFY(n == 2);
+ VERIFY(aset.size() == 2);
+}
+
+void test3() // uniform extract
+{
+ std::multiset<X, cmp> aset{cmp{}};
+ aset.insert({X{"abc"}, X{"def"}, X{"def"}, X{"ghi"}});
+ const auto node = aset.extract(X{std::string{"def"}});
+ VERIFY(node.value().s == "def");
+ VERIFY(aset.size() == 3);
+}
+
+void test4() // heterogeneous extract
+{
+ std::multiset<X, cmp> aset{cmp{}};
+ aset.insert({X{"abc"}, X{"def"}, X{"def"}, X{"ghi"}});
+ const auto node = aset.extract(Y{std::string_view{"def"}});
+ VERIFY(node.value().s == "def");
+ VERIFY(aset.size() == 3);
+}
+
+struct Z {
+ std::string_view s;
+ friend auto operator<=>(X const& a, Z const& b) {
+ int cmp = std::memcmp(a.s.data(), b.s.data(), 3);
+ return cmp < 0 ? std::strong_ordering::less :
+ cmp == 0 ? std::strong_ordering::equal :
+ std::strong_ordering::greater;
+ }
+};
+
+void test5()
+{
+ std::multiset<X, cmp> aset{cmp{}};
+ aset.insert({X{"abcdef"}, X{"defghi"}, X{"defjkl"}, X{"jklmno"}});
+ auto n = aset.erase(Z{std::string_view{"def"}});
+ VERIFY(n == 2);
+ VERIFY(aset.size() == 2);
+}
+
+int main()
+{
+ test1();
+ test2();
+ test3();
+ test4();
+ test5();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/set/modifiers/hetero/erase.cc
b/libstdc++-v3/testsuite/23_containers/set/modifiers/hetero/erase.cc
new file mode 100644
index 00000000000..8377a3f5728
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/set/modifiers/hetero/erase.cc
@@ -0,0 +1,88 @@
+// { dg-do run { target c++23 } }
+
+#include <set>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <compare>
+#include <cstring>
+#include <testsuite_hooks.h>
+
+struct X {
+ std::string s;
+ friend auto operator<=>(X const& a, X const& b) = default;
+};
+
+struct Y {
+ std::string_view s;
+ Y(std::string_view sv) : s(sv) {}
+ Y(std::string const& sv) : s(sv) {}
+ friend auto operator<=>(Y const& a, Y const& b) = default;
+ friend auto operator<=>(X const& a, Y const& b) { return a.s <=> b.s; }
+};
+
+using cmp = std::less<void>;
+
+void test1() // uniform erase
+{
+ std::set<X, cmp> aset{cmp{}};
+ aset.insert({X{"abc"}, X{"def"}, X{"ghi"}});
+ auto n = aset.erase(X{std::string{"def"}});
+ VERIFY(n == 1);
+ VERIFY(aset.size() == 2);
+}
+
+void test2() // heterogeneous erase
+{
+ std::set<X, cmp> aset{cmp{}};
+ aset.insert({X{"abc"}, X{"def"}, X{"ghi"}});
+ auto n = aset.erase(Y{std::string_view{"def"}});
+ VERIFY(n == 1);
+ VERIFY(aset.size() == 2);
+}
+
+void test3() // uniform extract
+{
+ std::set<X, cmp> aset{cmp{}};
+ aset.insert({X{"abc"}, X{"def"}, X{"ghi"}});
+ auto node = aset.extract(X{std::string{"def"}});
+ VERIFY(node.value().s == X{"def"}.s);
+ VERIFY(aset.size() == 2);
+}
+
+void test4() // heterogeneous extract
+{
+ std::set<X, cmp> aset{cmp{}};
+ aset.insert({X{"abc"}, X{"def"}, X{"ghi"}});
+ auto node = aset.extract(Y{std::string_view{"def"}});
+ VERIFY(node.value().s == X{"def"}.s);
+ VERIFY(aset.size() == 2);
+}
+
+struct Z {
+ std::string_view s;
+ friend auto operator<=>(X const& a, Z const& b) {
+ int cmp = std::memcmp(a.s.data(), b.s.data(), 3);
+ return cmp < 0 ? std::strong_ordering::less :
+ cmp == 0 ? std::strong_ordering::equal :
+ std::strong_ordering::greater;
+ }
+};
+
+void test5()
+{
+ std::set<X, cmp> aset{cmp{}};
+ aset.insert({X{"abcdef"}, X{"defghi"}, X{"defjkl"}, X{"jklmno"}});
+ auto n = aset.erase(Z{std::string_view{"def"}});
+ VERIFY(n == 2);
+ VERIFY(aset.size() == 2);
+}
+
+int main()
+{
+ test1();
+ test2();
+ test3();
+ test4();
+ test5();
+}
diff --git
a/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/hetero/erase.cc
b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/hetero/erase.cc
new file mode 100644
index 00000000000..976b574fde2
--- /dev/null
+++
b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/hetero/erase.cc
@@ -0,0 +1,76 @@
+// { dg-do run { target c++23 } }
+
+#include <unordered_map>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <functional>
+#include <compare>
+#include <testsuite_hooks.h>
+
+struct X {
+ std::string s;
+ friend bool operator==(X const& a, X const& b) = default;
+};
+
+struct Y {
+ std::string_view s;
+ Y(std::string_view sv) : s(sv) {}
+ Y(std::string const& sv) : s(sv) {}
+ friend bool operator==(Y const& a, Y const& b) = default;
+ friend bool operator==(X const& a, Y const& b) { return a.s == b.s; }
+};
+
+struct Hash {
+ using is_transparent = void;
+ template <typename T>
+ auto operator()(T const& t) const { return
std::hash<decltype(T::s)>{}(t.s); }
+};
+
+using Equal = std::equal_to<void>;
+
+void test1() // uniform erase
+{
+ std::unordered_map<X, int, Hash, Equal> amap;
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+ auto n = amap. erase(X{ std::string{"def"}});
+ VERIFY(n == 1);
+ VERIFY(amap.size() == 2);
+}
+
+void test2() // heterogeneous erase
+{
+ std::unordered_map<X, int, Hash, Equal> amap;
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+ auto n = amap. erase(Y{ std::string_view{"def"}});
+ VERIFY(n == 1);
+ VERIFY(amap.size() == 2);
+}
+
+void test3() // uniform extract
+{
+ std::unordered_map<X, int, Hash, Equal> amap;
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+ auto node = amap. extract(X{ std::string{"def"}});
+ VERIFY(node.key().s == X{"def"}.s);
+ VERIFY(node.mapped() == 2);
+ VERIFY(amap.size() == 2);
+}
+
+void test4() // heterogeneous extract
+{
+ std::unordered_map<X, int, Hash, Equal> amap;
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+ auto node = amap. extract(Y{ std::string_view{"def"}});
+ VERIFY(node.key().s == X{"def"}.s);
+ VERIFY(node.mapped() == 2);
+ VERIFY(amap.size() == 2);
+}
+
+int main()
+{
+ test1();
+ test2();
+ test3();
+ test4();
+}
diff --git
a/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/hetero/erase.cc
b/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/hetero/erase.cc
new file mode 100644
index 00000000000..df8f2161aa6
--- /dev/null
+++
b/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/hetero/erase.cc
@@ -0,0 +1,75 @@
+// { dg-do run { target c++23 } }
+
+#include <unordered_map>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <functional>
+#include <testsuite_hooks.h>
+
+struct X {
+ std::string s;
+ friend bool operator==(X const& a, X const& b) = default;
+};
+
+struct Y {
+ std::string_view s;
+ Y(std::string_view sv) : s(sv) {}
+ Y(std::string const& sv) : s(sv) {}
+ friend bool operator==(Y const& a, Y const& b) = default;
+ friend bool operator==(X const& a, Y const& b) { return a.s == b.s; }
+};
+
+struct Hash {
+ using is_transparent = void;
+ template <typename T>
+ auto operator()(T const& t) const { return
std::hash<decltype(T::s)>{}(t.s); }
+};
+
+using Equal = std::equal_to<void>;
+
+void test1() // uniform erase
+{
+ std::unordered_multimap<X, int, Hash, Equal> amap;
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"def"}, 3}, {X{"ghi"}, 4}});
+ auto n = amap. erase(X{ std::string{"def"}});
+ VERIFY(n == 2);
+ VERIFY(amap.size() == 2);
+}
+
+void test2() // heterogeneous erase
+{
+ std::unordered_multimap<X, int, Hash, Equal> amap;
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"def"}, 3}, {X{"ghi"}, 4}});
+ auto n = amap. erase(Y{ std::string_view{"def"}});
+ VERIFY(n == 2);
+ VERIFY(amap.size() == 2);
+}
+
+void test3() // uniform extract
+{
+ std::unordered_multimap<X, int, Hash, Equal> amap;
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"def"}, 3}, {X{"ghi"}, 4}});
+ auto node = amap. extract(X{ std::string{"def"}});
+ VERIFY(node.key().s == X{"def"}.s);
+ VERIFY(node.mapped() == 2 || node.mapped() == 3);
+ VERIFY(amap.size() == 3);
+}
+
+void test4() // heterogeneous extract
+{
+ std::unordered_multimap<X, int, Hash, Equal> amap;
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"def"}, 3}, {X{"ghi"}, 4}});
+ auto node = amap. extract(Y{ std::string_view{"def"}});
+ VERIFY(node.key().s == X{"def"}.s);
+ VERIFY(node.mapped() == 2 || node.mapped() == 3);
+ VERIFY(amap.size() == 3);
+}
+
+int main()
+{
+ test1();
+ test2();
+ test3();
+ test4();
+}
diff --git
a/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/hetero/erase.cc
b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/hetero/erase.cc
new file mode 100644
index 00000000000..e886abe2b54
--- /dev/null
+++
b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/hetero/erase.cc
@@ -0,0 +1,73 @@
+// { dg-do run { target c++23 } }
+
+#include <unordered_set>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <functional>
+#include <testsuite_hooks.h>
+
+struct X {
+ std::string s;
+ friend bool operator==(X const& a, X const& b) = default;
+};
+
+struct Y {
+ std::string_view s;
+ Y(std::string_view sv) : s(sv) {}
+ Y(std::string const& sv) : s(sv) {}
+ friend bool operator==(Y const& a, Y const& b) = default;
+ friend bool operator==(X const& a, Y const& b) { return a.s == b.s; }
+};
+
+struct Hash {
+ using is_transparent = void;
+ template <typename T>
+ auto operator()(T const& t) const { return
std::hash<decltype(T::s)>{}(t.s); }
+};
+
+using Equal = std::equal_to<void>;
+
+void test1() // uniform erase
+{
+ std::unordered_multiset<X, Hash, Equal> aset;
+ aset.insert({X{"abc"}, X{"def"}, X{"def"}, X{"ghi"}});
+ auto n = aset. erase(X{ std::string{"def"}});
+ VERIFY(n == 2);
+ VERIFY(aset.size() == 2);
+}
+
+void test2() // heterogeneous erase
+{
+ std::unordered_multiset<X, Hash, Equal> aset;
+ aset.insert({X{"abc"}, X{"def"}, X{"def"}, X{"ghi"}});
+ auto n = aset. erase(Y{ std::string_view{"def"}});
+ VERIFY(n == 2);
+ VERIFY(aset.size() == 2);
+}
+
+void test3() // uniform extract
+{
+ std::unordered_multiset<X, Hash, Equal> aset;
+ aset.insert({X{"abc"}, X{"def"}, X{"def"}, X{"ghi"}});
+ auto node = aset. extract(X{ std::string{"def"}});
+ VERIFY(node.value().s == X{"def"}.s);
+ VERIFY(aset.size() == 3);
+}
+
+void test4() // heterogeneous extract
+{
+ std::unordered_multiset<X, Hash, Equal> aset;
+ aset.insert({X{"abc"}, X{"def"}, X{"def"}, X{"ghi"}});
+ auto node = aset. extract(Y{ std::string_view{"def"}});
+ VERIFY(node.value().s == X{"def"}.s);
+ VERIFY(aset.size() == 3);
+}
+
+int main()
+{
+ test1();
+ test2();
+ test3();
+ test4();
+}
diff --git
a/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/hetero/erase.cc
b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/hetero/erase.cc
new file mode 100644
index 00000000000..6b60fa40198
--- /dev/null
+++
b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/hetero/erase.cc
@@ -0,0 +1,73 @@
+// { dg-do run { target c++23 } }
+
+#include <unordered_set>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <functional>
+#include <testsuite_hooks.h>
+
+struct X {
+ std::string s;
+ friend bool operator==(X const& a, X const& b) = default;
+};
+
+struct Y {
+ std::string_view s;
+ Y(std::string_view sv) : s(sv) {}
+ Y(std::string const& sv) : s(sv) {}
+ friend bool operator==(Y const& a, Y const& b) = default;
+ friend bool operator==(X const& a, Y const& b) { return a.s == b.s; }
+};
+
+struct Hash {
+ using is_transparent = void;
+ template <typename T>
+ auto operator()(T const& t) const { return
std::hash<decltype(T::s)>{}(t.s); }
+};
+
+using Equal = std::equal_to<void>;
+
+void test1() // uniform erase
+{
+ std::unordered_set<X, Hash, Equal> aset;
+ aset.insert({X{"abc"}, X{"def"}, X{"ghi"}});
+ auto n = aset.erase(X{std::string{"def"}});
+ VERIFY(n == 1);
+ VERIFY(aset.size() == 2);
+}
+
+void test2() // heterogeneous erase
+{
+ std::unordered_set<X, Hash, Equal> aset;
+ aset.insert({X{"abc"}, X{"def"}, X{"ghi"}});
+ auto n = aset.erase(Y{std::string_view{"def"}});
+ VERIFY(n == 1);
+ VERIFY(aset.size() == 2);
+}
+
+void test3() // uniform extract
+{
+ std::unordered_set<X, Hash, Equal> aset;
+ aset.insert({X{"abc"}, X{"def"}, X{"ghi"}});
+ auto node = aset.extract(X{std::string{"def"}});
+ VERIFY(node.value().s == X{"def"}.s);
+ VERIFY(aset.size() == 2);
+}
+
+void test4() // heterogeneous extract
+{
+ std::unordered_set<X, Hash, Equal> aset;
+ aset.insert({X{"abc"}, X{"def"}, X{"ghi"}});
+ auto node = aset.extract(Y{std::string_view{"def"}});
+ VERIFY(node.value().s == X{"def"}.s);
+ VERIFY(aset.size() == 2);
+}
+
+int main()
+{
+ test1();
+ test2();
+ test3();
+ test4();
+}
--
2.52.0
