On Tue, 10 Feb 2026 at 23:14, Nathan Myers <[email protected]> wrote:
>
> Implement the debug versions of new overloads from P2077.
>
> Also, make existing unordered_set<>::erase perform the same
> bucket check as erase on unordered_multimap.
>
> libstdc++-v3/ChangeLog:
> PR libstdc++/117402
> * include/debug/map.h (extract, erase): Define overloads.
> * include/debug/multimap.h: Same.
> * include/debug/multiset.h: Same.
> * include/debug/set.h: Same.
> * include/debug/unordered_map: Same (2x).
> * include/debug/unordered_set: Same (2x).
> ---
> libstdc++-v3/include/debug/map.h | 30 ++++++++++++
> libstdc++-v3/include/debug/multimap.h | 27 +++++++++++
> libstdc++-v3/include/debug/multiset.h | 27 +++++++++++
> libstdc++-v3/include/debug/set.h | 30 ++++++++++++
> libstdc++-v3/include/debug/unordered_map | 49 +++++++++++++++++++
> libstdc++-v3/include/debug/unordered_set | 62 +++++++++++++++++++++---
> 6 files changed, 219 insertions(+), 6 deletions(-)
>
> diff --git a/libstdc++-v3/include/debug/map.h
> b/libstdc++-v3/include/debug/map.h
> index 0fc7afae385..29363a08d4d 100644
> --- a/libstdc++-v3/include/debug/map.h
> +++ b/libstdc++-v3/include/debug/map.h
> @@ -476,6 +476,16 @@ namespace __debug
> return {};
> }
>
> +# ifdef __glibcxx_heterogeneous_container_erasure
> + template <__heterogeneous_tree_key<map> _Kt>
> + node_type
> + extract(_Kt&& __key)
> + {
> + const auto __position = _Base::find<_Kt>(__key);
> + return __position != end() ? extract(__position) : {};
> + }
> +# endif
> +
> insert_return_type
> insert(node_type&& __nh)
> {
> @@ -538,6 +548,26 @@ namespace __debug
> }
> }
>
> +# ifdef __glibcxx_heterogeneous_container_erasure
> + // 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)
> + {
> + auto __victims = _Base::equal_range<_Kt>(__x);
> + size_type __count = 0;
> + for (auto __victim = __victims.first; __victim != __victims.second;)
> + {
> + this->_M_invalidate_if(_Equal(__victim));
> + _Base::erase(__victim++);
> + ++__count;
> + }
Would it be more efficient to do one call to:
_Base::erase(__victims.first, __victims.second)
so that the tree doesn't keep rebalancing?
> + return __count;
> + }
> +# endif
> +
> #if __cplusplus >= 201103L
> iterator
> erase(const_iterator __first, const_iterator __last)
> diff --git a/libstdc++-v3/include/debug/multimap.h
> b/libstdc++-v3/include/debug/multimap.h
> index 4137186c527..ba6e9498710 100644
> --- a/libstdc++-v3/include/debug/multimap.h
> +++ b/libstdc++-v3/include/debug/multimap.h
> @@ -360,6 +360,16 @@ namespace __debug
> return {};
> }
>
> +# ifdef __glibcxx_heterogeneous_container_erasure
> + template <__heterogeneous_tree_key<multimap> _Kt>
> + node_type
> + extract(_Kt&& __key)
> + {
> + const auto __position = _Base::find<_Kt>(__key);
> + return __position != end() ? extract(__position) : {};
> + }
> +# endif
> +
> iterator
> insert(node_type&& __nh)
> { return { _Base::insert(std::move(__nh)), this }; }
> @@ -420,6 +430,23 @@ namespace __debug
> return __count;
> }
>
> +# ifdef __glibcxx_heterogeneous_container_erasure
> + template <__heterogeneous_tree_key<multimap> _Kt>
> + size_type
> + erase(_Kt&& __x)
> + {
> + auto __victims = _Base::equal_range<_Kt>(__x);
> + size_type __count = 0;
> + for (auto __victim = __victims.first; __victim != __victims.second;)
> + {
> + this->_M_invalidate_if(_Equal(__victim));
> + _Base::erase(__victim++);
> + ++__count;
> + }
> + return __count;
> + }
> +# endif
> +
> #if __cplusplus >= 201103L
> iterator
> erase(const_iterator __first, const_iterator __last)
> diff --git a/libstdc++-v3/include/debug/multiset.h
> b/libstdc++-v3/include/debug/multiset.h
> index 6fa499228f5..c8e34f704b4 100644
> --- a/libstdc++-v3/include/debug/multiset.h
> +++ b/libstdc++-v3/include/debug/multiset.h
> @@ -331,6 +331,16 @@ namespace __debug
> return {};
> }
>
> +# ifdef __glibcxx_heterogeneous_container_erasure
> + template <__heterogeneous_tree_key<multiset> _Kt>
> + node_type
> + extract(_Kt&& __key)
> + {
> + const auto __position = _Base::find<_Kt>(__key);
> + return __position != end() ? extract(__position) : {};
> + }
> +#endif
> +
> iterator
> insert(node_type&& __nh)
> { return { _Base::insert(std::move(__nh)), this }; }
> @@ -387,6 +397,23 @@ namespace __debug
> return __count;
> }
>
> +# ifdef __glibcxx_heterogeneous_container_erasure
> + template <__heterogeneous_tree_key<multiset> _Kt>
> + size_type
> + erase(_Kt&& __x)
> + {
> + auto __victims = _Base::equal_range<_Kt>(__x);
> + size_type __count = 0;
> + for (auto __victim = __victims.first; __victim != __victims.second;)
> + {
> + this->_M_invalidate_if(_Equal(__victim));
> + _Base::erase(__victim++);
> + ++__count;
> + }
> + return __count;
> + }
> +# endif
> +
> #if __cplusplus >= 201103L
> _GLIBCXX_ABI_TAG_CXX11
> iterator
> diff --git a/libstdc++-v3/include/debug/set.h
> b/libstdc++-v3/include/debug/set.h
> index 99701d4a6d7..9a3bcce41fa 100644
> --- a/libstdc++-v3/include/debug/set.h
> +++ b/libstdc++-v3/include/debug/set.h
> @@ -340,6 +340,16 @@ namespace __debug
> return {};
> }
>
> +# ifdef __glibcxx_heterogeneous_container_erasure
> + template <__heterogeneous_tree_key<set> _Kt>
> + node_type
> + extract(_Kt&& __key)
> + {
> + const auto __position = _Base::find<_Kt>(__key);
> + return __position != end() ? extract(__position) : {};
> + }
> +#endif
> +
> insert_return_type
> insert(node_type&& __nh)
> {
> @@ -398,6 +408,26 @@ namespace __debug
> }
> }
>
> +# ifdef __glibcxx_heterogeneous_container_erasure
> + // Note that for some types _Kt this may erase more than
> + // one element, such as if _Kt::operator< checks only part
> + // of the key.
> + template <__heterogeneous_tree_key<set> _Kt>
> + size_type
> + erase(_Kt&& __x)
> + {
> + auto __victims = _Base::equal_range<_Kt>(__x);
> + size_type __count = 0;
> + for (auto __victim = __victims.first; __victim != __victims.second;)
> + {
> + this->_M_invalidate_if(_Equal(__victim));
> + _Base::erase(__victim++);
> + ++__count;
> + }
> + return __count;
> + }
> +#endif
> +
> #if __cplusplus >= 201103L
> _GLIBCXX_ABI_TAG_CXX11
> iterator
> diff --git a/libstdc++-v3/include/debug/unordered_map
> b/libstdc++-v3/include/debug/unordered_map
> index 4bde18c917b..e90d1078241 100644
> --- a/libstdc++-v3/include/debug/unordered_map
> +++ b/libstdc++-v3/include/debug/unordered_map
> @@ -581,6 +581,16 @@ namespace __debug
> return {};
> }
>
> +# ifdef __glibcxx_heterogeneous_container_erasure
> + template <__heterogeneous_tree_key<unordered_map> _Kt>
> + node_type
> + extract(_Kt&& __key)
> + {
> + const auto __position = _Base::find<_Kt>(__key);
> + return __position != _Base::end() ? _M_extract(__position) : {};
> + }
> +#endif
> +
> insert_return_type
> insert(node_type&& __nh)
> {
> @@ -713,6 +723,16 @@ namespace __debug
> return __ret;
> }
>
> +# ifdef __glibcxx_heterogeneous_container_erasure
> + template <__heterogeneous_tree_key<unordered_map> _Kt>
> + size_type
> + erase(_Kt&& __key)
> + {
> + auto __victim = _Base::find<_Kt>(__key);
> + return __victim != _Base::end() ? _M_erase(__victim), 1 : 0;
> + }
> +#endif
> +
> iterator
> erase(const_iterator __it)
> {
> @@ -1381,6 +1401,16 @@ namespace __debug
> return {};
> }
>
> +# ifdef __glibcxx_heterogeneous_container_erasure
> + template <__heterogeneous_tree_key<unordered_multimap> _Kt>
> + node_type
> + extract(_Kt&& __key)
> + {
> + const auto __position = _Base::find<_Kt>(__key);
> + return __position != _Base::end() ? _M_extract(__position) : {};
> + }
> +#endif
> +
> iterator
> insert(node_type&& __nh)
> { return { _Base::insert(std::move(__nh)), this }; }
> @@ -1510,6 +1540,25 @@ namespace __debug
> return __ret;
> }
>
> +# ifdef __glibcxx_heterogeneous_container_erasure
> + template <__heterogeneous_tree_key<unordered_multimap> _Kt>
> + size_type
> + erase(_Kt&& __key)
> + {
> + size_type __count(0);
> + size_type __bucket_count = this->bucket_count();
> + auto __victims = _Base::equal_range<_Kt>(__key);
> + for (auto __victim = __victims.first; __victim != __victims.second;)
> + {
> + _M_invalidate(__victim);
> + __victim = _Base::erase(__victim);
> + ++__count;
> + }
> + _M_check_rehashed(__bucket_count);
> + return __count;
> + }
> +#endif
> +
> iterator
> erase(const_iterator __it)
> {
> diff --git a/libstdc++-v3/include/debug/unordered_set
> b/libstdc++-v3/include/debug/unordered_set
> index de999a76890..6f4f4ae8f96 100644
> --- a/libstdc++-v3/include/debug/unordered_set
> +++ b/libstdc++-v3/include/debug/unordered_set
> @@ -468,6 +468,16 @@ namespace __debug
> return {};
> }
>
> +# ifdef __glibcxx_heterogeneous_container_erasure
> + template <__heterogeneous_tree_key<unordered_set> _Kt>
> + node_type
> + extract(_Kt&& __key)
> + {
> + const auto __position = _Base::find<_Kt>(__key);
> + return __position != _Base::end() ? _M_extract(__position) : {};
> + }
> +#endif
> +
> insert_return_type
> insert(node_type&& __nh)
> {
> @@ -598,6 +608,16 @@ namespace __debug
> return __ret;
> }
>
> +# ifdef __glibcxx_heterogeneous_container_erasure
> + template <__heterogeneous_tree_key<unordered_set> _Kt>
> + size_type
> + erase(_Kt&& __x)
> + {
> + auto __victim = _Base::find<_Kt>(__key);
> + return __victim != _Base::end() ? _M_erase(__victim), 1 : 0;
> + }
> +#endif
> +
> iterator
> erase(const_iterator __it)
> {
> @@ -1202,6 +1222,16 @@ namespace __debug
> return {};
> }
>
> +# ifdef __glibcxx_heterogeneous_container_erasure
> + template <__heterogeneous_tree_key<unordered_multiset> _Kt>
> + node_type
> + extract(const _Kt& __key)
> + {
> + const auto __position = _Base::find<_Kt>(__key);
> + return __position != _Base::end() ? _M_extract(__position) : {};
> + }
> +#endif
> +
> iterator
> insert(node_type&& __nh)
> { return { _Base::insert(std::move(__nh)), this }; }
> @@ -1318,18 +1348,38 @@ namespace __debug
> size_type
> erase(const key_type& __key)
> {
> - size_type __ret(0);
> - auto __pair = _Base::equal_range(__key);
> - for (auto __victim = __pair.first; __victim != __pair.second;)
> + size_type __count(0);
> + size_type __bucket_count = this->bucket_count();
> + auto __victims = _Base::equal_range(__key);
> + for (auto __victim = __victims.first; __victim != __victims.second;)
> {
> _M_invalidate(__victim);
> __victim = _Base::erase(__victim);
> - ++__ret;
> + ++__count;
> }
> -
> - return __ret;
> + _M_check_rehashed(__bucket_count);
Is this a bug fix? It's not mentioned in the commit message.
> + return __count;
> }
>
> +# ifdef __glibcxx_heterogeneous_container_erasure
> + template <__heterogeneous_tree_key<unordered_multiset> _Kt>
> + size_type
> + erase(_Kt&& __key)
> + {
> + size_type __count(0);
> + size_type __bucket_count = this->bucket_count();
> + auto __victims = _Base::equal_range<_Kt>(__key);
> + for (auto __victim = __victims.first; __victim != __victims.second;)
> + {
> + _M_invalidate(__victim);
> + __victim = _Base::erase(__victim);
> + ++__count;
> + }
> + _M_check_rehashed(__bucket_count);
> + return __count;
> + }
> +#endif
> +
> iterator
> erase(const_iterator __it)
> {
> --
> 2.52.0
>
