Understanding equal_range

std::equal_range is a general purpose standard algorithm used to find a sub-range of values in a given sorted or at least partitioned range. In this post, I will explain how the algorithm works.

The overloads, as of C++20, are as follows:

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

template< class ForwardIt, class T, class Compare >
constexpr std::pair<ForwardIt,ForwardIt> 
              equal_range(ForwardIt first, ForwardIt last, const T& value, Compare comp);

Both overloads take a range of elements to examine and a value to compare the elements to. In addition, the second overload also takes a binary predicate used to compare the elements of the range with the supplied value. The first overload uses operator< instead. The input range, however, must be either fully sorted or partially ordered with respect to value, as follows:

• all the elements for which the expression e < value or comp(e, value) is true must come before all the elements for which the expression is false.
• all the elements for which the expression !(value < e) or !comp(value, e) is true must come before all the elements for which the expression is false.
• for all elements, if e < value or comp(e, value) is true then !(value < e) or !comp(value, e) is also true.

The value returned by the function is a pair of iterators that define the result sub-range:

• if a sub-range is found then the first iterator points to the first element that is not less than value and the second iterator points to the first element greater than value.
• if there are no elements not less than value, last is returned as the first iterator.
• if there are no elements greater than value, last is returned as the second iterator.

The result iterators (first and second, respectively) may also be obtained with std::lower_bound() and std::upper_bound.

std::equal_range performs a number of comparisons logarithmic in the input range size; this number does not exceed 2 * log2(last - first) + O(1) comparisons.

To better understand how this works let us look at some examples, and for this, we will consider the following input range.

std::vector<int> v{ 1,1,2,3,5,7,7,8 };

Conceptually, this looks as follows:

If we search for value 7, then the result is a sub-range with two elements. The first iterator returned points to the first element 7, and the second iterator returned points to 8 because this is the first element greater than the value.

auto [first, last] = std::equal_range(std::cbegin(v), std::cend(v), 7);

If we search for value 4, then the result is an empty sub-range because there is no such element in the input range. In this case, the first iterator returned points to 5 because this is the first element not less than 4; the second iterator points also to the element 5 because this is the first element greater than 4.

auto [first, last] = std::equal_range(std::cbegin(v), std::cend(v), 4);

There are two more possible cases when an element is not found. The first is when there is no element less than the values to search for. In our example, this happens if we search for value 0. The result, basically, falls into the same category as previously: the first iterator returned points to the first element 1, because that is the first value not less than 0; the second iterator, also points to the first element 1 because that is the first element greater than 0.

auto [first, last] = std::equal_range(std::cbegin(v), std::cend(v), 0);

The second case though, is when there is no element not less or greater (which in this particular example are the same) than the search values. This can happen in our example if we search for the value 9. In this case, the last element of the input range is returned for both the first and the second iterator.

auto [first, last] = std::equal_range(std::cbegin(v), std::cend(v), 9);

As you can see from these examples when the sub-range is empty the returned first and second iterators are both equal.

In all the examples so far, the input range was fully sorted. However, the algorithm also works when the range is only partitioned. Let us take the following example:

std::vector<int> v{ 3,1,2,1,7,7,8,5 };

The input range is not sorted; however, it is partitioned with respect for value 4:

• if we search for value 4, then we can see that all the elements less than 4 are preceding all the elements greater than 4, even though they are not in order. In this case, the result iterators are as follows:
  
• if we search for value 0, we can see that all the elements of the range are greater than 0. In this case, the result iterators are as follows:
  
• if we search for value 9, we can see that all the elements of the range are smaller than 9. In this case, the result iterators are as follows:
  

In all these cases, we can use std::equal_range on the input range. However, searching for value 7 for instance will not work because not all the elements smaller than 7 are preceeding all the elements greater than 7. In this particular example, the result sub-range will also include the element 5, as shown in the following image:

In the next example, a rectangle class is defined with width and height as properties but also area computed from the two. Two rectangles that have the same width and height are equal but two rectangles that have the same area (such as 2×4 and 4×2) are equivalent.

struct rect
{
   int width_;
   int height_;

   constexpr rect (int const w = 0, int const h = 0):
      width_(w), height_(h)
   {}

   constexpr int area() const noexcept { return width_ * height_; }
   constexpr int width() const noexcept { return width_; }
   constexpr int height() const noexcept { return height_; }
};

constexpr bool operator==(rect const & r1, rect const & r2) noexcept
{
   return r1.width() == r2.width() && r1.height() == r2.height();
}

constexpr bool equivalent(rect const & r1, rect const & r2) noexcept
{
   return r1.area() == r2.area();
}

We can define the following range, which, conceptually, may look as shown below:

std::vector<rect> rects{ rect {1,1}, rect {2,2}, rect {7,1},
                         rect {2,4}, rect {4,2}, rect {8,1}, rect {5,2} };

This particular range is partitioned so that rectangles are arranged in increasing value of their area. That means, we can use std::equal_range to find the elements that have the area equal to a particular value. For instance, if we search for rectangles equivalent to 1×8 we will find the sub-range of 2×4, 4×2, and 8×1.

However, to do so, we must also specify, in this case, the fourth parameter, the binary comparison function, which must return true if the first value is less than the second.

auto[first, last] = std::equal_range(std::cbegin(rects), std::cend(rects), 
                                     rect{1,8}, 
                                     [](rect const & r1, rect const & r2) {
                                        return r1.area() < r2.area();
                                     });

for (auto it = first; it < last; ++it)
{
   std::cout << it->width() << ',' << it->height() << '\n';
}