On Mon, 13 Jul 2026, Tomasz Kaminski wrote:
>
>
> On Mon, Jul 13, 2026 at 5:22 PM Patrick Palka <[email protected]> wrote:
> Tested on x86_64-pc-linux-gnu, does this look OK for trunk and perhaps
> 16?
> I'm not sure if it's worth avoiding dereferencing *__first twice in this
> special case, but I figured we might as well?
>
> -- >8 --
>
> When inserting a range of pair-like elements we can avoid constructing a
> value_type temporary and instead obtain the corresponding key and value
> to insert directly from *__first.
>
> libstdc++-v3/ChangeLog:
>
> * include/std/flat_map (flat_map::_M_insert): Avoid constructing
> value_type temporary when the iterator already has pair-like
> elements.
> ---
> libstdc++-v3/include/std/flat_map | 17 ++++++++++++++---
> 1 file changed, 14 insertions(+), 3 deletions(-)
>
> LGTM, only small suggestions.
>
> diff --git a/libstdc++-v3/include/std/flat_map
> b/libstdc++-v3/include/std/flat_map
> index b82d41b4f5e1..1815ced51225 100644
> --- a/libstdc++-v3/include/std/flat_map
> +++ b/libstdc++-v3/include/std/flat_map
> @@ -637,9 +637,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> auto __n = size();
> for (; __first != __last; ++__first)
> {
>
> I do not think we need this braces for nesting.
Fixed.
> - value_type __value = *__first;
> - _M_cont.keys.emplace_back(std::move(__value.first));
> - _M_cont.values.emplace_back(std::move(__value.second));
> + if constexpr (__pair_like<iter_reference_t<_Iter>>)
> + {
> + auto&& __value = *__first;
> + _M_cont.keys.emplace_back
> +
> (std::get<0>(std::forward<decltype(__value)>(__value)));
> + _M_cont.values.emplace_back
> +
> (std::get<1>(std::forward<decltype(__value)>(__value)));
>
> // Maybe we could alias iter_reference_t<_Iter> and replace the
> decltypes(__value) and auto&&?
Sounds good. Avoiding temporary materialization and an intermediate
reference should be cheaper with -O0.
> + }
> + else
> + {
> + value_type __value = *__first;
> + _M_cont.keys.emplace_back(std::move(__value.first));
> +
> _M_cont.values.emplace_back(std::move(__value.second));
> + }
> }
> auto __zv = views::zip(_M_cont.keys, _M_cont.values);
> if (__is_sorted)
> --
> 2.55.0.122.gf85a7e6620
>
> Do you think it will be worth to have a test that will count number of moves,
> when
> we pass sourted_unique flag is passed?
Sure. Like so?
Changes in v2:
- Addresses Tomasz's comments
- Clarified relevance of LWG 4499
-- >8 --
Subject: [PATCH v2] libstdc++: Optimize flat_map range insertion for pair-like
elements
When inserting a range of pair-like elements we can avoid constructing a
value_type temporary and instead obtain the corresponding key and value
directly from *__first.
This came up when looking at LWG 4499 for flat_set::insert_range (which
I think we already implement, with no extra std::move) but it prompted
me to look at flat_map::insert_range during which I noticed this extra
std::move.
libstdc++-v3/ChangeLog:
* include/std/flat_map (flat_map::_M_insert): Avoid constructing
value_type temporary when the iterator already has pair-like
elements.
* testsuite/23_containers/flat_map/1.cc (test14): New test.
---
libstdc++-v3/include/std/flat_map | 18 +++++++---
.../testsuite/23_containers/flat_map/1.cc | 34 +++++++++++++++++++
2 files changed, 47 insertions(+), 5 deletions(-)
diff --git a/libstdc++-v3/include/std/flat_map
b/libstdc++-v3/include/std/flat_map
index b82d41b4f5e1..ad5fddfe29e1 100644
--- a/libstdc++-v3/include/std/flat_map
+++ b/libstdc++-v3/include/std/flat_map
@@ -635,12 +635,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
auto __guard = _M_make_clear_guard();
auto __n = size();
+ using __ref = iter_reference_t<_Iter>;
for (; __first != __last; ++__first)
- {
- value_type __value = *__first;
- _M_cont.keys.emplace_back(std::move(__value.first));
- _M_cont.values.emplace_back(std::move(__value.second));
- }
+ if constexpr (__pair_like<__ref>)
+ {
+ __ref __value = *__first;
+
_M_cont.keys.emplace_back(std::get<0>(std::forward<__ref>(__value)));
+
_M_cont.values.emplace_back(std::get<1>(std::forward<__ref>(__value)));
+ }
+ else
+ {
+ value_type __value = *__first;
+ _M_cont.keys.emplace_back(std::move(__value.first));
+ _M_cont.values.emplace_back(std::move(__value.second));
+ }
auto __zv = views::zip(_M_cont.keys, _M_cont.values);
if (__is_sorted)
_GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(__zv.begin() + __n,
__zv.end(),
diff --git a/libstdc++-v3/testsuite/23_containers/flat_map/1.cc
b/libstdc++-v3/testsuite/23_containers/flat_map/1.cc
index 0cd06b72e96c..0e539af3e5f2 100644
--- a/libstdc++-v3/testsuite/23_containers/flat_map/1.cc
+++ b/libstdc++-v3/testsuite/23_containers/flat_map/1.cc
@@ -405,6 +405,38 @@ test13()
VERIFY( std::ranges::equal(s.values(), (int[]){3, 1, 2}) );
}
+void
+test14()
+{
+ // Verify optimal number of moves in flat_map::insert_range for sorted_unique
+ static int moves;
+ struct counter
+ {
+ int val;
+ constexpr counter() = default;
+ constexpr counter(int v) : val(v) {}
+ constexpr counter(const counter&) = default;
+ constexpr counter(counter&& o) noexcept : val(o.val) { ++moves; }
+ constexpr counter& operator=(const counter& o) = default;
+ constexpr counter& operator=(counter&& o) noexcept {
+ val = o.val;
+ ++moves;
+ return *this;
+ }
+ constexpr bool operator==(const counter&) const = default;
+ constexpr auto operator<=>(const counter& o) const = default;
+ };
+
+ std::flat_map<counter, counter> m;
+ std::pair<counter, counter> s[] = {
+ {counter(1), counter(10)},
+ {counter(2), counter(20)}
+ };
+ moves = 0;
+ m.insert_range(std::sorted_unique, std::views::as_rvalue(s));
+ VERIFY( moves == 4 );
+}
+
void
test()
{
@@ -425,6 +457,7 @@ test()
test11<throwing_vector, std::vector>();
test12();
test13();
+ test14();
}
constexpr
@@ -446,6 +479,7 @@ test_constexpr()
// test11() is non-constexpr
test12();
// test13() is non-constexpr
+ // test14() is non-constexpr
return true;
}
--
2.55.0.178.gd35c5399e3
