On Fri, 4 Apr 2025, Tomasz Kaminski wrote:
>
>
> On Fri, Apr 4, 2025 at 6:07 PM Tomasz Kaminski <[email protected]> wrote:
>
>
> On Fri, Apr 4, 2025 at 5:50 PM Patrick Palka <[email protected]> wrote:
> flat_set::emplace (and flat_multiset) currently unconditionally
> constructs an object outside of the container, but if we're passed
> a value_type object we can and should avoid that.
>
> PR libstdc++/119620
>
> libstdc++-v3/ChangeLog:
>
> * include/std/flat_set (_Flat_set_impl::_M_try_emplace): Split
> out into two overloads, one taking at least one argument and one
> taking zero arguments. Turn __k into an auto&& reference bound
> to __arg if it's already a value_type otherwise bound to a
> lifetime-extended value_type temporary.
> * testsuite/23_containers/flat_multiset/1.cc (test08): New test.
> * testsuite/23_containers/flat_set/1.cc (test08): New test.
> ---
> libstdc++-v3/include/std/flat_set | 20 +++++++++++++----
> .../23_containers/flat_multiset/1.cc | 22 +++++++++++++++++++
> .../testsuite/23_containers/flat_set/1.cc | 20 +++++++++++++++++
> 3 files changed, 58 insertions(+), 4 deletions(-)
>
> diff --git a/libstdc++-v3/include/std/flat_set
> b/libstdc++-v3/include/std/flat_set
> index a7b0b8aef15..3e15d1af416 100644
> --- a/libstdc++-v3/include/std/flat_set
> +++ b/libstdc++-v3/include/std/flat_set
> @@ -350,12 +350,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> { return _M_cont.max_size(); }
>
> // modifiers
> - template<typename... _Args>
> + template<typename _Arg, typename... _Args>
> pair<iterator, bool>
> - _M_try_emplace(optional<const_iterator> __hint, _Args&&...
> __args)
> + _M_try_emplace(optional<const_iterator> __hint, _Arg&& __arg,
> _Args&&... __args)
>
> map.try_emplace(key) is valid construct, and commonly used to value construct
> value type. For example operator[] is defined in terms of it.
> {
> // TODO: Simplify and audit the hint handling.
> - value_type __k(std::forward<_Args>(__args)...);
> + auto&& __k = [&] -> decltype(auto) {
> + if constexpr (sizeof...(_Args) == 0
> + && same_as<remove_cvref_t<_Arg>, value_type>)
> + return std::forward<_Arg>(__arg);
>
> I think you can do sizeof..(_Args) == 1 and return
> (std::forward<_Args>(__args), ...);
> + else
> + return value_type(std::forward<_Arg>(__arg),
> + std::forward<_Args>(__args)...);
> + }();
> typename container_type::iterator __it;
> int __r = -1, __s = -1;
> if (__hint.has_value()
> @@ -397,11 +404,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> return {__it, false};
>
> auto __guard = _M_make_clear_guard();
> - __it = _M_cont.insert(__it, std::move(__k));
> + __it = _M_cont.insert(__it, std::forward<decltype(__k)>(__k));
> __guard._M_disable();
> return {__it, true};
> }
>
> + template<typename... _Args>
> + pair<iterator, bool>
> + _M_try_emplace(optional<const_iterator> __hint)
> + { return _M_try_emplace(__hint, value_type()); }
>
> Ah, I haven't noticed this overload that restores _M_try_empalce. But this
> causes additional move, so I think I prefer my suggestion.
I'd expect there would be just one move in that case, when __k is moved
from in the _M_cont.insert call? There should be no move when we e.g.
bind __k to the default-constructed value_type.
> +
> template<typename... _Args>
> requires is_constructible_v<value_type, _Args...>
> __emplace_result_t
> diff --git
> a/libstdc++-v3/testsuite/23_containers/flat_multiset/1.cc
> b/libstdc++-v3/testsuite/23_containers/flat_multiset/1.cc
> index dc3cecd9720..7d9a33c6b00 100644
> --- a/libstdc++-v3/testsuite/23_containers/flat_multiset/1.cc
> +++ b/libstdc++-v3/testsuite/23_containers/flat_multiset/1.cc
> @@ -214,6 +214,27 @@ void test07()
> #endif
> }
>
> +void
> +test08()
> +{
> + // PR libstdc++/119620 -- flat_set::emplace always constructs
> element on the stack
> + static int copy_counter;
> + struct A {
> + A() { }
> + A(const A&) { ++copy_counter; }
> + A& operator=(const A&) { ++copy_counter; return *this; }
> + auto operator<=>(const A&) const = default;
> + };
> + std::vector<A> v;
> + v.reserve(2);
> + std::flat_multiset<A> s(std::move(v));
> + A a;
> + s.emplace(a);
> + VERIFY( copy_counter == 1 );
> + s.emplace(a);
> + VERIFY( copy_counter == 2 );
> +}
> +
> int
> main()
> {
> @@ -225,4 +246,5 @@ main()
> test05();
> test06();
> test07();
> + test08();
> }
> diff --git a/libstdc++-v3/testsuite/23_containers/flat_set/1.cc
> b/libstdc++-v3/testsuite/23_containers/flat_set/1.cc
> index 90f5855859f..ed24fab785b 100644
> --- a/libstdc++-v3/testsuite/23_containers/flat_set/1.cc
> +++ b/libstdc++-v3/testsuite/23_containers/flat_set/1.cc
> @@ -229,6 +229,25 @@ void test07()
> #endif
> }
>
> +void
> +test08()
> +{
> + // PR libstdc++/119620 -- flat_set::emplace always constructs
> element on the stack
> + static int copy_counter;
> + struct A {
> + A() { }
> + A(const A&) { ++copy_counter; }
> + A& operator=(const A&) { ++copy_counter; return *this; }
> + auto operator<=>(const A&) const = default;
> + };
> + std::flat_set<A> s;
> + A a;
> + s.emplace(a);
> + VERIFY( copy_counter == 1 );
> + s.emplace(a);
> + VERIFY( copy_counter == 1 );
> +}
> +
> int
> main()
> {
> @@ -240,4 +259,5 @@ main()
> test05();
> test06();
> test07();
> + test08();
> }
> --
> 2.49.0.111.g5b97a56fa0
>
>
>
