https://gcc.gnu.org/g:457c7bb2d3dc605738f044c02c66512770cb7d10
commit r17-907-g457c7bb2d3dc605738f044c02c66512770cb7d10 Author: Patrick Palka <[email protected]> Date: Thu May 28 10:39:27 2026 -0400 libstdc++: Fix suboptimal complexity of flat_map::_M_insert 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. Reviewed-by: Tomasz Kamiński <[email protected]> Reviewed-by: Jonathan Wakely <[email protected]> Diff: --- 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
