[PATCH] libstdc++: make trees hetero equal_range O(lg n) [PR118851]

[Nathan Myers]

On 7/3/26 8:48 AM, Jonathan Wakely wrote:
>>>          {
>>> -         const_iterator __low(_M_lower_bound_tr(__k));
>>> -         auto __high = __low;
>>> -         auto& __cmp = _M_impl._M_key_compare;
>>> -         while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
>>> -           ++__high;
>>> -         return { __low, __high };
>>> +         auto __x = _M_begin(), __y = _M_end();
>>> +         while (__x)
>>> +           {
>>> +             if (_M_key_compare(_S_key(__x), __k))
>>> +               __x = _S_right(__x);
>>> +             else if (_M_key_compare(__k, _S_key(__x)))
>>> +               __y = __x, __x = _S_left(__x);
>>> +             else
>>> +               {
>>> +                 auto __xu(__x), __yu(__y);
>> Why not integrate the two line below and have:
>>                       auto __xu =   _S_right(__x), __yu = __y;
> If we did that, we should make the same change in the non-transparent
> equal_range overloads as well.
> I think that could be done separately in a follow-up (and preferably
> stop assigning to both __y and __x in a single statement using the
> comma operator).

The others use the comma operator. We could use std::exchange
in this one, with arguably clearer intent, but I wouldn't.

We can improve efficency in the common case by checking if the
result of lower_bound is more than the key, and if not, its
successor, and not calling upper_bound if one of those is
satisfied. But it would work in the other equal_range members,
so I am guessing that should be a separate patch.