Thank you.
On 11/12/25 4:12 AM, Tomasz Kaminski wrote:
On Sun, Nov 9, 2025 at 8:58 AM Nathan Myers <[email protected]
<mailto:[email protected]>> wrote:
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.
* 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.
The std/debug/files needs to be also updated. But you may do this as
separate commit.
Got it.
* include/bits/stl_map.h: Add specified new 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.
* include/bits/stl_tree.h: Add supporting overloads, new
concept
__heterogeneous_tree_key.
* include/bits/stl_function.h: Add concept __heterogeneous_key.
* testsuite/23_containers/map/modifiers/erase/p2077.cc: New
test.
* testsuite/23_containers/multimap/modifiers/erase/
p2077.cc: Same.
* testsuite/23_containers/multiset/modifiers/erase/
p2077.cc: Same.
* testsuite/23_containers/set/modifiers/erase/p2077.cc: Same.
* testsuite/23_containers/unordered_map/modifiers/p2077.cc:
Same.
* testsuite/23_containers/unordered_multimap/modifiers/
p2077.cc: Same.
* testsuite/23_containers/unordered_multiset/modifiers/
p2077.cc: Same.
* testsuite/23_containers/unordered_set/modifiers/p2077.cc:
Same.
---
libstdc++-v3/include/bits/hashtable.h | 139 ++++++++++++++++++
libstdc++-v3/include/bits/stl_function.h | 9 ++
libstdc++-v3/include/bits/stl_map.h | 13 ++
libstdc++-v3/include/bits/stl_multimap.h | 13 ++
libstdc++-v3/include/bits/stl_multiset.h | 13 ++
libstdc++-v3/include/bits/stl_set.h | 13 ++
libstdc++-v3/include/bits/stl_tree.h | 120 ++++++++++++++-
libstdc++-v3/include/bits/unordered_map.h | 24 +++
libstdc++-v3/include/bits/unordered_set.h | 24 +++
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/erase/p2077.cc | 91 ++++++++++++
.../multimap/modifiers/erase/p2077.cc | 91 ++++++++++++
.../multiset/modifiers/erase/p2077.cc | 85 +++++++++++
.../set/modifiers/erase/p2077.cc | 85 +++++++++++
.../unordered_map/modifiers/p2077.cc | 94 ++++++++++++
.../unordered_multimap/modifiers/p2077.cc | 94 ++++++++++++
.../unordered_multiset/modifiers/p2077.cc | 92 ++++++++++++
.../unordered_set/modifiers/p2077.cc | 92 ++++++++++++
23 files changed, 1149 insertions(+), 40 deletions(-)
create mode 100644 libstdc++-v3/testsuite/23_containers/map/
modifiers/erase/p2077.cc
create mode 100644 libstdc++-v3/testsuite/23_containers/multimap/
modifiers/erase/p2077.cc
create mode 100644 libstdc++-v3/testsuite/23_containers/multiset/
modifiers/erase/p2077.cc
create mode 100644 libstdc++-v3/testsuite/23_containers/set/
modifiers/erase/p2077.cc
create mode 100644 libstdc++-v3/testsuite/23_containers/
unordered_map/modifiers/p2077.cc
create mode 100644 libstdc++-v3/testsuite/23_containers/
unordered_multimap/modifiers/p2077.cc
create mode 100644 libstdc++-v3/testsuite/23_containers/
unordered_multiset/modifiers/p2077.cc
create mode 100644 libstdc++-v3/testsuite/23_containers/
unordered_set/modifiers/p2077.cc
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/
include/bits/hashtable.h
index 06cc51ac4a0..a8a844b40d8 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;
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ template <typename _HetKey>
+ __location_type
+ _M_locate_tr(const _HetKey& __k) const;
+#endif
+
__node_ptr
_M_find_node(size_type __bkt, const key_type& __key,
__hash_code __c) const
@@ -1163,6 +1169,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
size_type
erase(const key_type& __k);
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ template <typename _HetKey>
+ size_type
+ _M_erase_tr(const _HetKey& __k);
+#endif
+
iterator
erase(const_iterator, const_iterator);
@@ -1283,6 +1295,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 +2316,45 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return __loc;
}
+#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>
+ 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;
+ }
+#endif
+
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
typename _Hash, typename _RangeHash, typename _Unused,
@@ -2598,6 +2664,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,
@@ -2658,6 +2725,70 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
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)
equal(__k, __element) may form an equivalence relation, and there may be
more
than one element equal to __k even for non-multimap. Consider a
StringPrefix wrapper
over string_view, such comparison against the prefix of the string_view.
From what I read this
satisfies requirements on the key: https://eel.is/c++draft/
containers#associative.reqmts.general-7.23 <https://eel.is/c++draft/
containers#associative.reqmts.general-7.23>.
An erase is specified to remove all these elements: https://eel.is/c+
+draft/containers#associative.reqmts.general-123 <https://eel.is/c+
+draft/containers#associative.reqmts.general-123>.
Good catch! I will need to add tests for that usage.
It seems more tricky even than this, because the set of matching
elements need not be a contiguous range. I think we need to move
the nodes to be erased to a local bucket as they are discovered,
before freeing them.
In short, we need to do loop even for unique keys.
I would do something like:
__node_ptr __n_last = __n->_M_next();
while (__n_last && this->_M_node_equals(*__n, *__n_last))
__n_last = __n_last->_M_next();
if constexpr (__unique_keys::value)
if (_n->_M_next() == _n_last) [[likely]]
{
_M_erase(__bkt, __prev_n, __n);
return 1;
}
Or even without constexpr.
Yes.
+ {
+ _M_erase(__bkt, __prev_n, __n);
+ return 1;
+ }
+ else
+ {
+ // _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;
+ }
+ }
+#endif // P2207
#pragma GCC diagnostic pop
template<typename _Key, typename _Value, typename _Alloc,
@@ -2977,6 +3108,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 =
+ __heterogeneous_key<_Kt, remove_cvref_t<_Container>> &&
+ __transparent_comparator<typename
remove_cvref_t<_Container>::hasher> &&
+ __transparent_comparator<typename
remove_cvref_t<_Container>::key_equal>;
Because the operands on the && in concept are short-circuited I would
check the
__transparent_comparator<typename remove_cvref_t<_Container>::hasher>
__transparent_comparator<typename remove_cvref_t<_Container>::key_equal>
first, before __heterogeneous_hash_key. For given container
specialization they give the same
result, and the compiler caches the values of concepts, so we will exit
early, before checking is_convertible.
So concrete suggestion is:
+ concept __heterogeneous_hash_key =
+ __transparent_comparator<typename remove_cvref_t<_Container>::hasher> &&
+ __transparent_comparator<typename
remove_cvref_t<_Container>::key_equal> &&
+ __heterogeneous_key<_Kt, remove_cvref_t<_Container>>;
And similarly for __heterogeneous_tree_key in stl_tree.h.
Also do you need remove_cvref_t on _Container?
It is not needed for use in the container member functions, as
there the container type is provided explicitly, but when the
container is an argument, deduction adds a (spurious) ref.
The concept might end up used beyond just these headers.
But that anyway doesn't need the cv part.
+#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..2ee61e79f02 100644
--- a/libstdc++-v3/include/bits/stl_function.h
+++ b/libstdc++-v3/include/bits/stl_function.h
@@ -1486,6 +1486,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
#endif
#endif
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+template <typename _Kt, typename _Container>
+ concept __heterogeneous_key =
+ (!is_convertible_v<_Kt&&, typename _Container::iterator> &&
+ !is_convertible_v<_Kt&&, typename _Container::const_iterator> &&
+ !is_same_v<remove_cv_t<typename _Container::key_type>,
+ remove_cvref_t<_Kt>>);
I do not think you need remove_cv_t on key_type here.
Not for our containers, but maybe for others.
+#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..69d57df728a 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>
namespace std _GLIBCXX_VISIBILITY(default)
{
@@ -679,6 +680,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
extract(const key_type& __x)
{ return _M_t.extract(__x); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ node_type
+ extract(__heterogeneous_tree_key<map> auto&& __key)
I would suggest that you use an normal-template head here, as it gives
more readable error message,
for illustration see here https://godbolt.org/z/3rd4KoTE7 <https://
godbolt.org/z/3rd4KoTE7>:
<source>:7:10: note: candidate template ignored: constraints not
satisfied [with U = int]
7 | void usingRequires(U&&) {}
<source>:9:10: note: candidate template ignored: constraints not
satisfied [with x:auto = int]
9 | void usingAuto(Check auto&& x) {}
The [x::auto = int] is much more confusing, than just U&&. This apply
everywhere.
Anyway declaring it like
template <__heterogeneous_tree_key<map> _Kt>
node_type
extract(_Kt&& __key)
avoids that problem, without a separate "requires" line.
+ { return _M_t._M_extract_tr(__key); }
+#endif
+
/// Re-insert an extracted node.
insert_return_type
insert(node_type&& __nh)
@@ -1158,6 +1165,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
erase(const key_type& __x)
{ return _M_t._M_erase_unique(__x); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ size_type
+ erase(__heterogeneous_tree_key<map> auto&& __key)
+ { return _M_t._M_erase_unique_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_multimap.h b/libstdc++-
v3/include/bits/stl_multimap.h
index b2ae2bae745..4ba628ac7b4 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>
namespace std _GLIBCXX_VISIBILITY(default)
{
@@ -688,6 +689,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
extract(const key_type& __x)
{ return _M_t.extract(__x); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ node_type
+ extract(__heterogeneous_tree_key<multimap> auto&& __key)
+ { return _M_t._M_extract_tr(__key); }
+#endif
+
/// Re-insert an extracted node.
iterator
insert(node_type&& __nh)
@@ -787,6 +794,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
erase(const key_type& __x)
{ return _M_t.erase(__x); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ size_type
+ erase(__heterogeneous_tree_key<multimap> auto&& __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..49d12884bdf 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,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
extract(const key_type& __x)
{ return _M_t.extract(__x); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ node_type
+ extract(__heterogeneous_tree_key<multiset> auto&& __key)
+ { return _M_t._M_extract_tr(__key); }
+#endif
+
/// Re-insert an extracted node.
iterator
insert(node_type&& __nh)
@@ -712,6 +719,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
erase(const key_type& __x)
{ return _M_t.erase(__x); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ size_type
+ erase(__heterogeneous_tree_key<multiset> auto&& __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..8d675040bb7 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,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
extract(const key_type& __x)
{ return _M_t.extract(__x); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ node_type
+ extract(__heterogeneous_tree_key<set> auto&& __key)
+ { return _M_t._M_extract_tr(__key); }
+#endif
+
/// Re-insert an extracted node.
insert_return_type
insert(node_type&& __nh)
@@ -730,6 +737,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
erase(const key_type& __x)
{ return _M_t._M_erase_unique(__x); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ size_type
+ erase(__heterogeneous_tree_key<set> auto&& __key)
+ { return _M_t._M_erase_unique_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..5e922e426c6 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"
);
#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>
+ _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,9 +1864,21 @@ 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);
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ template<typename _HetKey>
+ size_type
+ _M_erase_unique_tr(const _HetKey& __x);
+#endif
+
#if __cplusplus >= 201103L
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 130. Associative erase should return an iterator.
@@ -2198,6 +2224,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 +2651,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 +2685,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 +3217,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
@@ -3156,6 +3247,24 @@ namespace __rb_tree
return 1;
}
+#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_unique_tr(const _HetKey& __x)
Again, similar comment, we need to erase all equivalent elements.
We can forward inside this function to _M_erase_tr for the moment, and
later see if we can get optimized
for one element case.
Right. I don't think trees have the problem that hash
tables have with possibly two or more discontiguous ranges.
+ -> size_type
+ {
+ iterator __it = _M_find_tr(__x);
+ if (__it == end())
+ return 0;
+
+ _M_erase_aux(__it);
+ return 1;
+ }
+#endif
+
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue,
@@ -3249,6 +3358,13 @@ namespace __rb_tree
};
#endif // C++17
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+template <typename _Kt, typename _Container>
+ concept __heterogeneous_tree_key =
+ __heterogeneous_key<_Kt, remove_cvref_t<_Container>> &&
+ __transparent_comparator<typename
remove_cvref_t<_Container>::key_compare>;
Put __transparent_comparation before __heterogeneous_key, for same
reason as above.
+#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..51ad049c2d1 100644
--- a/libstdc++-v3/include/bits/unordered_map.h
+++ b/libstdc++-v3/include/bits/unordered_map.h
@@ -501,6 +501,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
extract(const key_type& __key)
{ return _M_h.extract(__key); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ node_type
+ extract(__heterogeneous_hash_key<unordered_map> auto&& __key)
+ { return _M_h._M_extract_tr(__key); }
+#endif
+
/// Re-insert an extracted node.
insert_return_type
insert(node_type&& __nh)
@@ -848,6 +854,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
erase(const key_type& __x)
{ return _M_h.erase(__x); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ size_type
+ erase(__heterogeneous_hash_key<unordered_map> auto&& __key)
+ { return _M_h._M_erase_tr(__key); }
+#endif
+
/**
* @brief Erases a [__first,__last) range of elements from an
* %unordered_map.
@@ -1872,6 +1884,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
extract(const key_type& __key)
{ return _M_h.extract(__key); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ node_type
+ extract(__heterogeneous_hash_key<unordered_multimap> auto&&
__key)
+ { return _M_h._M_extract_tr(__key); }
+#endif
+
/// Re-insert an extracted node.
iterator
insert(node_type&& __nh)
@@ -1922,6 +1940,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
erase(const key_type& __x)
{ return _M_h.erase(__x); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ size_type
+ erase(__heterogeneous_hash_key<unordered_multimap> auto&& __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..b2c539ebbaa 100644
--- a/libstdc++-v3/include/bits/unordered_set.h
+++ b/libstdc++-v3/include/bits/unordered_set.h
@@ -581,6 +581,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
extract(const key_type& __key)
{ return _M_h.extract(__key); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ node_type
+ extract(__heterogeneous_hash_key<unordered_set> auto&& __key)
+ { return _M_h._M_extract_tr(__key); }
+#endif
+
/// Re-insert an extracted node.
insert_return_type
insert(node_type&& __nh)
@@ -632,6 +638,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
erase(const key_type& __x)
{ return _M_h.erase(__x); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ size_type
+ erase(__heterogeneous_hash_key<unordered_set> auto&& __key)
+ { return _M_h._M_erase_tr(__key); }
+#endif
+
/**
* @brief Erases a [__first,__last) range of elements from an
* %unordered_set.
@@ -1574,6 +1586,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
extract(const key_type& __key)
{ return _M_h.extract(__key); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ node_type
+ extract(__heterogeneous_hash_key<unordered_multiset> auto&&
__key)
+ { return _M_h._M_extract_tr(__key); }
+#endif
+
/// Re-insert an extracted node.
iterator
insert(node_type&& __nh)
@@ -1627,6 +1645,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
erase(const key_type& __x)
{ return _M_h.erase(__x); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ size_type
+ erase(__heterogeneous_hash_key<unordered_multiset> auto&& __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) */
#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>
+
#include <bits/requires_hosted.h> // containers
-#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/
erase/p2077.cc b/libstdc++-v3/testsuite/23_containers/map/modifiers/
erase/p2077.cc
new file mode 100644
index 00000000000..b64fe8abf82
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/map/modifiers/erase/p2077.cc
@@ -0,0 +1,91 @@
+// Copyright (C) 2011-2025 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public
License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/ <http://www.gnu.org/licenses/>>.
+//
+
+// { dg-do compile { target c++23 } }
+
+#include <map>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <testsuite_hooks.h>
+
+struct X {
+ std::string s;
+ friend bool operator<(X const& a, X const& b) { return a.s < b.s; }
+};
+
+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) { return a.s < b.s; }
+ friend bool operator<(X const& a, Y const& b) { return a.s < b.s; }
+ friend bool operator<(Y const& a, X 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);
+}
+
+int main()
+{
+ test1();
+ test2();
+ test3();
+ test4();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/multimap/
modifiers/erase/p2077.cc b/libstdc++-v3/testsuite/23_containers/
multimap/modifiers/erase/p2077.cc
new file mode 100644
index 00000000000..3fb6a421337
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multimap/modifiers/erase/
p2077.cc
@@ -0,0 +1,91 @@
+// Copyright (C) 2011-2025 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public
License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/ <http://www.gnu.org/licenses/>>.
+//
+
+// { dg-do compile { target c++23 } }
+
+#include <map>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <testsuite_hooks.h>
+
+struct X {
+ std::string s;
+ friend bool operator<(X const& a, X const& b) { return a.s < b.s; }
+};
+
+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) { return a.s < b.s; }
+ friend bool operator<(X const& a, Y const& b) { return a.s < b.s; }
+ friend bool operator<(Y const& a, X 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);
+}
+
+int main()
+{
+ test1();
+ test2();
+ test3();
+ test4();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/multiset/
modifiers/erase/p2077.cc b/libstdc++-v3/testsuite/23_containers/
multiset/modifiers/erase/p2077.cc
new file mode 100644
index 00000000000..10a3cc07b2d
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multiset/modifiers/erase/
p2077.cc
@@ -0,0 +1,85 @@
+// Copyright (C) 2011-2025 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public
License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/ <http://www.gnu.org/licenses/>>.
+//
+
+// { dg-do compile { target c++23 } }
+
+#include <set>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <testsuite_hooks.h>
+
+struct X {
+ std::string s;
+ friend bool operator<(X const& a, X const& b) { return a.s < b.s; }
+};
+
+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) { return a.s < b.s; }
+ friend bool operator<(X const& a, Y const& b) { return a.s < b.s; }
+ friend bool operator<(Y const& a, X 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);
+}
+
+int main()
+{
+ test1();
+ test2();
+ test3();
+ test4();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/set/modifiers/
erase/p2077.cc b/libstdc++-v3/testsuite/23_containers/set/modifiers/
erase/p2077.cc
new file mode 100644
index 00000000000..3de72a66540
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/set/modifiers/erase/p2077.cc
@@ -0,0 +1,85 @@
+// Copyright (C) 2011-2025 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public
License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/ <http://www.gnu.org/licenses/>>.
+//
+
+// { dg-do compile { target c++23 } }
+
+#include <set>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <testsuite_hooks.h>
+
+struct X {
+ std::string s;
+ friend bool operator<(X const& a, X const& b) { return a.s < b.s; }
+};
+
+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) { return a.s < b.s; }
+ friend bool operator<(X const& a, Y const& b) { return a.s < b.s; }
+ friend bool operator<(Y const& a, X 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);
+}
+
+int main()
+{
+ test1();
+ test2();
+ test3();
+ test4();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/
modifiers/p2077.cc b/libstdc++-v3/testsuite/23_containers/
unordered_map/modifiers/p2077.cc
new file mode 100644
index 00000000000..a22eb993b2b
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/
p2077.cc
@@ -0,0 +1,94 @@
+// Copyright (C) 2011-2025 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public
License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/ <http://www.gnu.org/licenses/>>.
+//
+
+// { 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) { return a.s == b.s; }
+};
+
+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) { return a.s == b.s; }
+ friend bool operator==(X const& a, Y const& b) { return a.s == b.s; }
+ friend bool operator==(Y const& a, X 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/p2077.cc b/libstdc++-v3/
testsuite/23_containers/unordered_multimap/modifiers/p2077.cc
new file mode 100644
index 00000000000..3a455b2d701
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/
modifiers/p2077.cc
@@ -0,0 +1,94 @@
+// Copyright (C) 2011-2025 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public
License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/ <http://www.gnu.org/licenses/>>.
+//
+
+// { 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) { return a.s == b.s; }
+};
+
+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) { return a.s == b.s; }
+ friend bool operator==(X const& a, Y const& b) { return a.s == b.s; }
+ friend bool operator==(Y const& a, X 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/p2077.cc b/libstdc++-v3/
testsuite/23_containers/unordered_multiset/modifiers/p2077.cc
new file mode 100644
index 00000000000..671ba8c173e
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/
modifiers/p2077.cc
@@ -0,0 +1,92 @@
+// Copyright (C) 2011-2025 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public
License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/ <http://www.gnu.org/licenses/>>.
+//
+
+// { 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) { return a.s == b.s; }
+};
+
+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) { return a.s == b.s; }
+ friend bool operator==(X const& a, Y const& b) { return a.s == b.s; }
+ friend bool operator==(Y const& a, X 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/p2077.cc b/libstdc++-v3/testsuite/23_containers/
unordered_set/modifiers/p2077.cc
new file mode 100644
index 00000000000..b4f8dd0284c
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/
p2077.cc
@@ -0,0 +1,92 @@
+// Copyright (C) 2011-2025 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public
License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/ <http://www.gnu.org/licenses/>>.
+//
+
+// { 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) { return a.s == b.s; }
+};
+
+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) { return a.s == b.s; }
+ friend bool operator==(X const& a, Y const& b) { return a.s == b.s; }
+ friend bool operator==(Y const& a, X 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
