https://gcc.gnu.org/bugzilla/show_bug.cgi?id=118851
--- Comment #2 from GCC Commits <cvs-commit at gcc dot gnu.org> --- The master branch has been updated by Nathan Myers <[email protected]>: https://gcc.gnu.org/g:6fc5746a5e809e4f22f343eb51bb963cd151ee7e commit r17-2267-g6fc5746a5e809e4f22f343eb51bb963cd151ee7e Author: Nathan Myers <[email protected]> Date: Thu Jun 4 23:42:11 2026 -0400 libstdc++: make trees hetero equal_range O(lg n) [PR118851] As shipped, the heterogeneous-key members equal_range of rbtree containers map, multimap, set, and multiset walk the entire range calling the predicate, in violation of the requirement for logarithmic complexity. This patch revises them to match the behavior of the non-heterogeneous multimap and multiset members, and provides tests to verify it. libstdc++-v3/Changelog: PR libstdc++/118851 * include/bits/stl_tree.h (_M_equal_range_tr): Rewrite to match non-heterogeneous equal_range implementation. * testsuite/23_containers/map/operations/hetero/equal_range.cc: New test. * testsuite/23_containers/multimap/operations/hetero/equal_range.cc: Same. * testsuite/23_containers/multiset/operations/hetero/equal_range.cc: Same. * testsuite/23_containers/set/operations/hetero/equal_range.cc: Same.
