[PATCH v1] libstdc++: Optimize removal from unique assoc containers [PR112934]

[Barnabás Pőcze]

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_tree.h (_Rb_tree<>::_M_erase_unique): Add.
        * include/bits/stl_map.h (map<>::erase): Use _M_erase_unique.
        * include/bits/stl_set.h (set<>::erase): Likewise.
---
 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 ad58a631af5..229643b77fd 100644
--- a/libstdc++-v3/include/bits/stl_map.h
+++ b/libstdc++-v3/include/bits/stl_map.h
@@ -1115,7 +1115,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 c0eb4dbf65f..51a1717ec62 100644
--- a/libstdc++-v3/include/bits/stl_set.h
+++ b/libstdc++-v3/include/bits/stl_set.h
@@ -684,7 +684,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 6f470f04f6a..9e80d449c7e 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -1225,6 +1225,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       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.
@@ -2518,6 +2521,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       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,
-- 
2.44.0