libstdc++: Fix heterogeneous equal_range complexity in rbtree containers
Heterogeneous `equal_range` operations on rbtree containers now correctly achieve logarithmic complexity.
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.
In Details
Fixes _M_equal_range_tr in libstdc++-v3/include/bits/stl_tree.h for heterogeneous lookups in std::map, std::multiset, etc. Previously, the loop condition for finding the end of the range failed to use the proper iterator comparison, causing it to scan linearly instead of utilizing the tree structure for logarithmic time complexity. The implementation now mirrors the non-heterogeneous _M_equal_range.
- libstdc++
- The C++ Standard Library implementation used by GCC.
- rbtree
- Red-black tree, a self-balancing binary search tree used to implement associative containers like
std::mapandstd::setin C++. - heterogeneous
- In the context of C++ standard library containers, refers to operations that allow keys of a different, but comparable, type than the container's key type. For example, searching a
std::map<int, Value>using adoublethat can be converted toint. - equal_range
- A container member function that returns a pair of iterators defining the range of elements equivalent to a given key. For associative containers, this range should be found efficiently.
- O(lg n)
- Logarithmic time complexity. An operation with this complexity scales very well with input size, meaning it performs a small, constant number of steps per power of two increase in input size.