On Thu, 11 Dec 2025 at 13:19 -0500, Nathan Myers wrote:
Changes in v3:
* Implement permissive matching for het erase on {,multi}{set,map},
remove now unused _M_erase_unique_tr, test.
* Adjust indent on erase_some.
* Remove copyright decls from tests.
* Use (defaulted) operator<=> in tree tests.
* Rename tests for content rather than paper number.
* Remove hashtable.h change meant for p2363.
Remaining to do:
* Add new declarations in debug headers too.
Changes in v2:
* Remove excess remove_reference<> and remove_cxref<> in new concepts.
* Reorder terms in concept expressions to favor short-circuiting
evaluation in common cases.
* Declare with "template <concept ..." so that users' types are named
in error messages.
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.
Header inclusion order is adjusted to make version.h symbols
available in more places.
libstdc++-v3/ChangeLog:
PR libstdc++/117404
* include/bits/version.def: Add feature macro
__cpplib_heterogeneous_erasure.
Please name the thing being added using the usual ChangeLog format
described at
https://www.gnu.org/prep/standards/html_node/Style-of-Change-Logs.html
* filename (name_of_thing): Define.
But also __cpplib_heterogeneous_erasure isn't the right name.
So:
* 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: Add specified new overloads.
This should say which 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.
* include/bits/unordered_set.h: Same.
* include/bits/hashtable.h: Add supporting overloads, new concept
__heterogeneous_hash_key.
Ditto, and then add:
(__heterogeneous_hash_key): New concept.
* include/bits/stl_tree.h: Add supporting overloads, new concept
__heterogeneous_tree_key.
* include/bits/stl_function.h: Add concepts __not_container_iterator and
__heterogeneous_key.
* 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 | 182 +++++++++++++++---
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 | 96 ++++++++-
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 | 12 +-
libstdc++-v3/include/std/map | 22 +--
libstdc++-v3/include/std/set | 19 +-
libstdc++-v3/include/std/unordered_map | 19 +-
libstdc++-v3/include/std/unordered_set | 17 +-
.../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, 1102 insertions(+), 72 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 06cc51ac4a0..bd5c9dc64e5 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -905,6 +905,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__location_type
_M_locate(const key_type& __k) const;
+ // We would like to extend _M_locate for heterogeneous
+ // keys, and use try_emplace as is, but ABI forbids it.
Why? Because of explicit instantiations, or something else?
+ template <typename _HetKey>
We use _Kt everywhere else for heterogeneous key parameters. The fact
it's a template parameter (rather than just using _Key or key_type)
already implies it's a heterogeneous key type.
+ __location_type
+ _M_locate_tr(const _HetKey& __k) const;
Should this be guarded by __glibcxx_associative_heterogeneous_erasure ?
Patch v2 called _M_locate_tr from pre-C++23 code, but v3 doesn't seem
to.
+
__node_ptr
_M_find_node(size_type __bkt, const key_type& __key,
__hash_code __c) const
@@ -1016,6 +1022,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 +1172,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
size_type
erase(const key_type& __k);
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
We don't put the paper number on these feature test checks anywhere
else in our headers.
+ template <typename _HetKey>
+ size_type
+ _M_erase_tr(const _HetKey& __k);
+#endif
+
iterator
erase(const_iterator, const_iterator);
@@ -1283,6 +1298,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return __nh;
}
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ template <typename _HetKey>
+ node_type
+ _M_extract_tr(const _HetKey& __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;
+ }
+#endif
+
/// Merge from another container of the same type.
void
_M_merge_unique(_Hashtable& __src)
@@ -2289,6 +2319,43 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return __loc;
}
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
+ template <typename _HetKey>
+ inline auto
+ _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
+ _M_locate_tr(const _HetKey& __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_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_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_tr(
+ __loc._M_bucket_index, __k, __loc._M_hash_code);
+
+ return __loc;
+ }
+
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
typename _Hash, typename _RangeHash, typename _Unused,
@@ -2598,6 +2665,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 +2685,89 @@ _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;
}
+
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
+ template <typename _HetKey>
+ auto
+ _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
+ _M_erase_tr(const _HetKey& __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);
+ }
+#endif // P2207
This should definitely not be the paper number here, but the macro
name (omitting the prefix if you want to keep it brief):
# endif // associative_heterogeneous_erasure
+
#pragma GCC diagnostic pop
template<typename _Key, typename _Value, typename _Alloc,
@@ -2977,6 +3087,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
= __enable_if_t<!__or_<is_integral<_Hash>, __is_allocator<_Hash>>::value>;
#endif
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+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 ff3f8f4c6e7..7f99ffe1566 100644
--- a/libstdc++-v3/include/bits/stl_function.h
+++ b/libstdc++-v3/include/bits/stl_function.h
@@ -1486,6 +1486,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
#endif
#endif
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+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>;
Do you need to add the && here when __not_container_iterator
explicitly adds it again?
+#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 62d66cef6b2..686ab792399 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 <bits/stl_tree.h>
If this is included here, it doesn't need to be included in <regex>
prior to including stl_map.h.
+ ///@{
/**
* @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); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ // 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 b2ae2bae745..7576653c8b9 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>
Adding this is redundant. stl_multimap.h is included in exactly one
file, <map>, and that includes stl_tree.h before it includes stl_map.h
and stl_multimap.h
Although GCC optimizes includes to avoid reopening the file on disk,
we now do #include <bits/stl_tree.h> three times in <set> and three
times in <map>.
The only reason that a "single use" header like stl_set.h needs to be
self-sufficient in terms of "include what you use" is if you are
compiling individual bits/*.h headers as header units so they can be
imported, which Nathan Sidwell was at one time making changes to
support.
I have a weak preference for not adding these redundant includes.
P.S. oh I see later in the patch that including bits/stl_tree.h is
removed from <map> and <set>, so it's only being included twice now,
not three times as I said above. So that's less bad.
namespace std _GLIBCXX_VISIBILITY(default)
{
@@ -679,6 +680,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
extract(const key_type& __x)
{ return _M_t.extract(__x); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ 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
namespace std _GLIBCXX_VISIBILITY(default)
{
@@ -688,6 +689,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
extract(const key_type& __x)
{ return _M_t.extract(__x); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ 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); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ 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 b6e1bfc4246..49539616615 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>
namespace std _GLIBCXX_VISIBILITY(default)
{
@@ -621,6 +622,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
extract(const key_type& __x)
{ return _M_t.extract(__x); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ 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); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ 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 f03d9e54d33..57fdce37434 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>
namespace std _GLIBCXX_VISIBILITY(default)
{
@@ -639,6 +640,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
extract(const key_type& __x)
{ return _M_t.extract(__x); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ 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); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ // 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 e78fa1dbfb3..5f977835c84 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -1399,8 +1399,8 @@ namespace __rb_tree
#if __cplusplus >= 201103L
// 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"
+ __is_invocable<const _Compare&, const _Key1&, const _Key2&>::value,
+ "comparison object must be invocable with key types used"
IIRC I made this function a template so the static_assert would only
be checked if a comparison was actually performed (so not checked for
the default constructor and destructor, for example). But the fact
that it tested invocation with _Key not with _Key1 and _Key2 was
intentional. The point of this static_assert is to check that _Compare
accepts arguments of type const _Key& because those are the template
parameters of the whole class.
Specifically, it was for diagnosing Gaby's example in
https://gcc.gnu.org/PR48101
So I'm not sure we need to generalize the assertion for all uses of
transparent comparators, but I suppose it doesn't hurt.
);
#endif
return _M_impl._M_key_compare(__k1, __k2);
@@ -1539,10 +1539,24 @@ namespace __rb_tree
_M_lower_bound(_Base_ptr __x, _Base_ptr __y,
const _Key& __k) const;
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ template <typename _HetKey>
Again, we just use _Kt for e.g. _Rb_tree::_M_find_tr
+ _Base_ptr
+ _M_lower_bound_tr(
+ _Base_ptr __x, _Base_ptr __y, const _HetKey& __k) const;
+#endif
+
_Base_ptr
_M_upper_bound(_Base_ptr __x, _Base_ptr __y,
const _Key& __k) const;
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ template <typename _HetKey>
+ _Base_ptr
+ _M_upper_bound_tr(
+ _Base_ptr __x, _Base_ptr __y, const _HetKey& __k) const;
+#endif
+
public:
// allocation/deallocation
#if __cplusplus < 201103L
@@ -1850,6 +1864,12 @@ namespace __rb_tree
size_type
erase(const key_type& __x);
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ template <typename _HetKey>
+ size_type
+ _M_erase_tr(const _HetKey& __x);
+#endif
+
size_type
_M_erase_unique(const key_type& __x);
@@ -2198,6 +2218,19 @@ namespace __rb_tree
return __nh;
}
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ template <typename _HetKey>
+ node_type
+ _M_extract_tr(const _HetKey& __k)
+ {
+ node_type __nh;
+ auto __pos = _M_find_tr(__k);
+ if (__pos != end())
+ __nh = extract(const_iterator(__pos));
+ return __nh;
+ }
+#endif
+
template<typename _Compare2>
using _Compatible_tree
= _Rb_tree<_Key, _Val, _KeyOfValue, _Compare2, _Alloc>;
@@ -2612,6 +2645,24 @@ namespace __rb_tree
return __y;
}
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ template<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ template <typename _HetKey>
+ auto
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_lower_bound_tr(_Base_ptr __x, _Base_ptr __y, const _HetKey& __k) const
+ -> _Base_ptr
+ {
+ while (__x)
+ if (!_M_key_compare(_S_key(__x), __k))
+ __y = __x, __x = _S_left(__x);
+ else
+ __x = _S_right(__x);
+ return __y;
+ }
+#endif
+
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue,
@@ -2628,6 +2679,24 @@ namespace __rb_tree
return __y;
}
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ template<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ template <typename _HetKey>
+ auto
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_upper_bound_tr(_Base_ptr __x, _Base_ptr __y, const _HetKey& __k) const
+ -> _Base_ptr
+ {
+ while (__x)
+ if (_M_key_compare(__k, _S_key(__x)))
+ __y = __x, __x = _S_left(__x);
+ else
+ __x = _S_right(__x);
+ return __y;
+ }
+#endif
+
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
@@ -3142,6 +3211,22 @@ namespace __rb_tree
return __old_size - size();
}
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ template<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ template <typename _HetKey>
+ auto
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_erase_tr(const _HetKey& __x)
+ -> size_type
+ {
+ 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();
+ }
+#endif
+
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
@@ -3249,6 +3334,13 @@ namespace __rb_tree
};
#endif // C++17
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+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 b9b2772aaa9..c0b7f4efd83 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); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ 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); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ 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); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ 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); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ 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 29bc49a590a..15a4a978590 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); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ 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); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ 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); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ 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); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ 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 04232187965..e3b9627b022 100644
--- a/libstdc++-v3/include/bits/version.def
+++ b/libstdc++-v3/include/bits/version.def
@@ -1589,6 +1589,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 df7a291b05f..39f5d462550 100644
--- a/libstdc++-v3/include/bits/version.h
+++ b/libstdc++-v3/include/bits/version.h
@@ -1756,6 +1756,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
@@ -2198,7 +2208,7 @@
# define __cpp_lib_observable_checkpoint 202506L
# endif
# endif
-#endif /* !defined(__cpp_lib_observable_checkpoint) &&
defined(__glibcxx_want_observable_checkpoint) */
+#endif /* !defined(__cpp_lib_observable_checkpoint) */
This was already removed in late October. Please be sure to rebase
this patch to make sure it applies to current trunk.
#undef __glibcxx_want_observable_checkpoint
#if !defined(__cpp_lib_algorithm_default_value_type)
diff --git a/libstdc++-v3/include/std/map b/libstdc++-v3/include/std/map
index 6bfb53848ba..efdf915f081 100644
--- a/libstdc++-v3/include/std/map
+++ b/libstdc++-v3/include/std/map
@@ -59,9 +59,19 @@
#pragma GCC system_header
#endif
+#define __glibcxx_want_allocator_traits_is_always_equal
+#define __glibcxx_want_containers_ranges
+#define __glibcxx_want_erase_if
+#define __glibcxx_want_generic_associative_lookup
+#define __glibcxx_want_map_try_emplace
+#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>
Is there a reason to move these earlier?
The downside of doing this is that the __cpp_lib_xxx forms of the
macros are all defined while preprocessing the headers that follow,
not *only* for the code that appears directly in *this* header.
That's not necessarily a problem, but it makes it easier to
accidentally rely on #if __cpp_lib_xxx in other files which should
be relying on the #if __glibcxx_xxx form instead.
With the current ordering, the effects of the "want" macros are
limited to a smaller scope, just this file and user code that includes
it, but not all the other library internals this this file includes.
So the current ordering is intentional, not accidental, and this patch
doesn't mention any rationale for changing that.
#include <bits/requires_hosted.h> // containers
This one should certainly be first, it just has a #error for
non-hosted. We want the "die or continue" header to be first, before
we waste time processing any other code.
-#include <bits/stl_tree.h>
#include <bits/stl_map.h>
#include <bits/stl_multimap.h>
#include <bits/range_access.h>
@@ -71,16 +81,6 @@
# include <debug/map>
#endif
-#define __glibcxx_want_allocator_traits_is_always_equal
-#define __glibcxx_want_containers_ranges
-#define __glibcxx_want_erase_if
-#define __glibcxx_want_generic_associative_lookup
-#define __glibcxx_want_map_try_emplace
-#define __glibcxx_want_node_extract
-#define __glibcxx_want_nonmember_container_access
-#define __glibcxx_want_tuple_like
-#include <bits/version.h>
-
#if __cplusplus >= 201703L
#include <bits/memory_resource.h>
namespace std _GLIBCXX_VISIBILITY(default)
diff --git a/libstdc++-v3/include/std/set b/libstdc++-v3/include/std/set
index cf7057aa6c6..0e6fb3e88c6 100644
--- a/libstdc++-v3/include/std/set
+++ b/libstdc++-v3/include/std/set
@@ -59,9 +59,18 @@
#pragma GCC system_header
#endif
+#define __glibcxx_want_allocator_traits_is_always_equal
+#define __glibcxx_want_containers_ranges
+#define __glibcxx_want_erase_if
+#define __glibcxx_want_generic_associative_lookup
+#define __glibcxx_want_node_extract
+#define __glibcxx_want_nonmember_container_access
+#define __glibcxx_want_associative_heterogeneous_erasure
+#define __glibcxx_want_associative_heterogeneous_insertion
+#include <bits/version.h>
+
#include <bits/requires_hosted.h> // containers
-#include <bits/stl_tree.h>
#include <bits/stl_set.h>
#include <bits/stl_multiset.h>
#include <bits/range_access.h>
@@ -71,14 +80,6 @@
# include <debug/set>
#endif
-#define __glibcxx_want_allocator_traits_is_always_equal
-#define __glibcxx_want_containers_ranges
-#define __glibcxx_want_erase_if
-#define __glibcxx_want_generic_associative_lookup
-#define __glibcxx_want_node_extract
-#define __glibcxx_want_nonmember_container_access
-#include <bits/version.h>
-
#if __cplusplus >= 201703L
#include <bits/memory_resource.h>
namespace std _GLIBCXX_VISIBILITY(default)
diff --git a/libstdc++-v3/include/std/unordered_map
b/libstdc++-v3/include/std/unordered_map
index 3ae25d758ac..783ead99a4b 100644
--- a/libstdc++-v3/include/std/unordered_map
+++ b/libstdc++-v3/include/std/unordered_map
@@ -39,15 +39,6 @@
# include <bits/c++0x_warning.h>
#else
-#include <initializer_list>
-#include <bits/unordered_map.h>
-#include <bits/range_access.h>
-#include <bits/erase_if.h>
-
-#ifdef _GLIBCXX_DEBUG
-# include <debug/unordered_map>
-#endif
-
#define __glibcxx_want_allocator_traits_is_always_equal
#define __glibcxx_want_containers_ranges
#define __glibcxx_want_erase_if
@@ -56,8 +47,18 @@
#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>
+#include <initializer_list>
+#include <bits/unordered_map.h>
+#include <bits/range_access.h>
+#include <bits/erase_if.h>
+
+#ifdef _GLIBCXX_DEBUG
+# include <debug/unordered_map>
+#endif
+
#if __cplusplus >= 201703L
#include <bits/memory_resource.h>
namespace std _GLIBCXX_VISIBILITY(default)
diff --git a/libstdc++-v3/include/std/unordered_set
b/libstdc++-v3/include/std/unordered_set
index b561163d31d..9dcecb050b0 100644
--- a/libstdc++-v3/include/std/unordered_set
+++ b/libstdc++-v3/include/std/unordered_set
@@ -39,6 +39,15 @@
# include <bits/c++0x_warning.h>
#else
+#define __glibcxx_want_allocator_traits_is_always_equal
+#define __glibcxx_want_containers_ranges
+#define __glibcxx_want_erase_if
+#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>
+
#include <initializer_list>
#include <bits/unordered_set.h>
#include <bits/range_access.h>
@@ -48,14 +57,6 @@
# include <debug/unordered_set>
#endif
-#define __glibcxx_want_allocator_traits_is_always_equal
-#define __glibcxx_want_containers_ranges
-#define __glibcxx_want_erase_if
-#define __glibcxx_want_generic_unordered_lookup
-#define __glibcxx_want_node_extract
-#define __glibcxx_want_nonmember_container_access
-#include <bits/version.h>
-
#if __cplusplus >= 201703L
#include <bits/memory_resource.h>
namespace std _GLIBCXX_VISIBILITY(default)
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..711ba05952c
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/map/modifiers/hetero/erase.cc
@@ -0,0 +1,95 @@
+// { dg-do compile { target c++23 } }
All these tests use dg-do compile but have main() functions. Those
main functions aren't going to run, so you're only testing that the
code compiles, not that it runs.
Presumably they should be dg-do run.
+
+#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..85610643801
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multimap/modifiers/hetero/erase.cc
@@ -0,0 +1,95 @@
+// { dg-do compile { 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..7da9cd0095b
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/hetero/erase.cc
@@ -0,0 +1,88 @@
+// { dg-do compile { 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..af7db5b7adb
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/set/modifiers/hetero/erase.cc
@@ -0,0 +1,88 @@
+// { dg-do compile { 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..c38b4550f36
--- /dev/null
+++
b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/hetero/erase.cc
@@ -0,0 +1,76 @@
+// { dg-do compile { 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..c9f418341b0
--- /dev/null
+++
b/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/hetero/erase.cc
@@ -0,0 +1,75 @@
+// { dg-do compile { 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..8c2d5c6d3a7
--- /dev/null
+++
b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/hetero/erase.cc
@@ -0,0 +1,73 @@
+// { dg-do compile { 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..fcf25faa724
--- /dev/null
+++
b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/hetero/erase.cc
@@ -0,0 +1,73 @@
+// { dg-do compile { 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.50.1
