Changes in v2:
* Remove excess remove_reference<> and remove_cxref<> in new
concept definitions.
* Reorder terms in concept expressions to favor short-circuit
evaluation in common cases.
* Add a new concept __not_container_iterator<_Kt, _Container>
for use in __heterogeneous_key<_Kt, _Container>.
* Declare new overloads with "template <__concept ..." so that
users' type substitutions are named in error messages.
* Fix up a doc annotation so existing language applies to new
overloads.
* Define a new _Hashtable<>::erase_some called from existing erase
and new heterogeneous-key _M_erase_tr.
Remaining to do:
* Add new declarations in debug headers too.
Implement C++23 P2077R3 "Heterogeneous erasure overloads for
associative containers". Adds template overloads for members
erase and extract to address elements using an alternative key
type, such as string_view for a container of strings, without
need to construct an actual key object.
The new overloads enforce concept __heterogeneous_tree_key or
__heterogeneous_hash_key to verify the function objects provided
meet requirements, and that the key supplied is not an iterator
or the native key.
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.
* 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 concepts __not_container_iterator and
__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 | 126 +++++++++++++++++-
libstdc++-v3/include/bits/stl_function.h | 12 ++
libstdc++-v3/include/bits/stl_map.h | 17 +++
libstdc++-v3/include/bits/stl_multimap.h | 15 +++
libstdc++-v3/include/bits/stl_multiset.h | 15 +++
libstdc++-v3/include/bits/stl_set.h | 15 +++
libstdc++-v3/include/bits/stl_tree.h | 120 ++++++++++++++++-
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/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, 1153 insertions(+), 44 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..cc992d8b48b 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.
+ template <typename _HetKey>
+ __location_type
+ _M_locate_tr(const _HetKey& __k) const;
+
__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);
@@ -1088,7 +1097,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
__hash_code __code;
size_type __bkt;
- if (auto __loc = _M_locate(__k))
+ if (auto __loc = _M_locate_tr(__k))
return { iterator(__loc), false };
else
{
@@ -1163,6 +1172,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 +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,14 +2685,25 @@ _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?
@@ -2656,8 +2735,39 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_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
+
#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>;
+#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..9c9f6d4cfc7 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,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
+ ///@{
/**
* @brief Erases elements according to the provided key.
* @param __x Key of element to be erased.
@@ -1158,6 +1167,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
erase(const key_type& __x)
{ return _M_t._M_erase_unique(__x); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ template <__heterogeneous_tree_key<map> _Kt>
+ size_type
+ erase(_Kt&& __x)
+ { return _M_t._M_erase_unique_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>
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..90301a28711 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,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
erase(const key_type& __x)
{ return _M_t._M_erase_unique(__x); }
+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+ template <__heterogeneous_tree_key<set> _Kt>
+ size_type
+ erase(_Kt&& __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..1c1eae1833f 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)
+ -> 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 =
+ __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) */
#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/>.
+//
+
+// { 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/>.
+//
+
+// { 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/>.
+//
+
+// { 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/>.
+//
+
+// { 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/>.
+//
+
+// { 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/>.
+//
+
+// { 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/>.
+//
+
+// { 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/>.
+//
+
+// { 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
