[PATCH] libstdc++: Limit allocations in _Rb_tree

[PATCH] libstdc++: Limit allocations in _Rb_tree

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 1867 bytes --]

This is PR 96088 but this time for _Rb_tree based containers.

I guess it won't go in for the moment but I wanted to submit it already 
because of the changes I had to do in stl_functions.h. It sounds like 
missing parts for C++11 move-semantic. I still need to run all tests to 
see if they can have side effects.

      libstdc++: [_Rb_tree] Limit allocation on iterator insertion [PR 
96088]

     Detect when invoking the comparer require an allocation and in this 
case
     create a temporary instance that will be moved to storage location 
if the
     insertion eventually takes place. Avoid to allocate a node otherwise.

     libstdc++-v3/ChangeLog:

             PR libstdc++/96088
             * include/bits/stl_function.h
             (std::less<>::operator()): Add noexcept qualification.
             (std::greater::operator()): Likewise.
(std::_Identity<>::operator<_Tp2>(_Tp2&&)): New perfect forwarding operator.
(std::_Select1st<>::operator<_Pair2>(_Pair2&&)): New move operator.
             * include/bits/stl_tree.h 
(_Rb_tree<>::_ConvertToValueType<>): New helper type.
             (_Rb_tree<>::_M_get_insert_unique_pos_tr): New.
             (_Rb_tree<>::_S_forward_key): New.
             (_Rb_tree<>::_M_emplace_unique_kv): New.
             (_Rb_tree<>::_M_emplace_unique_aux): New, use latter.
             (_Rb_tree<>::_M_emplace_unique): New, use latter.
             * testsuite/23_containers/map/96088.cc: New test case.
             * testsuite/23_containers/multimap/96088.cc: New test case.
             * testsuite/23_containers/multiset/96088.cc: New test case.
             * testsuite/23_containers/set/96088.cc: New test case.

Ok to commit ?

François


[-- Attachment #2: pr96088_tree.patch --]
[-- Type: text/x-patch, Size: 25425 bytes --]

diff --git a/libstdc++-v3/include/bits/stl_function.h b/libstdc++-v3/include/bits/stl_function.h
index fa03f32b1b8..5e04c82629b 100644
--- a/libstdc++-v3/include/bits/stl_function.h
+++ b/libstdc++-v3/include/bits/stl_function.h
@@ -395,6 +395,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _GLIBCXX14_CONSTEXPR
       bool
       operator()(const _Tp& __x, const _Tp& __y) const
+	_GLIBCXX_NOEXCEPT_IF( noexcept(__x > __y) )
       { return __x > __y; }
     };
 
@@ -405,6 +406,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _GLIBCXX14_CONSTEXPR
       bool
       operator()(const _Tp& __x, const _Tp& __y) const
+	_GLIBCXX_NOEXCEPT_IF( noexcept(__x < __y) )
       { return __x < __y; }
     };
 
@@ -1165,6 +1167,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       const _Tp&
       operator()(const _Tp& __x) const
       { return __x; }
+
+#if __cplusplus >= 201103L
+    template<typename _Tp2>
+      _Tp2&&
+      operator()(_Tp2&& __x) const noexcept
+      { return std::forward<_Tp2>(__x); }
+#endif
     };
 
   // Partial specialization, avoids confusing errors in e.g. std::set<const T>.
@@ -1192,6 +1201,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	const typename _Pair2::first_type&
 	operator()(const _Pair2& __x) const
 	{ return __x.first; }
+
+      template<typename _Pair2>
+	typename _Pair2::first_type&&
+	operator()(_Pair2&& __x) const
+	{ return std::move(__x.first); }
 #endif
     };
 
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index 3c331fbc952..8096ba97f18 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -534,6 +534,42 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_Rb_tree& _M_t;
       };
 
+#if __cplusplus >= 201103L
+      template<typename _ExKey, typename _Value>
+	struct _ConvertToValueType;
+
+      template<typename _Value>
+	struct _ConvertToValueType<std::_Identity<_Value>, _Value>
+	{
+	  template<typename _Kt>
+	    constexpr _Kt&&
+	    operator()(_Kt&& __k) const noexcept
+	    { return std::forward<_Kt>(__k); }
+	};
+
+      template<typename _Value>
+	struct _ConvertToValueType<std::_Select1st<_Value>, _Value>
+	{
+	  constexpr _Value&&
+	  operator()(_Value&& __x) const noexcept
+	  { return std::move(__x); }
+
+	  constexpr const _Value&
+	  operator()(const _Value& __x) const noexcept
+	  { return __x; }
+
+	  template<typename _Kt, typename _Vt>
+	    constexpr std::pair<_Kt, _Vt>&&
+	    operator()(std::pair<_Kt, _Vt>&& __x) const noexcept
+	    { return std::move(__x); }
+
+	  template<typename _Kt, typename _Vt>
+	    constexpr const std::pair<_Kt, _Vt>&
+	    operator()(const std::pair<_Kt, _Vt>& __x) const noexcept
+	    { return __x; }
+      };
+#endif // C++11
+
     public:
       typedef _Key 				key_type;
       typedef _Val 				value_type;
@@ -830,6 +866,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       pair<_Base_ptr, _Base_ptr>
       _M_get_insert_unique_pos(const key_type& __k);
 
+#if __cplusplus >= 201103L
+      template<typename _Kt>
+	pair<_Base_ptr, _Base_ptr>
+	_M_get_insert_unique_pos_tr(const _Kt& __k);
+#endif
+
       pair<_Base_ptr, _Base_ptr>
       _M_get_insert_equal_pos(const key_type& __k);
 
@@ -1075,6 +1117,45 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
 	}
 
+      template<typename _Kt>
+	static __conditional_t<
+	__and_<__is_nothrow_invocable<_Compare&,
+				      const key_type&, const key_type&>,
+	       __not_<__is_nothrow_invocable<_Compare&,
+					     _Kt, const key_type&>>>::value,
+	  key_type, _Kt&&>
+	_S_forward_key(_Kt&& __k)
+	{ return std::forward<_Kt>(__k); }
+
+      static const key_type&
+      _S_forward_key(const key_type& __k)
+      { return __k; }
+
+      static key_type&&
+      _S_forward_key(key_type&& __k)
+      { return std::move(__k); }
+
+      template<typename _Kt, typename _Arg>
+	std::pair<iterator, bool>
+	_M_emplace_unique_kv(_Kt&&, _Arg&&);
+
+      template<typename _Arg>
+	pair<iterator, bool>
+	_M_emplace_unique_aux(_Arg&& __arg)
+	{
+	  return _M_emplace_unique_kv(
+	    _S_forward_key(_KeyOfValue{}(std::forward<_Arg>(__arg))),
+	    std::forward<_Arg>(__arg));
+	}
+
+      template<typename _Arg>
+	pair<iterator, bool>
+	_M_emplace_unique(_Arg&& __arg)
+	{
+	  using __to_value = _ConvertToValueType<_KeyOfValue, value_type>;
+	  return _M_emplace_unique_aux(__to_value{}(std::forward<_Arg>(__arg)));
+	}
+
       template<typename... _Args>
 	pair<iterator, bool>
 	_M_emplace_unique(_Args&&... __args);
@@ -1670,6 +1751,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_Rb_tree& _M_t;
 	_Link_type _M_node;
       };
+
+      template<typename _Kt, typename _Arg, typename _SelectFst>
+	static _Auto_node
+	_S_build_node(_Rb_tree& __t, _Kt&& __k, _Arg&& __arg, _SelectFst)
+	{
+	  return
+	    { __t, std::forward<_Kt>(__k), std::forward<_Arg>(__arg).second };
+	}
+
+      template<typename _Kt, typename _Arg>
+	static _Auto_node
+	_S_build_node(_Rb_tree& __t, _Kt&& __k, _Arg&&, std::_Identity<_Val>)
+	{ return { __t, std::forward<_Kt>(__k) }; }
 #endif // C++11
     };
 
