https://gcc.gnu.org/g:7c2e60f67a02d17d8c2f67ba438fdb50d51bc9f4
commit r16-284-g7c2e60f67a02d17d8c2f67ba438fdb50d51bc9f4
Author: Barnabás Pőcze <po...@protonmail.com>
Date: Mon Mar 11 23:35:50 2024 +0000
libstdc++: Optimize removal from unique assoc containers [PR112934]
Previously, calling erase(key) on both std::map and std::set
would execute that same code that std::multi{map,set} would.
However, doing that is unnecessary because std::{map,set}
guarantee that all elements are unique.
It is reasonable to expect that erase(key) is equivalent
or better than:
auto it = m.find(key);
if (it != m.end())
m.erase(it);
However, this was not the case. Fix that by adding a new
function _Rb_tree<>::_M_erase_unique() that is essentially
equivalent to the above snippet, and use this from both
std::map and std::set.
libstdc++-v3/ChangeLog:
PR libstdc++/112934
* include/bits/stl_map.h (map::erase): Use _M_erase_unique.
* include/bits/stl_set.h (set::erase): Likewise.
* include/bits/stl_tree.h (_Rb_tree::_M_erase_unique): Add.
Diff:
---
libstdc++-v3/include/bits/stl_map.h | 2 +-
libstdc++-v3/include/bits/stl_set.h | 2 +-
libstdc++-v3/include/bits/stl_tree.h | 17 +++++++++++++++++
3 files changed, 19 insertions(+), 2 deletions(-)
diff --git a/libstdc++-v3/include/bits/stl_map.h
b/libstdc++-v3/include/bits/stl_map.h
index 006ff46dfb5d..68c23b8e3e71 100644
--- a/libstdc++-v3/include/bits/stl_map.h
+++ b/libstdc++-v3/include/bits/stl_map.h
@@ -1156,7 +1156,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
*/
size_type
erase(const key_type& __x)
- { return _M_t.erase(__x); }
+ { return _M_t._M_erase_unique(__x); }
#if __cplusplus >= 201103L
// _GLIBCXX_RESOLVE_LIB_DEFECTS
diff --git a/libstdc++-v3/include/bits/stl_set.h
b/libstdc++-v3/include/bits/stl_set.h
index 0799fd0918a3..b65d63195aa2 100644
--- a/libstdc++-v3/include/bits/stl_set.h
+++ b/libstdc++-v3/include/bits/stl_set.h
@@ -728,7 +728,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
*/
size_type
erase(const key_type& __x)
- { return _M_t.erase(__x); }
+ { return _M_t._M_erase_unique(__x); }
#if __cplusplus >= 201103L
// _GLIBCXX_RESOLVE_LIB_DEFECTS
diff --git a/libstdc++-v3/include/bits/stl_tree.h
b/libstdc++-v3/include/bits/stl_tree.h
index 6c12c41bba7b..4b7f482e794c 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -1850,6 +1850,9 @@ namespace __rb_tree
size_type
erase(const key_type& __x);
+ size_type
+ _M_erase_unique(const key_type& __x);
+
#if __cplusplus >= 201103L
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 130. Associative erase should return an iterator.
@@ -3139,6 +3142,20 @@ namespace __rb_tree
return __old_size - size();
}
+ template<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_erase_unique(const _Key& __x)
+ {
+ iterator __it = find(__x);
+ if (__it == end())
+ return 0;
+
+ _M_erase_aux(__it);
+ return 1;
+ }
+
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue,
