https://gcc.gnu.org/bugzilla/show_bug.cgi?id=118851
Bug ID: 118851
Summary: _Rb_tree::_M_equal_range_tr has linear complexity
Product: gcc
Version: 15.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: libstdc++
Assignee: unassigned at gcc dot gnu.org
Reporter: redi at gcc dot gnu.org
Target Milestone: ---
template<typename _Kt,
typename _Req = __has_is_transparent_t<_Compare, _Kt>>
pair<const_iterator, const_iterator>
_M_equal_range_tr(const _Kt& __k) const
{
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 };
}
This does a linear walk to find the upper bound. This is OK for a small number
of equivalent elements, or for unique keys, but fails to meet the logarithmic
complexity requirement for a large number of equivalent elements in a
multiset/multimap.
We should do what the _M_equal_range function does, and perform another binary
search on the portion of the container that follows the lower bound.
Or we could consider deciding whether to do a linear search or binary tree
lookup based on log2(this->size()).