@@ -2131,6 +2225,39 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return _Res(__j._M_node, 0);
     }
 
+#if __cplusplus >= 201103L
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+	   typename _Compare, typename _Alloc>
+    template<typename _Kt>
+      auto
+      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      _M_get_insert_unique_pos_tr(const _Kt& __k)
+      -> pair<_Base_ptr, _Base_ptr>
+      {
+	typedef pair<_Base_ptr, _Base_ptr> _Res;
+	_Link_type __x = _M_begin();
+	_Base_ptr __y = _M_end();
+	bool __comp = true;
+	while (__x != 0)
+	  {
+	    __y = __x;
+	    __comp = _M_impl._M_key_compare(__k, _S_key(__x));
+	    __x = __comp ? _S_left(__x) : _S_right(__x);
+	  }
+	iterator __j = iterator(__y);
+	if (__comp)
+	  {
+	    if (__j == begin())
+	      return _Res(__x, __y);
+	    else
+	      --__j;
+	  }
+	if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
+	  return _Res(__x, __y);
+	return _Res(__j._M_node, 0);
+      }
+#endif
+
   template<typename _Key, typename _Val, typename _KeyOfValue,
 	   typename _Compare, typename _Alloc>
     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
@@ -2438,6 +2565,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	return {iterator(__res.first), false};
       }
 
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+	   typename _Compare, typename _Alloc>
+    template<typename _Kt, typename _Arg>
+      auto
+      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      _M_emplace_unique_kv(_Kt&& __k, _Arg&& __arg)
+      -> pair<iterator, bool>
+      {
+	auto __res = _M_get_insert_unique_pos_tr(__k);
+	if (__res.second)
+	  {
+	    _Auto_node __z = _S_build_node(*this,
+	      std::forward<_Kt>(__k), std::forward<_Arg>(__arg), _KeyOfValue{});
+	    return { __z._M_insert(__res), true };
+	  }
+	return { iterator(__res.first), false };
+      }
+
   template<typename _Key, typename _Val, typename _KeyOfValue,
 	   typename _Compare, typename _Alloc>
     template<typename... _Args>
