Landing: 457c7bb2d3dc
Project / Subsystem
gcc / libstdc++
Date
2026-05-28
Author
Patrick Palka
Commit
457c7bb2d3dc605738f044c02c66512770cb7d10
Source
github
Perf win
Yes
Breaking
No
All attributes
- project
- gcc
- subsystem
- libstdc++
- patch_id
- —
- commit_hash
- 457c7bb2d3dc605738f044c02c66512770cb7d10
- source_type
- github
- headline
- libstdc++: Improve complexity of flat_map insertion.
- tldr
- The flat_map::_M_insert function now merges in linearithmic time, rather than logarithmic time, for sorted input.
- author
- Patrick Palka
- outcome
- committed
- performance_win
- true
- breaking_change
- false
- series_id
- —
- series_parts
- []
- tags
-
- • libstdc++
- • containers
- • flat_map
- • performance
- discussion_id_link
- —
- bugzilla_pr
- —
- date
- 2026-05-28T00:00:00.000Z
The flat_map::_M_insert function now has optimal complexity N + M log M instead of N log N when inserting already-sorted data. This improvement uses ranges::inplace_merge and views::zip which are now correctly C++20 iterator aware. This change should improve the performance of inserting sorted data into flat_map.