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.
auto [first, last] = std::equal_range(v.begin(), v.end(), 20); std::cout << (last - first) << " copies of 20";
Try it
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.
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
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_boundplus oneupper_bound. - Cheaper than looping: to count duplicates of a value in a sorted vector,
std::distanceover anequal_rangeis O(log n), whilestd::countis O(n). - Containers: call
m.equal_range(key)on astd::multimaporstd::setinstead of the free function; the free function on astd::setis 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 == lastbefore using the iterators as elements.