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
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;
+}
