The Interesting Evolution of std::equal_range

Published January 10, 2022

The good old std::equal_range STL algorithm, which has been in the STL since C++98, has evolved along with the versions of C++.

Starting from a poor interface and now a much better one, its story is an interesting example of how to improve the abstraction of an interface.

(Good?) old C++98 `equal_range`

The first version of std::equal_range (that is still present in the standard in C++20, albeit with a constexpr), and the only one that was available before C++17, has this prototype:

template<class ForwardIterator, class T>
std::pair<ForwardIterator, ForwardIterator> 
    equal_range(ForwardIterator first, ForwardIterator last, const T& value);

equal_range takes a sorted range (in the form of two iterators) and a value, and it indicates where the values of the range equivalent the value passed in are located.

I say “equivalent” rather than “equal” because equivalence is different from equality, but if you’re not sure about the difference between equivalence and equality then we can just talk of equality, because this doesn’t change anything to our purpose here.

Anyway, equal_range allows to locate the values that are equivalent to the one that is passed in. Since the range is sorted, those values are next to each other, if they exist at all. This means that those values form a subrange within the input range.

This is what the return type of equal_range represents. It is a pair of iterators, the first element of that pair being the begin of that subrange, and the second one being the end (meaning one position past the last element) of that subrange.

And if there is no such equivalent value in the input range, then the two iterators are equal to each other, thus representing an empty range.

An abstraction problem

Here was the code we could write in C++98 to use std::equal_range:

auto const numbers = std::vector<int>{1, 2, 3, 3, 3, 5, 6};
std::pair<std::vector<int>::const_iterator, std::vector<int>::const_iterator> const threes =
    std::equal_range(numbers.begin(), numbers.end(), 3);

There are a lot of characters in this snippet of code to express not so much.

And a usage could look like this:

std::for_each(threes.first, threes.second, myFunction);

There is also an important issue in this usage: threes doesn’t look like a range. Its type says that it is a pair of (unrelated) iterators. The names of the members of the pair also say that they are unrelated: one happens to be first and the other one second, as opposed to a begin and an end.

The pair is missing the semantics of a range, even though its purpose is to represent a range. But on the other hand, we could argue that we don’t need more than two iterators to represent a range.

The thing is that a range can be implemented with two iterators, but its interface should show that it is a range. What we pass to std::for_each should look like “begin” and “end” and not “first” and “second”. Because of the return type of equal_range that is a pair, the above usage is too low in terms of level of abstraction.

C++11: the code gets more concise

C++11 brought auto, which makes the calling expression more terse:

auto const numbers = std::vector<int>{1, 2, 3, 3, 3, 5, 6};
auto const threes = std::equal_range(numbers.begin(), numbers.end(), 3);

However, our design problem of abstraction is not fixed, as the return value of std::equal_range remains at the low level of abstraction, which we can still observe in the using code:

std::for_each(threes.first, threes.second, myFunction);

C++17: structured bindings

C++17 didn’t change the return type of equal_range, but with structured bindings, we are now free to use a better naming than “first” and “second”.

We can create iterators with names that are at the level of abstraction of the iterators of a range, and not at the one of a pair:

auto const numbers = std::vector<int>{1, 2, 3, 3, 3, 5, 6};
auto const [threesBegin, threesEnd] = std::equal_range(numbers.begin(), numbers.end(), 3);

Structured bindings allow to initialize several values from the various elements in a pair or tuple.

We could achieve this with C++11’s std::tie as well, but with less concise code:

auto const numbers = std::vector<int>{1, 2, 3, 3, 3, 5, 6};
std::vector<int>::const_iterator const threesBegin, threesEnd;
std::tie(threesBegin, threesEnd) = std::equal_range(numbers.begin(), numbers.end(), 3);

As a result, the values returned by equal_range are at a higher level of abstraction, which we can observe in the using code:

std::for_each(threesBegin, threesEnd, myFunction);

C++20: the range abstraction

C++20 added the ranges library, that defines a host of functions and types that represent or use ranges. They no longer force us to go through iterators. Indeed, iterators are higher in abstraction than pairs, but lower than ranges.

The Ranges library, in its algorithms, contains an equal_range. It is in the namespace std::ranges. Here is a simplified version of one of its overloads (that omits projectors and comparators, which we’ll talk about in a later post):

template<forward_range R, class T>
constexpr safe_subrange_t<R> ranges::equal_range(R&& range, const T& value);

What matters for our purpose in this prototype is that equal_range returns an object that is a range. This is something we can call begin and end on, or that we can directly pass to other algorithms (indeed, note that this overload takes a range as input).

No more iterators, no more pairs, equal_range finally returns something at the level of abstraction of its description: a range.

Levels of abstraction

This analysis shows us the evolution of the return type of equal_range, that benefited from the evolution of the C++ language and of its standard library.

It’s a good example for designing our own interfaces, and in particular our return types. What type is a function supposed to return? The one that matches its level of abstraction.

A good rule of thumb for this is the terms you would use to explain if you were to describe the purpose of the function. As often, it all comes down to levels of abstraction.