[gcc r17-2704] libstdc++: Optimize flat_map range insertion for pair-like elements

[Patrick Palka]

https://gcc.gnu.org/g:f678da4a9930c8c0e3b4367cd2493ed26321fe54

commit r17-2704-gf678da4a9930c8c0e3b4367cd2493ed26321fe54
Author: Patrick Palka <ppalka@redhat.com>
Date:   Sat Jul 25 16:12:13 2026 -0400

    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 (i.e. pair) 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 optimally implement) 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.
    
    Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
    Reviewed-by: Jonathan Wakely <jwakely@redhat.com>

Diff:
---
 libstdc++-v3/include/std/flat_map                  | 18 +++++++----
 libstdc++-v3/testsuite/23_containers/flat_map/1.cc | 35 ++++++++++++++++++++++
 2 files changed, 48 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..d53e56a1b717 100644
--- a/libstdc++-v3/testsuite/23_containers/flat_map/1.cc
+++ b/libstdc++-v3/testsuite/23_containers/flat_map/1.cc
@@ -405,6 +405,39 @@ 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> r[] = {
+    {counter(1), counter(10)},
+    {counter(2), counter(20)},
+    {counter(3), counter(30)},
+  };
+  moves = 0;
+  m.insert_range(std::sorted_unique, std::views::as_rvalue(r));
+  VERIFY( moves == 6 );
+}
+
 void
 test()
 {
@@ -425,6 +458,7 @@ test()
   test11<throwing_vector, std::vector>();
   test12();
   test13();
+  test14();
 }
 
 constexpr
@@ -446,6 +480,7 @@ test_constexpr()
   // test11() is non-constexpr
   test12();
   // test13() is non-constexpr
+  // test14() is non-constexpr
   return true;
 }