diff options
| author | Barnabás Pőcze <pobrn@protonmail.com> | 2024-03-11 23:35:50 +0000 |
|---|---|---|
| committer | Jonathan Wakely <redi@gcc.gnu.org> | 2025-04-29 15:08:53 +0100 |
| commit | 7c2e60f67a02d17d8c2f67ba438fdb50d51bc9f4 (patch) | |
| tree | 44b4cbcdd09c3f2bb92feb64dfe2ccda082f66b6 | |
| parent | 102eccaf8e2f914d3afbf7acfcee19bc5b240eca (diff) | |
| download | gcc-7c2e60f67a02d17d8c2f67ba438fdb50d51bc9f4.zip gcc-7c2e60f67a02d17d8c2f67ba438fdb50d51bc9f4.tar.gz gcc-7c2e60f67a02d17d8c2f67ba438fdb50d51bc9f4.tar.bz2 | |
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.
| -rw-r--r-- | libstdc++-v3/include/bits/stl_map.h | 2 | ||||
| -rw-r--r-- | libstdc++-v3/include/bits/stl_set.h | 2 | ||||
| -rw-r--r-- | 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 006ff46..68c23b8 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 0799fd0..b65d631 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 6c12c41..4b7f482 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. @@ -3141,6 +3144,20 @@ namespace __rb_tree 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, _Compare, _Alloc>::iterator _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |