On Wed, May 27, 2026 at 3:06 PM Patrick Palka <[email protected]> wrote:
> 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 default 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(-)
>
This one LGTM.
>
> 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
>
>