diff --git a/libstdc++-v3/testsuite/23_containers/map/96088.cc b/libstdc++-v3/testsuite/23_containers/map/96088.cc
new file mode 100644
index 00000000000..7dd62129c23
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/map/96088.cc
@@ -0,0 +1,252 @@
+// { dg-do run { target c++17 } }
+// { dg-require-effective-target std_allocator_new }
+
+// Copyright (C) 2023 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// libstdc++/96088
+
+#include <string_view>
+#include <string>
+#include <map>
+#include <vector>
+
+#include <testsuite_hooks.h>
+#include <replacement_memory_operators.h>
+
+static constexpr std::initializer_list<std::pair<const char*, int>> lst =
+  { {"long_str_for_dynamic_allocating", 1} };
+
+void
+test01()
+{
+  __gnu_test::counter::reset();
+  std::map<std::string, int> m;
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+void
+test02()
+{
+  __gnu_test::counter::reset();
+  std::map<std::string, int, std::less<std::string_view>> m;
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+}
+
+bool
+less_string_f(const std::string& lhs, const std::string& rhs) noexcept
+{ return lhs < rhs; }
+
+void
+test11()
+{
+  typedef bool (*less_string_t)(const std::string&,
+				const std::string&) noexcept;
+  __gnu_test::counter::reset();
+  less_string_t comparer = &less_string_f;
+  std::map<std::string, int, less_string_t> m(comparer);
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+bool
+less_string_view_f(const std::string_view& lhs,
+		   const std::string_view& rhs) noexcept
+{ return lhs < rhs; }
+
+void
+test12()
+{
+  typedef bool (*less_stringview_t) (const std::string_view&,
+				     const std::string_view&) noexcept;
+  __gnu_test::counter::reset();
+  less_stringview_t comparer = &less_string_view_f;
+  std::map<std::string, int, less_stringview_t> m(comparer);
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+}
+
+struct less_string_functor
+{
+  bool
+  operator()(const std::string& lhs, const std::string& rhs) const noexcept
+  { return lhs < rhs; }
+};
+
+void
+test21()
+{
+  __gnu_test::counter::reset();
+  std::map<std::string, int, less_string_functor> m;
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+struct less_string_view_noexcept_functor
+{
+  bool
+  operator()(const std::string_view& lhs,
+	     const std::string_view& rhs) const noexcept
+  { return lhs < rhs; }
+};
+
+void
+test22()
+{
+  __gnu_test::counter::reset();
+  std::map<std::string, int, less_string_view_noexcept_functor> m;
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+}
+
+struct less_string_view_functor
+{
+  bool
+  operator()(const std::string_view& lhs,
+	     const std::string_view& rhs) const
+  { return lhs < rhs; }
+};
+
+void
+test23()
+{
+  __gnu_test::counter::reset();
+  std::map<std::string, int, less_string_view_functor> m;
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+void
+test03()
+{
+  std::vector<std::pair<std::string, int>> v;
+  v.insert(v.end(), lst.begin(), lst.end());
+
+  const auto origin = __gnu_test::counter::count();
+
+  {
+    __gnu_test::counter::reset();
+    std::map<std::string, int, std::less<std::string_view>> m;
+    m.insert(v.begin(), v.end());
+    VERIFY( m.size() == 1 );
+
+    // Allocate a node and the std::string (unless COW).
+    constexpr std::size_t increments = _GLIBCXX_USE_CXX11_ABI ? 2 : 1;
+
+    VERIFY( __gnu_test::counter::count() == origin + increments );
+    VERIFY( __gnu_test::counter::get()._M_increments == increments );
+
+    m.insert(v.begin(), v.end());
+    VERIFY( m.size() == 1 );
+
+    VERIFY( __gnu_test::counter::count() == origin + increments );
+    VERIFY( __gnu_test::counter::get()._M_increments == increments );
+  }
+  VERIFY( __gnu_test::counter::count() == origin );
+
+  {
+    __gnu_test::counter::reset();
+    std::map<std::string, int, std::less<std::string_view>> m;
+    m.insert(std::make_move_iterator(v.begin()),
+	     std::make_move_iterator(v.end()));
+    VERIFY( m.size() == 1 );
+
+    // Allocate a node. String is moved.
+    constexpr std::size_t increments = 1;
+
+    VERIFY( __gnu_test::counter::count() == origin + increments );
+    VERIFY( __gnu_test::counter::get()._M_increments == increments );
+  }
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  test11();
+  test12();
+  test21();
+  test22();
+  test03();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/multimap/96088.cc b/libstdc++-v3/testsuite/23_containers/multimap/96088.cc
new file mode 100644
index 00000000000..919c5e59c71
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multimap/96088.cc
@@ -0,0 +1,65 @@
+// { dg-do run { target c++17 } }
+// { dg-require-effective-target std_allocator_new }
+
+// Copyright (C) 2023 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// libstdc++/96088
+
+#include <string_view>
+#include <string>
+#include <map>
+
+#include <testsuite_hooks.h>
+#include <replacement_memory_operators.h>
+
+static constexpr std::initializer_list<std::pair<const char*, int>> lst = {
+    {"long_str_for_dynamic_allocating", 1}
+};
+
+void
+test01()
+{
+  __gnu_test::counter::reset();
+  std::multimap<std::string, int,
+		std::less<std::string_view>> foo;
+  foo.insert(lst.begin(), lst.end());
+  VERIFY( foo.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+}
+
+void
+test02()
+{
+  __gnu_test::counter::reset();
+  std::multimap<std::string, int> foo;
+  foo.insert(lst.begin(), lst.end());
+  VERIFY( foo.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/multiset/96088.cc b/libstdc++-v3/testsuite/23_containers/multiset/96088.cc
new file mode 100644
index 00000000000..2cdc08aba51
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multiset/96088.cc
@@ -0,0 +1,64 @@
+// { dg-do run { target c++17 } }
+// { dg-require-effective-target std_allocator_new }
+
+// Copyright (C) 2023 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// libstdc++/96088
+
+#include <string_view>
+#include <string>
+#include <set>
+
+#include <testsuite_hooks.h>
+#include <replacement_memory_operators.h>
+
+static constexpr std::initializer_list<const char*> lst = {
+  "long_str_for_dynamic_allocating"
+};
+
+void
+test01()
+{
+  __gnu_test::counter::reset();
+  std::multiset<std::string, std::less<std::string_view>> foo;
+  foo.insert(lst.begin(), lst.end());
+  VERIFY( foo.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+}
+
+void
+test02()
+{
+  __gnu_test::counter::reset();
+  std::multiset<std::string> foo;
+  foo.insert(lst.begin(), lst.end());
+  VERIFY( foo.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/set/96088.cc b/libstdc++-v3/testsuite/23_containers/set/96088.cc
new file mode 100644
index 00000000000..3ecb7f81ecc
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/set/96088.cc
@@ -0,0 +1,254 @@
+// { dg-do run { target c++17 } }
+// { dg-require-effective-target std_allocator_new }
+
+// Copyright (C) 2023 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// libstdc++/96088
+
+#include <string_view>
+#include <string>
+#include <set>
+#include <vector>
+
+#include <testsuite_hooks.h>
+#include <replacement_memory_operators.h>
+
+static constexpr std::initializer_list<const char*> lst = {
+  "long_str_for_dynamic_allocating"
+};
+
+void
+test01()
+{
+  __gnu_test::counter::reset();
+  std::set<std::string, std::greater<std::string>> s;
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+void
+test02()
+{
+  __gnu_test::counter::reset();
+  std::set<std::string, std::greater<std::string_view>> s;
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+}
+
+bool
+less_string_f(const std::string& lhs, const std::string& rhs) noexcept
+{ return lhs < rhs; }
+
+void
+test11()
+{
+  typedef bool (*less_string_t)(const std::string&,
+				const std::string&) noexcept;
+  __gnu_test::counter::reset();
+  less_string_t less = &less_string_f;
+  std::set<std::string, less_string_t> s(less);
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+bool
+less_string_view_f(const std::string_view& lhs,
+		   const std::string_view& rhs) noexcept
+{ return lhs < rhs; }
+
+void
+test12()
+{
+  typedef bool (*less_stringview_t)(const std::string_view&,
+				    const std::string_view&) noexcept;
+  __gnu_test::counter::reset();
+  less_stringview_t less = &less_string_view_f;
+  std::set<std::string, less_stringview_t> s(less);
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+}
+
+struct less_string_functor
+{
+  bool
+  operator()(const std::string& lhs, const std::string& rhs) const noexcept
+  { return lhs < rhs; }
+};
+
+void
+test21()
+{
+  __gnu_test::counter::reset();
+  std::set<std::string, less_string_functor> s;
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+struct less_string_view_noexcept_functor
+{
+  bool
+  operator()(const std::string_view& lhs,
+	     const std::string_view& rhs) const noexcept
+  { return lhs < rhs; }
+};
+
+void
+test22()
+{
+  __gnu_test::counter::reset();
+  std::set<std::string, less_string_view_noexcept_functor> s;
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+}
+
+struct less_string_view_functor
+{
+  bool
+  operator()(const std::string_view& lhs,
+	     const std::string_view& rhs) const
+  { return lhs < rhs; }
+};
+
+void
+test23()
+{
+  __gnu_test::counter::reset();
+  std::set<std::string, less_string_view_functor> s;
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+}
+
+void
+test03()
+{
+  std::vector<std::string> v;
+  v.insert(v.end(), lst.begin(), lst.end());
+
+  const auto origin = __gnu_test::counter::count();
+
+  {
+    __gnu_test::counter::reset();
+    std::set<std::string, std::less<std::string_view>> s;
+    s.insert(v.begin(), v.end());
+    VERIFY( s.size() == 1 );
+
+    // Allocate a node and the std::string (unless COW).
+    constexpr std::size_t increments = _GLIBCXX_USE_CXX11_ABI ? 2 : 1;
+
+    VERIFY( __gnu_test::counter::count() == origin + increments );
+    VERIFY( __gnu_test::counter::get()._M_increments == increments );
+
+    s.insert(v.begin(), v.end());
+    VERIFY( s.size() == 1 );
+
+    VERIFY( __gnu_test::counter::count() == origin + increments );
+    VERIFY( __gnu_test::counter::get()._M_increments == increments );
+  }
+  VERIFY( __gnu_test::counter::count() == origin );
+
+  {
+    __gnu_test::counter::reset();
+    std::set<std::string, std::less<std::string_view>> s;
+    s.insert(std::make_move_iterator(v.begin()),
+	     std::make_move_iterator(v.end()));
+    VERIFY( s.size() == 1 );
+
+    // Allocate a node, string is moved.
+    constexpr std::size_t increments = 1;
+
+    VERIFY( __gnu_test::counter::count() == origin + increments );
+    VERIFY( __gnu_test::counter::get()._M_increments == increments );
+  }
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  test11();
+  test12();
+  test21();
+  test22();
+  test23();
+  test03();
+  return 0;
+}

[PATCH] libstdc++: Limit allocations in _Rb_tree 1/2

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 3282 bytes --]

Here is eventually a working proposal.

Compared to the unordered container approach we need to find out what 
type is going to be used to call the comparer. Otherwise we might 
reinstantiate a temporary each time we call the comparer. For example in 
case of const char* insertion with a less<string_view> comparer we would 
create a string_view instance on each comparer call and so each time do 
a strlen.

This code is tricky and do not cover all use cases. For those uncovered 
cases the default behavior is to create a key_type instance which will 
be moved to storage if needed.

Is there any plan to create a builtin function to get help from the 
compiler to find out this type ? Something like std::invoke_result but 
giving also the actual argument types.

     libstdc++: [_Rb_tree] Limit allocations on unique insertions [PR 96088]

     Detect when invoking the comparer requires an allocation using the 
noexcept
     qualification of the functor. In this case guess the type needed to 
invoke
     the comparer and create a temporary instance used for all comparer 
invocations.
     This temporary instance will be eventually moved to storage 
location if it is to
     insert. Avoid to allocate a node and construct the stored value 
otherwise.

     libstdc++-v3/ChangeLog:

             PR libstdc++/96088
             * include/bits/stl_function.h
             (std::less<>::operator()): Add noexcept qualification.
             (std::greater::operator()): Likewise.
(std::_Identity<>::operator<_Tp2>(_Tp2&&)): New perfect forwarding operator.
(std::_Select1st<>::operator<_Pair2>(_Pair2&&)): New move operator.
             * include/bits/stl_tree.h 
(_Rb_tree<>::_ConvertToValueType<>): New helper type.
             (_Rb_tree<>::__has_firstargument): Likewise.
             (_Rb_tree<>::_S_get_key_type_aux): New helper method, use 
latter.
             (_Rb_tree<>::_S_get_key_type): New helper method, use latter.
             (_Rb_tree<>::__key_type_t): New.
             (_Rb_tree<>::__is_comparable_lhs): New.
             (_Rb_tree<>::__is_comparable_rhs): New.
             (_Rb_tree<>::__is_comparable): New, use latters.
             (_Rb_tree<>::__is_nothrow_comparable_lhs): New.
             (_Rb_tree<>::__is_nothrow_comparable_rhs): New.
             (_Rb_tree<>::__is_nothrow_comparable): New, use latters.
             (_Rb_tree<>::_S_forward_key): New.
             (_Rb_tree<>::_M_get_insert_unique_pos_tr): New.
             (_Rb_tree<>::_M_emplace_unique_kv): New.
             (_Rb_tree<>::_M_emplace_unique_aux): New, use latter.
             (_Rb_tree<>::_M_emplace_unique): New, use latter.
             (_Rb_tree<>::_Auto_node::_S_build): New.
             * testsuite/23_containers/map/96088.cc: New test case.
             * testsuite/23_containers/multimap/96088.cc: New test case.
             * testsuite/23_containers/multiset/96088.cc: New test case.
             * testsuite/23_containers/set/96088.cc: New test case.

François

[-- Attachment #2: pr96088_map.patch --]
[-- Type: text/x-patch, Size: 32241 bytes --]

diff --git a/libstdc++-v3/include/bits/stl_function.h b/libstdc++-v3/include/bits/stl_function.h
index fa03f32b1b8..f8817e2f6ae 100644
--- a/libstdc++-v3/include/bits/stl_function.h
+++ b/libstdc++-v3/include/bits/stl_function.h
@@ -395,6 +395,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _GLIBCXX14_CONSTEXPR
       bool
       operator()(const _Tp& __x, const _Tp& __y) const
+	_GLIBCXX_NOEXCEPT_IF( noexcept(__x > __y) )
       { return __x > __y; }
     };
 
@@ -405,6 +406,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _GLIBCXX14_CONSTEXPR
       bool
       operator()(const _Tp& __x, const _Tp& __y) const
+	_GLIBCXX_NOEXCEPT_IF( noexcept(__x < __y) )
       { return __x < __y; }
     };
 
@@ -1165,6 +1167,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       const _Tp&
       operator()(const _Tp& __x) const
       { return __x; }
+
+#if __cplusplus >= 201103L
+    template<typename _Tp2>
+      _Tp2&&
+      operator()(_Tp2&& __x) const noexcept
+      { return std::forward<_Tp2>(__x); }
+#endif
     };
 
   // Partial specialization, avoids confusing errors in e.g. std::set<const T>.
@@ -1183,15 +1192,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       { return __x.first; }
 
 #if __cplusplus >= 201103L
+    private:
       template<typename _Pair2>
-        typename _Pair2::first_type&
-        operator()(_Pair2& __x) const
-        { return __x.first; }
+	struct __1st_type
+	{ using type = typename _Pair2::first_type; };
+
+      template<typename _Tp, typename _Up>
+	struct __1st_type<pair<_Tp, _Up>>
+	{ using type = _Tp; };
 
+      template<typename _Tp, typename _Up>
+	struct __1st_type<const pair<_Tp, _Up>>
+	{ using type = const _Tp; };
+
+      template<typename _Pair2>
+	struct __1st_type<_Pair2&>
+	{ using type = typename __1st_type<_Pair2>::type&; };
+
+    public:
       template<typename _Pair2>
-        const typename _Pair2::first_type&
-        operator()(const _Pair2& __x) const
-        { return __x.first; }
+	typename __1st_type<_Pair2>::type&&
+	operator()(_Pair2&& __x) const noexcept
+	{ return std::forward<_Pair2>(__x).first; }
 #endif
     };
 
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index 3c331fbc952..5dae42a504c 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -534,6 +534,137 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_Rb_tree& _M_t;
       };
 
+#if __cplusplus >= 201103L
+      template<typename _ExKey, typename _Value>
+	struct _ConvertToValueType;
+
+      template<typename _Value>
+	struct _ConvertToValueType<std::_Identity<_Value>, _Value>
+	{
+	  template<typename _Kt>
+	    constexpr _Kt&&
+	    operator()(_Kt&& __k) const noexcept
+	    { return std::forward<_Kt>(__k); }
+	};
+
+      template<typename _Value>
+	struct _ConvertToValueType<std::_Select1st<_Value>, _Value>
+	{
+	  constexpr _Value&&
+	  operator()(_Value&& __x) const noexcept
+	  { return std::move(__x); }
+
+	  constexpr const _Value&
+	  operator()(const _Value& __x) const noexcept
+	  { return __x; }
+
+	  template<typename _Kt, typename _Vt>
+	    constexpr std::pair<_Kt, _Vt>&&
+	    operator()(std::pair<_Kt, _Vt>&& __x) const noexcept
+	    { return std::move(__x); }
+
+	  template<typename _Kt, typename _Vt>
+	    constexpr const std::pair<_Kt, _Vt>&
+	    operator()(const std::pair<_Kt, _Vt>& __x) const noexcept
+	    { return __x; }
+      };
+
+      template<typename _Func, typename _Kt, typename = __void_t<>>
+	struct __has_first_argument
+	{ };
+
+      template<typename _Func, typename _Kt>
+	struct __has_first_argument<_Func, _Kt,
+				__void_t<typename _Func::first_argument_type>>
+	{ using type = typename _Func::first_argument_type; };
+
+      template<typename _Func, typename _Kt>
+	using __has_first_argument_t
+	  = typename __has_first_argument<_Func, _Kt>::type;
+
+      template<typename _Func, typename _Kt,
+	       typename = __has_first_argument_t<_Func, _Kt>>
+	static typename _Func::first_argument_type
+	_S_get_key_type_aux(const _Func&, _Kt&& __kt);
+
+      template<typename _Func, typename _Kt>
+	static _Key
+	_S_get_key_type_aux(...);
+
+#if __cplusplus >= 201402L
+      template<typename _Func, typename _Kt,
+	       typename = __has_is_transparent_t<_Func, _Kt>>
+	static auto
+	_S_get_key_type(const _Func&, _Kt&& __kt)
+	-> decltype(std::forward<_Kt>(__kt));
+#endif
+
+      template<typename _Arg, typename _Kt>
+	static _Arg
+	_S_get_key_type(bool (*)(const _Arg&, const _Arg&), _Kt&&);
+
+      template<typename _Func, typename _Kt>
+	static auto
+	_S_get_key_type(const _Func& __func, _Kt&& __kt)
+	-> decltype(_S_get_key_type_aux(__func, std::forward<_Kt>(__kt)));
+
+      template<typename _Kt>
+	using __key_type_t = decltype(_S_get_key_type(
+		std::declval<_Compare>(), std::declval<_Kt>()));
+
+      template<typename _Kt>
+	using __is_comparable_lhs =
+	  __is_invocable<_Compare&, _Kt, const _Key&>;
+
+      template<typename _Kt>
+	using __is_comparable_rhs =
+	  __is_invocable<_Compare&, const _Key&, _Kt>;
+
+      template<typename _Kt>
+	using __is_comparable =
+	  __and_<__is_comparable_lhs<_Kt>, __is_comparable_rhs<_Kt>>;
+
+      template<typename _Kt>
+	using __is_nothrow_comparable_lhs =
+	  __is_nothrow_invocable<_Compare&, _Kt, const _Key&>;
+
+      template<typename _Kt>
+	using __is_nothrow_comparable_rhs =
+	  __is_nothrow_invocable<_Compare&, const _Key&, _Kt>;
+
+      template<typename _Kt>
+	using __is_nothrow_comparable =
+	  __and_<__is_nothrow_comparable_lhs<_Kt>,
+		 __is_nothrow_comparable_rhs<_Kt>>;
+
+      template<typename _Kt>
+	static __enable_if_t<
+	  __and_<__not_<is_same<__key_type_t<_Kt>, _Key>>,
+		 __is_comparable<__key_type_t<_Kt>>>::value,
+	  __conditional_t<
+	    __and_<__is_nothrow_comparable_lhs<const _Key&>,
+		   __not_<__is_nothrow_comparable<__key_type_t<_Kt>>>>::value,
+	    _Key, __key_type_t<_Kt>>>
+	_S_forward_key(_Kt&& __k)
+	{ return std::forward<_Kt>(__k); }
+
+      template<typename _Kt>
+	static __enable_if_t<
+	  __or_<is_same<__key_type_t<_Kt>, _Key>,
+		__not_<__is_comparable<__key_type_t<_Kt>>>>::value,
+	  _Key>
+	_S_forward_key(_Kt&& __k)
+	{ return { std::forward<_Kt>(__k) }; }
+
+      static const _Key&
+      _S_forward_key(const _Key& __k)
+      { return __k; }
+
+      static _Key&&
+      _S_forward_key(_Key&& __k)
+      { return std::move(__k); }
+#endif // C++11
+
     public:
       typedef _Key 				key_type;
       typedef _Val 				value_type;
@@ -833,6 +964,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       pair<_Base_ptr, _Base_ptr>
       _M_get_insert_equal_pos(const key_type& __k);
 
+#if __cplusplus >= 201103L
+      template<typename _Kt>
+	pair<_Base_ptr, _Base_ptr>
+	_M_get_insert_unique_pos_tr(const _Kt& __k);
+#endif
+
       pair<_Base_ptr, _Base_ptr>
       _M_get_insert_hint_unique_pos(const_iterator __pos,
 				    const key_type& __k);
@@ -1075,6 +1212,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
 	}
 
+      template<typename _Kt, typename _Arg>
+	std::pair<iterator, bool>
+	_M_emplace_unique_kv(_Kt&&, _Arg&&);
+
+      template<typename _Arg>
+	pair<iterator, bool>
+	_M_emplace_unique_aux(_Arg&& __arg)
+	{
+	  return _M_emplace_unique_kv(
+	    _S_forward_key(_KeyOfValue{}(std::forward<_Arg>(__arg))),
+	    std::forward<_Arg>(__arg));
+	}
+
+      template<typename _Arg>
+	pair<iterator, bool>
+	_M_emplace_unique(_Arg&& __arg)
+	{
+	  using __to_value = _ConvertToValueType<_KeyOfValue, value_type>;
+	  return _M_emplace_unique_aux(__to_value{}(std::forward<_Arg>(__arg)));
+	}
+
       template<typename... _Args>
 	pair<iterator, bool>
 	_M_emplace_unique(_Args&&... __args);
@@ -1667,6 +1825,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  return __it;
 	}
 
+	template<typename _Kt, typename _Arg, typename _Value>
+	  static _Auto_node
+	  _S_build(_Rb_tree& __t,
+		   _Kt&& __k, _Arg&& __arg, std::_Select1st<_Value>)
+	  {
+	    return
+	      { __t, std::forward<_Kt>(__k), std::forward<_Arg>(__arg).second };
+	  }
+
+	template<typename _Kt, typename _Arg, typename _Value>
+	  static _Auto_node
+	  _S_build(_Rb_tree& __t, _Kt&& __k, _Arg&&, std::_Identity<_Value>)
+	  { return { __t, std::forward<_Kt>(__k) }; }
+
 	_Rb_tree& _M_t;
 	_Link_type _M_node;
       };
@@ -2152,6 +2324,39 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return _Res(__x, __y);
     }
 
+#if __cplusplus >= 201103L
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+	   typename _Compare, typename _Alloc>
+    template<typename _Kt>
+      auto
+      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      _M_get_insert_unique_pos_tr(const _Kt& __k)
+      -> pair<_Base_ptr, _Base_ptr>
+      {
+	typedef pair<_Base_ptr, _Base_ptr> _Res;
+	_Link_type __x = _M_begin();
+	_Base_ptr __y = _M_end();
+	bool __comp = true;
+	while (__x != 0)
+	  {
+	    __y = __x;
+	    __comp = _M_impl._M_key_compare(__k, _S_key(__x));
+	    __x = __comp ? _S_left(__x) : _S_right(__x);
+	  }
+	iterator __j = iterator(__y);
+	if (__comp)
+	  {
+	    if (__j == begin())
+	      return _Res(__x, __y);
+	    else
+	      --__j;
+	  }
+	if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
+	  return _Res(__x, __y);
+	return _Res(__j._M_node, 0);
+      }
+#endif
+
   template<typename _Key, typename _Val, typename _KeyOfValue,
 	   typename _Compare, typename _Alloc>
 #if __cplusplus >= 201103L
@@ -2438,6 +2643,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	return {iterator(__res.first), false};
       }
 
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+	   typename _Compare, typename _Alloc>
+    template<typename _Kt, typename _Arg>
+      auto
+      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      _M_emplace_unique_kv(_Kt&& __k, _Arg&& __arg)
+      -> pair<iterator, bool>
+      {
+	auto __res = _M_get_insert_unique_pos_tr(__k);
+	if (__res.second)
+	  {
+	    _Auto_node __z = _Auto_node::_S_build(*this,
+	      std::forward<_Kt>(__k), std::forward<_Arg>(__arg), _KeyOfValue{});
+	    return { __z._M_insert(__res), true };
+	  }
+	return { iterator(__res.first), false };
+      }
+
   template<typename _Key, typename _Val, typename _KeyOfValue,
 	   typename _Compare, typename _Alloc>
     template<typename... _Args>
diff --git a/libstdc++-v3/testsuite/23_containers/map/96088.cc b/libstdc++-v3/testsuite/23_containers/map/96088.cc
new file mode 100644
index 00000000000..17c809240f4
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/map/96088.cc
@@ -0,0 +1,325 @@
+// { dg-do run { target c++17 } }
+// { dg-require-effective-target std_allocator_new }
+
+// Copyright (C) 2023 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// libstdc++/96088
+
+#include <string_view>
+#include <string>
+#include <map>
+#include <vector>
+
+#include <testsuite_hooks.h>
+#include <replacement_memory_operators.h>
+
+static constexpr std::initializer_list<std::pair<const char*, int>> lst =
+  { {"long_str_for_dynamic_allocating", 1} };
+
+void
+test01()
+{
+  __gnu_test::counter::reset();
+  std::map<std::string, int> m;
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+  VERIFY( !m.emplace(*lst.begin()).second );
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 4 );
+}
+
+void
+test02()
+{
+  __gnu_test::counter::reset();
+  std::map<std::string, int, std::less<std::string_view>> m;
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  VERIFY( !m.emplace(*lst.begin()).second );
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+}
+
+bool
+less_string_f(const std::string& lhs, const std::string& rhs) noexcept
+{ return lhs < rhs; }
+
+void
+test11()
+{
+  typedef bool (*less_string_t)(const std::string&,
+				const std::string&) noexcept;
+  __gnu_test::counter::reset();
+  less_string_t comparer = &less_string_f;
+  std::map<std::string, int, less_string_t> m(comparer);
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+bool
+less_string_view_f(const std::string_view& lhs,
+		   const std::string_view& rhs) noexcept
+{ return lhs < rhs; }
+
+void
+test12()
+{
+  typedef bool (*less_stringview_t) (const std::string_view&,
+				     const std::string_view&) noexcept;
+  __gnu_test::counter::reset();
+  less_stringview_t comparer = &less_string_view_f;
+  std::map<std::string, int, less_stringview_t> m(comparer);
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+}
+
+struct less_string_functor
+{
+  bool
+  operator()(const std::string& lhs,
+	     const std::string& rhs) const noexcept
+  { return lhs < rhs; }
+};
+
+void
+test21()
+{
+  __gnu_test::counter::reset();
+  std::map<std::string, int, less_string_functor> m;
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+struct less_string_view_noexcept_functor
+{
+  bool
+  operator()(const std::string_view& lhs,
+	     const std::string_view& rhs) const noexcept
+  { return lhs < rhs; }
+};
+
+void
+test22()
+{
+  __gnu_test::counter::reset();
+  std::map<std::string, int, less_string_view_noexcept_functor> m;
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+struct less_string_view_functor
+{
+  bool
+  operator()(const std::string_view& lhs,
+	     const std::string_view& rhs) const
+  { return lhs < rhs; }
+};
+
+void
+test23()
+{
+  __gnu_test::counter::reset();
+  std::map<std::string, int, less_string_view_functor> m;
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+struct less_string_view_noexcept_transparent_functor
+{
+  bool
+  operator()(const std::string_view& lhs,
+	     const std::string_view& rhs) const noexcept
+  { return lhs < rhs; }
+
+  typedef std::__is_transparent is_transparent;
+};
+
+void
+test24()
+{
+  __gnu_test::counter::reset();
+  std::map<std::string, int,
+	   less_string_view_noexcept_transparent_functor> m;
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+}
+
+struct less_string_view_transparent_functor
+{
+  bool
+  operator()(const std::string_view& lhs,
+	     const std::string_view& rhs) const
+  { return lhs < rhs; }
+
+  typedef std::__is_transparent is_transparent;
+};
+
+void
+test25()
+{
+  __gnu_test::counter::reset();
+  std::map<std::string, int, less_string_view_transparent_functor> m;
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  m.insert(lst.begin(), lst.end());
+  VERIFY( m.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+}
+
+void
+test03()
+{
+  std::vector<std::pair<std::string, int>> v;
+  v.insert(v.end(), lst.begin(), lst.end());
+
+  const auto origin = __gnu_test::counter::count();
+
+  {
+    __gnu_test::counter::reset();
+    std::map<std::string, int, std::less<std::string_view>> m;
+    m.insert(v.begin(), v.end());
+    VERIFY( m.size() == 1 );
+
+    // Allocate a node and the std::string (unless COW).
+    constexpr std::size_t increments = _GLIBCXX_USE_CXX11_ABI ? 2 : 1;
+
+    VERIFY( __gnu_test::counter::count() == origin + increments );
+    VERIFY( __gnu_test::counter::get()._M_increments == increments );
+
+    m.insert(v.begin(), v.end());
+    VERIFY( m.size() == 1 );
+
+    VERIFY( __gnu_test::counter::count() == origin + increments );
+    VERIFY( __gnu_test::counter::get()._M_increments == increments );
+  }
+  VERIFY( __gnu_test::counter::count() == origin );
+
+  {
+    __gnu_test::counter::reset();
+    std::map<std::string, int, std::less<std::string_view>> m;
+    m.insert(std::make_move_iterator(v.begin()),
+	     std::make_move_iterator(v.end()));
+    VERIFY( m.size() == 1 );
+
+    // Allocate a node. String is moved.
+    constexpr std::size_t increments = 1;
+
+    VERIFY( __gnu_test::counter::count() == origin + increments );
+    VERIFY( __gnu_test::counter::get()._M_increments == increments );
+  }
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  test11();
+  test12();
+  test21();
+  test22();
+  test23();
+  test24();
+  test25();
+  test03();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/multimap/96088.cc b/libstdc++-v3/testsuite/23_containers/multimap/96088.cc
new file mode 100644
index 00000000000..919c5e59c71
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multimap/96088.cc
@@ -0,0 +1,65 @@
+// { dg-do run { target c++17 } }
+// { dg-require-effective-target std_allocator_new }
+
+// Copyright (C) 2023 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// libstdc++/96088
+
+#include <string_view>
+#include <string>
+#include <map>
+
+#include <testsuite_hooks.h>
+#include <replacement_memory_operators.h>
+
+static constexpr std::initializer_list<std::pair<const char*, int>> lst = {
+    {"long_str_for_dynamic_allocating", 1}
+};
+
+void
+test01()
+{
+  __gnu_test::counter::reset();
+  std::multimap<std::string, int,
+		std::less<std::string_view>> foo;
+  foo.insert(lst.begin(), lst.end());
+  VERIFY( foo.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+}
+
+void
+test02()
+{
+  __gnu_test::counter::reset();
+  std::multimap<std::string, int> foo;
+  foo.insert(lst.begin(), lst.end());
+  VERIFY( foo.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/multiset/96088.cc b/libstdc++-v3/testsuite/23_containers/multiset/96088.cc
new file mode 100644
index 00000000000..2cdc08aba51
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multiset/96088.cc
@@ -0,0 +1,64 @@
+// { dg-do run { target c++17 } }
+// { dg-require-effective-target std_allocator_new }
+
+// Copyright (C) 2023 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// libstdc++/96088
+
+#include <string_view>
+#include <string>
+#include <set>
+
+#include <testsuite_hooks.h>
+#include <replacement_memory_operators.h>
+
+static constexpr std::initializer_list<const char*> lst = {
+  "long_str_for_dynamic_allocating"
+};
+
+void
+test01()
+{
+  __gnu_test::counter::reset();
+  std::multiset<std::string, std::less<std::string_view>> foo;
+  foo.insert(lst.begin(), lst.end());
+  VERIFY( foo.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+}
+
+void
+test02()
+{
+  __gnu_test::counter::reset();
+  std::multiset<std::string> foo;
+  foo.insert(lst.begin(), lst.end());
+  VERIFY( foo.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/set/96088.cc b/libstdc++-v3/testsuite/23_containers/set/96088.cc
new file mode 100644
index 00000000000..a6da8ecda27
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/set/96088.cc
@@ -0,0 +1,325 @@
+// { dg-do run { target c++17 } }
+// { dg-require-effective-target std_allocator_new }
+
+// Copyright (C) 2023 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// libstdc++/96088
+
+#include <string_view>
+#include <string>
+#include <set>
+#include <vector>
+
+#include <testsuite_hooks.h>
+#include <replacement_memory_operators.h>
+
+static constexpr std::initializer_list<const char*> lst = {
+  "long_str_for_dynamic_allocating"
+};
+
+void
+test01()
+{
+  __gnu_test::counter::reset();
+  std::set<std::string, std::greater<std::string>> s;
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+
+  s.emplace(*lst.begin());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 4 );
+}
+
+void
+test02()
+{
+  __gnu_test::counter::reset();
+  std::set<std::string, std::greater<std::string_view>> s;
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  s.emplace(*lst.begin());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+}
+
+bool
+less_string_f(const std::string& lhs, const std::string& rhs) noexcept
+{ return lhs < rhs; }
+
+void
+test11()
+{
+  typedef bool (*less_string_t)(const std::string&,
+				const std::string&) noexcept;
+  __gnu_test::counter::reset();
+  less_string_t less = &less_string_f;
+  std::set<std::string, less_string_t> s(less);
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+bool
+less_string_view_f(const std::string_view& lhs,
+		   const std::string_view& rhs) noexcept
+{ return lhs < rhs; }
+
+void
+test12()
+{
+  typedef bool (*less_stringview_t)(const std::string_view&,
+				    const std::string_view&) noexcept;
+  __gnu_test::counter::reset();
+  less_stringview_t less = &less_string_view_f;
+  std::set<std::string, less_stringview_t> s(less);
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+}
+
+struct less_string_functor
+{
+  bool
+  operator()(const std::string& lhs, const std::string& rhs) const noexcept
+  { return lhs < rhs; }
+};
+
+void
+test21()
+{
+  __gnu_test::counter::reset();
+  std::set<std::string, less_string_functor> s;
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+struct less_string_view_noexcept_functor
+{
+  bool
+  operator()(const std::string_view& lhs,
+	     const std::string_view& rhs) const noexcept
+  { return lhs < rhs; }
+};
+
+void
+test22()
+{
+  __gnu_test::counter::reset();
+  std::set<std::string, less_string_view_noexcept_functor> s;
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+struct less_string_view_functor
+{
+  bool
+  operator()(const std::string_view& lhs,
+	     const std::string_view& rhs) const
+  { return lhs < rhs; }
+};
+
+void
+test23()
+{
+  __gnu_test::counter::reset();
+  std::set<std::string, less_string_view_functor> s;
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 3 );
+}
+
+struct less_string_view_noexcept_transparent_functor
+{
+  bool
+  operator()(const std::string_view& lhs,
+	     const std::string_view& rhs) const noexcept
+  { return lhs < rhs; }
+
+  typedef std::__is_transparent is_transparent;
+};
+
+void
+test24()
+{
+  __gnu_test::counter::reset();
+  std::set<std::string,
+	   less_string_view_noexcept_transparent_functor> s;
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+}
+
+struct less_string_view_transparent_functor
+{
+  bool
+  operator()(const std::string_view& lhs,
+	     const std::string_view& rhs) const
+  { return lhs < rhs; }
+
+  typedef std::__is_transparent is_transparent;
+};
+
+void
+test25()
+{
+  __gnu_test::counter::reset();
+  std::set<std::string, less_string_view_transparent_functor> s;
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  s.insert(lst.begin(), lst.end());
+  VERIFY( s.size() == 1 );
+
+  VERIFY( __gnu_test::counter::count() == 2 );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+}
+
+void
+test03()
+{
+  std::vector<std::string> v;
+  v.insert(v.end(), lst.begin(), lst.end());
+
+  const auto origin = __gnu_test::counter::count();
+
+  {
+    __gnu_test::counter::reset();
+    std::set<std::string, std::less<std::string_view>> s;
+    s.insert(v.begin(), v.end());
+    VERIFY( s.size() == 1 );
+
+    // Allocate a node and the std::string (unless COW).
+    constexpr std::size_t increments = _GLIBCXX_USE_CXX11_ABI ? 2 : 1;
+
+    VERIFY( __gnu_test::counter::count() == origin + increments );
+    VERIFY( __gnu_test::counter::get()._M_increments == increments );
+
+    s.insert(v.begin(), v.end());
+    VERIFY( s.size() == 1 );
+
+    VERIFY( __gnu_test::counter::count() == origin + increments );
+    VERIFY( __gnu_test::counter::get()._M_increments == increments );
+  }
+  VERIFY( __gnu_test::counter::count() == origin );
+
+  {
+    __gnu_test::counter::reset();
+    std::set<std::string, std::less<std::string_view>> s;
+    s.insert(std::make_move_iterator(v.begin()),
+	     std::make_move_iterator(v.end()));
+    VERIFY( s.size() == 1 );
+
+    // Allocate a node, string is moved.
+    constexpr std::size_t increments = 1;
+
+    VERIFY( __gnu_test::counter::count() == origin + increments );
+    VERIFY( __gnu_test::counter::get()._M_increments == increments );
+  }
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  test11();
+  test12();
+  test21();
+  test22();
+  test23();
+  test24();
+  test25();
+  test03();
+  return 0;
+}

[PATCH] libstdc++: Limit allocations in _Rb_tree 2/2

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 1312 bytes --]

This one is a refinement for multimap/multiset.

It allows to have share the same key if managed with ref counting like 
the cow string.

     libstdc++: [_Rb_tree] Limit allocations on equal insertions [PR 96088]

     When inserting the same key several times prefer to insert the new 
entry using the
     current stored key_type instance if this copy is noexcept. 
Otherwise create a new
     key instance from input argument.

     libstdc++-v3/ChangeLog:

             PR libstdc++/96088
             * include/bits/cow_string.h 
(basic_string<>::basic_string(const basic_string&)):
             Add noexcept qualification when allocator is always equal.
             * include/bits/stl_tree.h 
(_Rb_tree<>::_M_get_insert_equal_pos_tr): New.
             (_Rb_tree<>::_M_emplace_equal_tr): New, use latter.
             (_Rb_tree<>::_M_emplace_equal_aux): New, use latter.
(_Rb_tree<>::_M_emplace_equal<_Arg>(_Arg&&)): New, use latter.
             * testsuite/23_containers/multimap/96088.cc (test01): Add 
check on redundant
             insertion.
             (test02): Likewise.
             * testsuite/23_containers/multiset/96088.cc (test01, 
test02): Likewise.

François

[-- Attachment #2: pr96088_multimap.patch --]
[-- Type: text/x-patch, Size: 5413 bytes --]

diff --git a/libstdc++-v3/include/bits/cow_string.h b/libstdc++-v3/include/bits/cow_string.h
index ad9929c4ad3..cdfbe5e190b 100644
--- a/libstdc++-v3/include/bits/cow_string.h
+++ b/libstdc++-v3/include/bits/cow_string.h
@@ -541,6 +541,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
        *  @param  __str  Source string.
        */
       basic_string(const basic_string& __str)
+	_GLIBCXX_NOEXCEPT_IF(_CharT_alloc_traits::_S_always_equal())
       : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(__str.get_allocator()),
 					    __str.get_allocator()),
 		    __str.get_allocator())
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index 21e9586b0a3..c3a4a97cfcf 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -968,6 +968,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       template<typename _Kt>
 	pair<_Base_ptr, _Base_ptr>
 	_M_get_insert_unique_pos_tr(const _Kt& __k);
+
+      template<typename _Kt>
+	pair<_Base_ptr, _Base_ptr>
+	_M_get_insert_equal_pos_tr(const _Kt& __k);
 #endif
 
       pair<_Base_ptr, _Base_ptr>
@@ -1225,6 +1229,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    std::forward<_Arg>(__arg));
 	}
 
+      template<typename _Kt, typename _Arg>
+	iterator
+	_M_emplace_equal_kv(_Kt&&, _Arg&&);
+
+      template<typename _Arg>
+	iterator
+	_M_emplace_equal_aux(_Arg&& __arg)
+	{
+	  return _M_emplace_equal_kv(
+	    _S_forward_key(_KeyOfValue{}(std::forward<_Arg>(__arg))),
+	    std::forward<_Arg>(__arg));
+	}
+
       template<typename _Arg>
 	pair<iterator, bool>
 	_M_emplace_unique(_Arg&& __arg)
@@ -1237,6 +1254,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	pair<iterator, bool>
 	_M_emplace_unique(_Args&&... __args);
 
+      template<typename _Arg>
+	iterator
+	_M_emplace_equal(_Arg&& __arg)
+	{
+	  using __to_value = _ConvertToValueType<_KeyOfValue, value_type>;
+	  return _M_emplace_equal_aux(__to_value{}(std::forward<_Arg>(__arg)));
+	}
+
       template<typename... _Args>
 	iterator
 	_M_emplace_equal(_Args&&... __args);
@@ -2355,6 +2380,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  return _Res(__x, __y);
 	return _Res(__j._M_node, 0);
       }
+
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+	   typename _Compare, typename _Alloc>
+    template<typename _Kt>
+      auto
+      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      _M_get_insert_equal_pos_tr(const _Kt& __k)
+      -> pair<_Base_ptr, _Base_ptr>
+      {
+	typedef pair<_Base_ptr, _Base_ptr> _Res;
+	_Link_type __x = _M_begin();
+	_Base_ptr __y = _M_end();
+	while (__x != 0)
+	  {
+	    __y = __x;
+	    __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
+	      _S_left(__x) : _S_right(__x);
+	  }
+	return _Res(__x, __y);
+      }
 #endif
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -2661,6 +2706,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	return { iterator(__res.first), false };
       }
 
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+	   typename _Compare, typename _Alloc>
+    template<typename _Kt, typename _Arg>
+      auto
+      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      _M_emplace_equal_kv(_Kt&& __k, _Arg&& __arg)
+      -> iterator
+      {
+	auto __res = _M_get_insert_equal_pos_tr(__k);
+	_Auto_node __z =
+	  (!is_nothrow_copy_constructible<key_type>::value
+	   || __res.second == _M_end()
+	   || _M_impl._M_key_compare(__k, _S_key(__res.second)))
+	  ? _S_build_node(*this, std::forward<_Kt>(__k),
+			  std::forward<_Arg>(__arg), _KeyOfValue{})
+	  : _S_build_node(*this, _S_key(__res.second),
+			  std::forward<_Arg>(__arg), _KeyOfValue{});
+	return __z._M_insert(__res);
+      }
+
   template<typename _Key, typename _Val, typename _KeyOfValue,
 	   typename _Compare, typename _Alloc>
     template<typename... _Args>
diff --git a/libstdc++-v3/testsuite/23_containers/multimap/96088.cc b/libstdc++-v3/testsuite/23_containers/multimap/96088.cc
index 919c5e59c71..1a778a0785d 100644
--- a/libstdc++-v3/testsuite/23_containers/multimap/96088.cc
+++ b/libstdc++-v3/testsuite/23_containers/multimap/96088.cc
@@ -1,4 +1,5 @@
 // { dg-do run { target c++17 } }
+// { dg-add-options no_pch }
 // { dg-require-effective-target std_allocator_new }
 
 // Copyright (C) 2023 Free Software Foundation, Inc.
@@ -20,6 +21,9 @@
 
 // libstdc++/96088
 
+#undef _GLIBCXX_USE_CXX11_ABI
+#define _GLIBCXX_USE_CXX11_ABI 0
+
 #include <string_view>
 #include <string>
 #include <map>
@@ -42,6 +46,15 @@ test01()
 
   VERIFY( __gnu_test::counter::count() == 2 );
   VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  // Allocate a node and the std::string (unless COW).
+  constexpr std::size_t increments = _GLIBCXX_USE_CXX11_ABI ? 2 : 1;
+
+  foo.insert(lst.begin(), lst.end());
+  VERIFY( foo.size() == 2 );
+
+  VERIFY( __gnu_test::counter::count() == 2 + increments );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 + increments );
 }
 
 void
@@ -54,6 +67,15 @@ test02()
 
   VERIFY( __gnu_test::counter::count() == 2 );
   VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+  // Allocate a node and the std::string (unless COW).
+  constexpr std::size_t increments = _GLIBCXX_USE_CXX11_ABI ? 2 : 1;
+
+  foo.insert(lst.begin(), lst.end());
+  VERIFY( foo.size() == 2 );
+
+  VERIFY( __gnu_test::counter::count() == 2 + increments );
+  VERIFY( __gnu_test::counter::get()._M_increments == 2 + 2 );
 }
 
 int

Re: [PATCH] libstdc++: Limit allocations in _Rb_tree 2/2

[François Dumont]

Just forget about this patch, bad idea.

The key_type might have additional data not used for the comparison. 
This data would not be preserved if we were inserting the already stored 
equivalent key instead of the user provided.


On 22/02/23 07:08, François Dumont wrote:
> This one is a refinement for multimap/multiset.
>
> It allows to have share the same key if managed with ref counting like 
> the cow string.
>
>     libstdc++: [_Rb_tree] Limit allocations on equal insertions [PR 
> 96088]
>
>     When inserting the same key several times prefer to insert the new 
> entry using the
>     current stored key_type instance if this copy is noexcept. 
> Otherwise create a new
>     key instance from input argument.
>
>     libstdc++-v3/ChangeLog:
>
>             PR libstdc++/96088
>             * include/bits/cow_string.h 
> (basic_string<>::basic_string(const basic_string&)):
>             Add noexcept qualification when allocator is always equal.
>             * include/bits/stl_tree.h 
> (_Rb_tree<>::_M_get_insert_equal_pos_tr): New.
>             (_Rb_tree<>::_M_emplace_equal_tr): New, use latter.
>             (_Rb_tree<>::_M_emplace_equal_aux): New, use latter.
> (_Rb_tree<>::_M_emplace_equal<_Arg>(_Arg&&)): New, use latter.
>             * testsuite/23_containers/multimap/96088.cc (test01): Add 
> check on redundant
>             insertion.
>             (test02): Likewise.
>             * testsuite/23_containers/multiset/96088.cc (test01, 
> test02): Likewise.
>
> François

Re: [PATCH] libstdc++: Limit allocations in _Rb_tree 2/2

[Jonathan Wakely]

On Thu, 2 Mar 2023 at 05:40, François Dumont via Libstdc++
<libstdc++@gcc.gnu.org> wrote:
>
> Just forget about this patch, bad idea.
>
> The key_type might have additional data not used for the comparison.
> This data would not be preserved if we were inserting the already stored
> equivalent key instead of the user provided.

Right. Key equivalence does not imply substitutability, or even equality.

struct Key {
  int i = 0;
  int j = 0;
  bool operator<(const Key& k) const { return i < k.j; }
  bool operator==(const Key& k) const { return i == k.i && j == k.j; }
};

Re: [PATCH] libstdc++: Limit allocations in _Rb_tree 1/2

[Jonathan Wakely]

On Wed, 22 Feb 2023 at 06:06, François Dumont via Libstdc++
<libstdc++@gcc.gnu.org> wrote:
>
> Here is eventually a working proposal.
>
> Compared to the unordered container approach we need to find out what
> type is going to be used to call the comparer. Otherwise we might
> reinstantiate a temporary each time we call the comparer. For example in
> case of const char* insertion with a less<string_view> comparer we would
> create a string_view instance on each comparer call and so each time do
> a strlen.

That's what std::less<void> is for. I don't think we need to spend
time trying to solve the problem against for std::less<T> when
std::less<void> already exists.

If the concern is strings vs const char*, we could explore your
suggestion in https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96088#c1
(keeping https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96088#c4 in
mind) so that we optimize that specific case.

> This code is tricky and do not cover all use cases. For those uncovered
> cases the default behavior is to create a key_type instance which will
> be moved to storage if needed.

Yes, it's tricky, and don't handle all cases, but slows down
compilation for all cases.

Also, I think you'll get ambiguous overloads for a comparison type
that has both first_argument_type and is_transparent defined, because
it will match two overloads.

I don't think we should be recreating the logic of transparent
comparison functions, and we shouldn't be reintroducing dependencies
on first_argument_type (in C++20 users should be able to use that
typedef for anything, e.g. make it a typedef for void, and the library
shouldn't care ... I think that would break with your patch).


> Is there any plan to create a builtin function to get help from the
> compiler to find out this type ? Something like std::invoke_result but
> giving also the actual argument types.

No, I don't think so.


>
>      libstdc++: [_Rb_tree] Limit allocations on unique insertions [PR 96088]
>
>      Detect when invoking the comparer requires an allocation using the
> noexcept
>      qualification of the functor. In this case guess the type needed to
> invoke
>      the comparer and create a temporary instance used for all comparer
> invocations.
>      This temporary instance will be eventually moved to storage
> location if it is to
>      insert. Avoid to allocate a node and construct the stored value
> otherwise.
>
>      libstdc++-v3/ChangeLog:
>
>              PR libstdc++/96088
>              * include/bits/stl_function.h
>              (std::less<>::operator()): Add noexcept qualification.
>              (std::greater::operator()): Likewise.
> (std::_Identity<>::operator<_Tp2>(_Tp2&&)): New perfect forwarding operator.
> (std::_Select1st<>::operator<_Pair2>(_Pair2&&)): New move operator.
>              * include/bits/stl_tree.h
> (_Rb_tree<>::_ConvertToValueType<>): New helper type.
>              (_Rb_tree<>::__has_firstargument): Likewise.
>              (_Rb_tree<>::_S_get_key_type_aux): New helper method, use
> latter.
>              (_Rb_tree<>::_S_get_key_type): New helper method, use latter.
>              (_Rb_tree<>::__key_type_t): New.
>              (_Rb_tree<>::__is_comparable_lhs): New.
>              (_Rb_tree<>::__is_comparable_rhs): New.
>              (_Rb_tree<>::__is_comparable): New, use latters.
>              (_Rb_tree<>::__is_nothrow_comparable_lhs): New.
>              (_Rb_tree<>::__is_nothrow_comparable_rhs): New.
>              (_Rb_tree<>::__is_nothrow_comparable): New, use latters.
>              (_Rb_tree<>::_S_forward_key): New.
>              (_Rb_tree<>::_M_get_insert_unique_pos_tr): New.
>              (_Rb_tree<>::_M_emplace_unique_kv): New.
>              (_Rb_tree<>::_M_emplace_unique_aux): New, use latter.
>              (_Rb_tree<>::_M_emplace_unique): New, use latter.
>              (_Rb_tree<>::_Auto_node::_S_build): New.
>              * testsuite/23_containers/map/96088.cc: New test case.
>              * testsuite/23_containers/multimap/96088.cc: New test case.
>              * testsuite/23_containers/multiset/96088.cc: New test case.
>              * testsuite/23_containers/set/96088.cc: New test case.
>
> François