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
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
