[PATCH 1/3] libstdc++: Fix suboptimal complexity of flat_map::_M_insert

[Patrick Palka]

Ever since r16-1742 ranges::inplace_merge is now correctly C++20 iterator
aware which allows us to idiomatically implement this helper with the
correct optimal complexity N + M log M instead of N log N.

libstdc++-v3/ChangeLog:

	* include/std/flat_map (_Flat_map_impl::_M_insert): New bool
	parameter __is_sorted defaulted to false.  Reimplement using
	views::zip and ranges::inplace_merge.
	(_Flat_map_impl::insert): In the __sorted_t overload, pass
	__is_sorted=true to _M_insert.
---
 libstdc++-v3/include/std/flat_map | 32 +++++++++----------------------
 1 file changed, 9 insertions(+), 23 deletions(-)

diff --git a/libstdc++-v3/include/std/flat_map b/libstdc++-v3/include/std/flat_map
index 18f06e6bdaf8..a51c6625d54a 100644
--- a/libstdc++-v3/include/std/flat_map
+++ b/libstdc++-v3/include/std/flat_map
@@ -602,13 +602,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       template<typename _Iter, typename _Sent>
 	_GLIBCXX26_CONSTEXPR
 	void
-	_M_insert(_Iter __first, _Sent __last)
+	_M_insert(_Iter __first, _Sent __last, bool __is_sorted = false)
 	{
-	  // FIXME: This implementation fails its complexity requirements.
-	  // We can't idiomatically implement an efficient version (as in the
-	  // disabled code) until ranges::inplace_merge is fixed to dispatch
-	  // on iterator concept instead of iterator category.
-#if 0
 	  auto __guard = _M_make_clear_guard();
 	  auto __n = size();
 	  for (; __first != __last; ++__first)
@@ -618,22 +613,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      _M_cont.values.emplace_back(std::move(__value.second));
 	    }
 	  auto __zv = views::zip(_M_cont.keys, _M_cont.values);
-	  ranges::sort(__zv.begin() + __n, __zv.end(), value_comp());
-	  ranges::inplace_merge(__zv.begin(), __zv.begin() + __n, __zv.end(), value_comp());
+	  if (__is_sorted)
+	    _GLIBCXX_DEBUG_ASSERT(ranges::is_sorted(__zv.begin() + __n, __zv.end(),
+						    value_comp()));
+	  else
+	    ranges::sort(__zv.begin() + __n, __zv.end(), value_comp());
+	  ranges::inplace_merge(__zv.begin(), __zv.begin() + __n, __zv.end(),
+				value_comp());
 	  if constexpr (!_Multi)
 	    _M_unique();
-	  __guard._M_cont = nullptr;
-#else
-	  auto __guard = _M_make_clear_guard();
-	  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));
-	    }
-	  _M_sort_uniq();
 	  __guard._M_disable();
-#endif
 	}
 
     public:
@@ -647,10 +636,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_GLIBCXX26_CONSTEXPR
 	void
 	insert(__sorted_t, _InputIterator __first, _InputIterator __last)
-	{
-	  // FIXME: This implementation fails its complexity requirements; see above.
-	  insert(std::move(__first), std::move(__last));
-	}
+	{ _M_insert(std::move(__first), std::move(__last), true); }
 
       template<__detail::__container_compatible_range<value_type> _Rg>
 	_GLIBCXX26_CONSTEXPR
-- 
2.54.0.rc1.54.g60f07c4f5c