Skip to content
Tutorials Center
My learning

Topics

C++ Reference ยท Algorithms

The std::equal_range algorithm

Reference for C++ std::equal_range: get the sub-range of equal elements in a sorted range with one call, count duplicates and use it on maps and sets.

std::equal_range takes a sorted range and a value, and returns a pair of iterators that bracket all elements equivalent to that value. The first iterator is what std::lower_bound would return; the second is what std::upper_bound would return. If the value is absent, both iterators are equal and point to the position where it would be inserted.

It is the natural tool for "give me all entries with this key" in a sorted vector, and it works the same way as the member equal_range of std::map, std::multimap, std::set and std::multiset.

C++
auto [first, last] = std::equal_range(v.begin(), v.end(), 20);
std::cout << (last - first) << " copies of 20";

Try it

C++ Counting and visiting duplicates

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

C++ Equal by a key: records sorted by group

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Syntax

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

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

// C++20
std::ranges::equal_range(R&& r, const T& value, Comp comp = {}, Proj proj = {});   // returns a subrange
Name Description
first, last The half-open range, which must be sorted (or at least partitioned with respect to value).
value The value (or key) to look for.
comp A strict weak ordering used for sorting the range. It must accept both (element, value) and (value, element).

Returns: std::pair of iterators [lower_bound, upper_bound). The ranges version returns a std::ranges::subrange.

Errors / undefined behavior: the range must be ordered consistently with the comparison; otherwise the result is not meaningful.

Usage notes

  • Equivalent, not equal: elements are matched by "neither is less than the other", so a custom comparator on one field finds every element with that field value.
  • Structured bindings make the result readable: auto [lo, hi] = std::equal_range(...).
  • Complexity: at most about 2 log2(n) + 1 comparisons for random-access ranges, the cost of one lower_bound plus one upper_bound.
  • Cheaper than looping: to count duplicates of a value in a sorted vector, std::distance over an equal_range is O(log n), while std::count is O(n).
  • Containers: call m.equal_range(key) on a std::multimap or std::set instead of the free function; the free function on a std::set is slow because its iterators are not random access.
  • Mixed-type searches need a comparator with both argument orders, as in the second example, or a transparent comparator.
  • Empty result: check first == last before using the iterators as elements.