Date: Fri, 5 Jun 2026 12:09:39 +0200
An annoyance with equal_range on [unordered] associative containers:
Associative containers have an equal_range member function that returns
a std::pair of iterators, which is not a range (as defined by
std::ranges::range) and cannot be iterated over directly.
The standard library provides no easy way to convert a pair of iterators
into a range.
ranges::equal_range does provide a true range, but it has terrible
performance for associative containers without random access iterators,
and it produces undefined behavior (usually in the form of incorrect
results) on unordered associative containers.
There are several ways this could be fixed:
An additional member function (true_equal_range?) could be added to the
existing [unordered] associative containers. This is less than ideal
because it leaves user-defined [unordered] associative containers behind.
Overloads for std::begin and std::end could be added for std::pairs of
iterators. This would be my preferred solution, but it could break
existing code. It also prevents treating std::pair<T, T> as a range of
two elements of type T.
A constructor that takes a std::pair of iterators could be added to
std::ranges::subrange. This should be a fairly safe addition to the
standard, although it can break user code in pathological cases.
Add a free function to convert a std::pair of iterators into a
std::ranges::subrange. This is the safest solution; highly unlikely to
break user code and any user code it does breaks is the fault of the user.
Code could be added to ranges::equal_range to handle [unordered]
associative containers correctly. Although this sounds good in theory,
in practice it may not be possible to verify that the ordering passed to
ranges::equal_range is the same as the ordering used by the container.
Associative containers have an equal_range member function that returns
a std::pair of iterators, which is not a range (as defined by
std::ranges::range) and cannot be iterated over directly.
The standard library provides no easy way to convert a pair of iterators
into a range.
ranges::equal_range does provide a true range, but it has terrible
performance for associative containers without random access iterators,
and it produces undefined behavior (usually in the form of incorrect
results) on unordered associative containers.
There are several ways this could be fixed:
An additional member function (true_equal_range?) could be added to the
existing [unordered] associative containers. This is less than ideal
because it leaves user-defined [unordered] associative containers behind.
Overloads for std::begin and std::end could be added for std::pairs of
iterators. This would be my preferred solution, but it could break
existing code. It also prevents treating std::pair<T, T> as a range of
two elements of type T.
A constructor that takes a std::pair of iterators could be added to
std::ranges::subrange. This should be a fairly safe addition to the
standard, although it can break user code in pathological cases.
Add a free function to convert a std::pair of iterators into a
std::ranges::subrange. This is the safest solution; highly unlikely to
break user code and any user code it does breaks is the fault of the user.
Code could be added to ranges::equal_range to handle [unordered]
associative containers correctly. Although this sounds good in theory,
in practice it may not be possible to verify that the ordering passed to
ranges::equal_range is the same as the ordering used by the container.
-- Rainer Deyke - rainerd_at_[hidden]
Received on 2026-06-05 10:09:49
