Landing: 6fc5746a5e80
Project / Subsystem
gcc / libstdc++
Date
2026-06-05
Author
Nathan Myers
Commit
6fc5746a5e809e4f22f343eb51bb963cd151ee7e
Source
github
Perf win
Yes
Breaking
No
All attributes
- project
- gcc
- subsystem
- libstdc++
- patch_id
- —
- commit_hash
- 6fc5746a5e809e4f22f343eb51bb963cd151ee7e
- source_type
- github
- headline
- libstdc++: Fix heterogeneous equal_range complexity in rbtree containers
- tldr
- Heterogeneous `equal_range` operations on rbtree containers now correctly achieve logarithmic complexity.
- author
- Nathan Myers
- outcome
- committed
- performance_win
- true
- breaking_change
- false
- series_id
- —
- series_parts
- []
- tags
-
- • libstdc++
- • performance
- • c++
- • container
- discussion_id_link
- —
- bugzilla_pr
- —
- date
- 2026-06-05T00:00:00.000Z
The heterogeneous-key versions of equal_range in libstdc++‘s rbtree-based containers (map, multimap, set, multiset) previously had linear complexity because they iterated through matching elements. This patch corrects the implementation to match the logarithmic complexity of the non-heterogeneous versions, ensuring efficient searching. New test cases verify the corrected behavior.