[PATCHv3] libstdc++: container erasure overloads (P2077) [PR117404]
Jonathan Wakely
jwakely@redhat.com
Mon Jan 26 16:29:16 GMT 2026
On Mon, 26 Jan 2026 at 15:57, Jonathan Wakely <jwakely@redhat.com> wrote:
>
> On Fri, 23 Jan 2026 at 20:05 -0500, Nathan Myers wrote:
> >Thank you.
> >
> >On 1/23/26 12:48 PM, Jonathan Wakely wrote:
> >>On Thu, 11 Dec 2025 at 13:19 -0500, Nathan Myers wrote:
> >>>...
> >>>libstdc++-v3/ChangeLog:
> >>> PR libstdc++/117404
> >>> * include/bits/version.def: Add feature macro
> >>> __cpplib_heterogeneous_erasure.
> >>
> >>Please name the thing being added using the usual ChangeLog format
> >>described at https://www.gnu.org/prep/standards/html_node/Style-of-
> >>Change-Logs.html
> >>
> >> * filename (name_of_thing): Define.
> >>
> >>But also __cpplib_heterogeneous_erasure isn't the right name.
> >>
> >>So:
> >>
> >> * include/bits/version.def (associative_heterogeneous_erasure):
> >> Define.
> >
> >OK.
> >
> >>> * include/bits/version.h: Regenerate.
> >>> * include/std/map: Request new feature from version.h.
> >>> * include/std/set: Same.
> >>> * include/std/unordered_map: Same.
> >>> * include/std/unordered_set: Same.
> >>> * include/bits/stl_map.h: Add specified new overloads.
> >>
> >>This should say which overloads.
> >
> >OK.
> >
> >>> * include/bits/stl_set.h: Same.
> >>> * include/bits/stl_multimap.h: Same.
> >>> * include/bits/stl_multiset.h: Same.
> >>> * include/bits/unordered_map.h: Same.
> >>> * include/bits/unordered_set.h: Same.
> >>> * include/bits/hashtable.h: Add supporting overloads, new concept
> >>> __heterogeneous_hash_key.
> >>
> >>Ditto, and then add:
> >>
> >> (__heterogeneous_hash_key): New concept.
> >
> >OK
> >
> >>> * include/bits/stl_tree.h: Add supporting overloads, new concept
> >>> __heterogeneous_tree_key.
> >>> * include/bits/stl_function.h: Add concepts
> >>>__not_container_iterator and
> >>> __heterogeneous_key.
> >>> * testsuite/23_containers/map/modifiers/hetero/erase.cc: New test.
> >>> * testsuite/23_containers/multimap/modifiers/hetero/erase.cc: Same.
> >>> * testsuite/23_containers/multiset/modifiers/hetero/erase.cc: Same.
> >>> * testsuite/23_containers/set/modifiers/hetero/erase.cc: Same.
> >>> *
> >>>testsuite/23_containers/unordered_map/modifiers/hetero/erase.cc:
> >>>Same.
> >>> * testsuite/23_containers/unordered_multimap/modifiers/hetero/
> >>>erase.cc:
> >>> Same.
> >>> * testsuite/23_containers/unordered_multiset/modifiers/hetero/
> >>>erase.cc:
> >>> Same.
> >>> *
> >>>testsuite/23_containers/unordered_set/modifiers/hetero/erase.cc:
> >>>Same.
> >>>---
> >>>libstdc++-v3/include/bits/hashtable.h | 182 +++++++++++++++---
> >>>libstdc++-v3/include/bits/stl_function.h | 12 ++
> >>>libstdc++-v3/include/bits/stl_map.h | 20 ++
> >>>libstdc++-v3/include/bits/stl_multimap.h | 15 ++
> >>>libstdc++-v3/include/bits/stl_multiset.h | 15 ++
> >>>libstdc++-v3/include/bits/stl_set.h | 18 ++
> >>>libstdc++-v3/include/bits/stl_tree.h | 96 ++++++++-
> >>>libstdc++-v3/include/bits/unordered_map.h | 28 +++
> >>>libstdc++-v3/include/bits/unordered_set.h | 28 +++
> >>>libstdc++-v3/include/bits/version.def | 8 +
> >>>libstdc++-v3/include/bits/version.h | 12 +-
> >>>libstdc++-v3/include/std/map | 22 +--
> >>>libstdc++-v3/include/std/set | 19 +-
> >>>libstdc++-v3/include/std/unordered_map | 19 +-
> >>>libstdc++-v3/include/std/unordered_set | 17 +-
> >>>.../map/modifiers/hetero/erase.cc | 95 +++++++++
> >>>.../multimap/modifiers/hetero/erase.cc | 95 +++++++++
> >>>.../multiset/modifiers/hetero/erase.cc | 88 +++++++++
> >>>.../set/modifiers/hetero/erase.cc | 88 +++++++++
> >>>.../unordered_map/modifiers/hetero/erase.cc | 76 ++++++++
> >>>.../modifiers/hetero/erase.cc | 75 ++++++++
> >>>.../modifiers/hetero/erase.cc | 73 +++++++
> >>>.../unordered_set/modifiers/hetero/erase.cc | 73 +++++++
> >>>23 files changed, 1102 insertions(+), 72 deletions(-)
> >>>create mode 100644
> >>>libstdc++-v3/testsuite/23_containers/map/modifiers/
> >>>hetero/erase.cc
> >>>create mode 100644 libstdc++-v3/testsuite/23_containers/multimap/
> >>>modifiers/hetero/erase.cc
> >>>create mode 100644 libstdc++-v3/testsuite/23_containers/multiset/
> >>>modifiers/hetero/erase.cc
> >>>create mode 100644
> >>>libstdc++-v3/testsuite/23_containers/set/modifiers/
> >>>hetero/erase.cc
> >>>create mode 100644
> >>>libstdc++-v3/testsuite/23_containers/unordered_map/
> >>>modifiers/hetero/erase.cc
> >>>create mode 100644 libstdc++-v3/testsuite/23_containers/
> >>>unordered_multimap/modifiers/hetero/erase.cc
> >>>create mode 100644 libstdc++-v3/testsuite/23_containers/
> >>>unordered_multiset/modifiers/hetero/erase.cc
> >>>create mode 100644
> >>>libstdc++-v3/testsuite/23_containers/unordered_set/
> >>>modifiers/hetero/erase.cc
> >>>
> >>>diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/
> >>>include/bits/hashtable.h
> >>>index 06cc51ac4a0..bd5c9dc64e5 100644
> >>>--- a/libstdc++-v3/include/bits/hashtable.h
> >>>+++ b/libstdc++-v3/include/bits/hashtable.h
> >>>@@ -905,6 +905,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> >>> __location_type
> >>> _M_locate(const key_type& __k) const;
> >>>
> >>>+ // We would like to extend _M_locate for heterogeneous
> >>>+ // keys, and use try_emplace as is, but ABI forbids it.
> >>
> >>Why? Because of explicit instantiations, or something else?
> >
> >Guessing that CUs built before this may have it as a global symbol
> >reference. If not, I am happy to remove it.
>
> But everything here is a template, so every object file contains
> implicit instantiations of all the member functions it uses.
>
> >>>+ template <typename _HetKey>
> >>
> >>We use _Kt everywhere else for heterogeneous key parameters. The fact
> >>it's a template parameter (rather than just using _Key or key_type)
> >>already implies it's a heterogeneous key type.
> >
> >OK.
> >
> >>>+ __location_type
> >>>+ _M_locate_tr(const _HetKey& __k) const;
> >>
> >>Should this be guarded by __glibcxx_associative_heterogeneous_erasure ?
> >>Patch v2 called _M_locate_tr from pre-C++23 code, but v3 doesn't seem
> >>to.
> >
> >P2363 updates various existing members to use _M_locate_tr with
> >the regular key, in an effort to minimize code duplication.
>
> OK, that makes sense.
>
> >>>+
> >>> __node_ptr
> >>> _M_find_node(size_type __bkt, const key_type& __key,
> >>> __hash_code __c) const
> >>>@@ -1016,6 +1022,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> >>> iterator
> >>> _M_erase(size_type __bkt, __node_base_ptr __prev_n,
> >>>__node_ptr __n);
> >>>
> >>>+ size_type
> >>>+ _M_erase_some(size_type __bkt, __node_base_ptr __prev_n,
> >>>__node_ptr __n);
> >>>+
> >>> template<typename _InputIterator>
> >>> void
> >>> _M_insert_range_multi(_InputIterator __first, _InputIterator __last);
> >>>@@ -1163,6 +1172,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> >>> size_type
> >>> erase(const key_type& __k);
> >>>
> >>>+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
> >>
> >>We don't put the paper number on these feature test checks anywhere
> >>else in our headers.
> >
> >OK, removing.
> >
> >>>+ template <typename _HetKey>
> >>>+ size_type
> >>>+ _M_erase_tr(const _HetKey& __k);
> >>>+#endif
> >>>...
> >>> +#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077>>
> >+ template<typename _Key, typename _Value, typename _Alloc,
> >>>+ typename _ExtractKey, typename _Equal,
> >>>+ typename _Hash, typename _RangeHash, typename _Unused,
> >>>+ typename _RehashPolicy, typename _Traits>
> >>>+ template <typename _HetKey>
> >>>+ auto
> >>>+ _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
> >>>+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
> >>>+ _M_erase_tr(const _HetKey& __k)
> >>>+ -> size_type
> >>>+ {
> >>>+ auto __loc = _M_locate_tr(__k);
> >>>+ if (!__loc)
> >>>+ return 0;
> >>>+
> >>>+ __node_base_ptr __prev_n = __loc._M_before;
> >>>+ __node_ptr __n = __loc._M_node();
> >>>+ auto __bkt = __loc._M_bucket_index;
> >>>+ if (__bkt == size_type(-1))
> >>>+ __bkt = _M_bucket_index(*__n);
> >>>+ if constexpr (__unique_keys::value)
> >>>+ {
> >>>+ _M_erase(__bkt, __prev_n, __n);
> >>>+ return 1;
> >>>+ }
> >>>+ else
> >>>+ return _M_erase_some(__bkt, __prev_n, __n);
> >>>+ }
> >>>+#endif // P2207
> >>
> >>This should definitely not be the paper number here, but the macro
> >>name (omitting the prefix if you want to keep it brief):
> >>
> >># endif // associative_heterogeneous_erasure
> >
> >OK.
> >
> >>>+
> >>>#pragma GCC diagnostic pop
> >>>
> >>> template<typename _Key, typename _Value, typename _Alloc,
> >>>@@ -2977,6 +3087,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> >>> = __enable_if_t<!__or_<is_integral<_Hash>,
> >>>__is_allocator<_Hash>>::value>;
> >>>#endif
> >>>
> >>>+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
> >>>+template <typename _Kt, typename _Container>
> >>>+ concept __heterogeneous_hash_key =
> >>>+ __transparent_comparator<typename _Container::hasher> &&
> >>>+ __transparent_comparator<typename _Container::key_equal> &&
> >>>+ __heterogeneous_key<_Kt, _Container>;
> >>>+#endif
> >>>+
> >>>/// @endcond
> >>>_GLIBCXX_END_NAMESPACE_VERSION
> >>>} // namespace std
> >>>diff --git a/libstdc++-v3/include/bits/stl_function.h
> >>>b/libstdc++-v3/ include/bits/stl_function.h
> >>>index ff3f8f4c6e7..7f99ffe1566 100644
> >>>--- a/libstdc++-v3/include/bits/stl_function.h
> >>>+++ b/libstdc++-v3/include/bits/stl_function.h
> >>>@@ -1486,6 +1486,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> >>>#endif
> >>>#endif
> >>>
> >>>+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
> >>>+template <typename _Kt, typename _Container>
> >>>+ concept __not_container_iterator =
> >>>+ (!is_convertible_v<_Kt&&, typename _Container::iterator> &&
> >>>+ !is_convertible_v<_Kt&&, typename _Container::const_iterator>);
> >>>+
> >>>+template <typename _Kt, typename _Container>
> >>>+ concept __heterogeneous_key =
> >>>+ (!is_same_v<typename _Container::key_type, remove_cvref_t<_Kt>>) &&
> >>>+ __not_container_iterator<_Kt&&, _Container>;
> >>
> >>Do you need to add the && here when __not_container_iterator
> >>explicitly adds it again?
> >
> >OK.
> >
> >>>+#endif
> >>>+
> >>>_GLIBCXX_END_NAMESPACE_VERSION
> >>>} // namespace
> >>>
> >>>diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/
> >>>include/bits/stl_map.h
> >>>index 62d66cef6b2..686ab792399 100644
> >>>--- a/libstdc++-v3/include/bits/stl_map.h
> >>>+++ b/libstdc++-v3/include/bits/stl_map.h
> >>>@@ -65,6 +65,7 @@
> >>>#if __glibcxx_containers_ranges // C++ >= 23
> >>># include <bits/ranges_base.h> // ranges::begin, ranges::distance etc.
> >>>#endif
> >>>+#include <bits/stl_tree.h>
> >>
> >>If this is included here, it doesn't need to be included in <regex>
> >>prior to including stl_map.h.
> >
> >Is this a suggestion to patch std/regex too?
> >Ready to do, if so.
>
> It can be part of a separate patch though.
>
> >>>
> >>>+ ///@{
> >>> /**
> >>> * @brief Erases elements according to the provided key.
> >>> * @param __x Key of element to be erased.
> >>>@@ -1158,6 +1167,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> >>> erase(const key_type& __x)
> >>> { return _M_t._M_erase_unique(__x); }
> >>>
> >>>+#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
> >>>+ // Note that for some types _Kt this may erase more than
> >>>+ // one element, such as if _Kt::operator< checks only part
> >>>+ // of the key.
> >>>+ template <__heterogeneous_tree_key<map> _Kt>
> >>>+ size_type
> >>>+ erase(_Kt&& __x)
> >>>+ { return _M_t._M_erase_tr(__x); }
> >>>+#endif
> >>>+ ///@}
> >>>+
> >>>#if __cplusplus >= 201103L
> >>> // _GLIBCXX_RESOLVE_LIB_DEFECTS
> >>> // DR 130. Associative erase should return an iterator.
> >>>diff --git a/libstdc++-v3/include/bits/stl_multimap.h
> >>>b/libstdc++-v3/ include/bits/stl_multimap.h
> >>>index b2ae2bae745..7576653c8b9 100644
> >>>--- a/libstdc++-v3/include/bits/stl_multimap.h
> >>>+++ b/libstdc++-v3/include/bits/stl_multimap.h
> >>>@@ -63,6 +63,7 @@
> >>>#if __glibcxx_containers_ranges // C++ >= 23
> >>># include <bits/ranges_base.h> // ranges::begin, ranges::distance etc.
> >>>#endif
> >>>+#include <bits/stl_tree.h>
> >>
> >>Adding this is redundant. stl_multimap.h is included in exactly one
> >>file, <map>, and that includes stl_tree.h before it includes stl_map.h
> >>and stl_multimap.h
> >
> >OK.
> >
> >>Although GCC optimizes includes to avoid reopening the file on disk,
> >>we now do #include <bits/stl_tree.h> three times in <set> and three
> >>times in <map>.
> >>
> >>The only reason that a "single use" header like stl_set.h needs to be
> >>self-sufficient in terms of "include what you use" is if you are
> >>compiling individual bits/*.h headers as header units so they can be
> >>imported, which Nathan Sidwell was at one time making changes to
> >>support.
> >>
> >>I have a weak preference for not adding these redundant includes.
> >>
> >>P.S. oh I see later in the patch that including bits/stl_tree.h is
> >>removed from <map> and <set>, so it's only being included twice now,
> >>not three times as I said above. So that's less bad.
> >
> >I will clean up redundant includes.
> >
> >>>...
> >>>--- a/libstdc++-v3/include/bits/stl_tree.h
> >>>+++ b/libstdc++-v3/include/bits/stl_tree.h
> >>>@@ -1399,8 +1399,8 @@ namespace __rb_tree
> >>>#if __cplusplus >= 201103L
> >>> // Enforce this here with a user-friendly message.
> >>> static_assert(
> >>>- __is_invocable<const _Compare&, const _Key&, const
> >>>_Key&>::value,
> >>>- "comparison object must be invocable with two arguments
> >>>of key type"
> >>>+ __is_invocable<const _Compare&, const _Key1&, const
> >>>_Key2&>::value,
> >>>+ "comparison object must be invocable with key types used"
> >>
> >>IIRC I made this function a template so the static_assert would only
> >>be checked if a comparison was actually performed (so not checked for
> >>the default constructor and destructor, for example). But the fact
> >>that it tested invocation with _Key not with _Key1 and _Key2 was
> >>intentional. The point of this static_assert is to check that _Compare
> >>accepts arguments of type const _Key& because those are the template
> >>parameters of the whole class.
> >>
> >>Specifically, it was for diagnosing Gaby's example in
> >>https://gcc.gnu.org/PR48101
> >>
> >>So I'm not sure we need to generalize the assertion for all uses of
> >>transparent comparators, but I suppose it doesn't hurt.
> >
> >Taking this as permission to retain the change...
> >Clear error messages in more use cases seems like a benefit.
>
> Agreed, but "with key types used" doesn't seem entirely clear, due to
> English ambiguity. It could mean "invocable using arguments of the key
> types used in this expression" or it could mean "must be invocable,
> and key types must be used"
>
> Is an unambiguous phrasing possible?
Maybe "comparison object must be invocable with the supplied key types" ?
More information about the Libstdc++
mailing list