C++ <algorithm> - equal_range() Function

The C++ algorithm::equal_range function returns the bounds of the subrange that includes all the elements of the range [first,last) which is equivalent to the specified value. The elements are compared using operator< (in first version) or comp (in second version). The elements in the range should be already sorted using the same criterion (operator< or comp), or at least partitioned with respect to specified value.

Syntax

//default version
template <class ForwardIterator, class T>
  pair<ForwardIterator,ForwardIterator>
    equal_range (ForwardIterator first, 
                 ForwardIterator last, 
                 const T& val);

//custom version
template <class ForwardIterator, class T, class Compare>
  pair<ForwardIterator,ForwardIterator>
    equal_range (ForwardIterator first, 
                 ForwardIterator last, 
                 const T& val,
                 Compare comp);

Parameters

`first`	Specify initial position of the forward iterator of a sorted (or properly partitioned) sequence. The range used is [first,last).
`last`	Specify final position of the forward iterator of a sorted (or properly partitioned) sequence. The range used is [first,last).
`val`	Specify the value of the srange to be searched for in the range.
`comp`	Specify a binary function that accepts two element as argument (one element from the range as first, and val as second), and returns a value convertible to bool. The returned value indicates whether the first argument is considered to go before the second.

Return Value

Returns a pair object with pair::first as an iterator pointing to the lower bound of the subrange, and pair::second as an iterator pointing to the upper bound of the subrange.

Time Complexity

On Average, up to twice of Logarithmic i.e, Θ(2*log(n)).

Example:

In the example below, the algorithm::equal_range function is used to find out the bounds of the subrange for specified value in the given range.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main (){
  vector<int> vec= {10, 20, 20, 20, 30, 40, 60};
  pair<vector<int>::iterator, vector<int>::iterator> srange;

  //finding bound of 20 in vec
  srange = equal_range(vec.begin(), vec.end(), 20);

  cout<<"Bounds for 20 in vec are at positions ";
  cout<<(srange.first - vec.begin())<<" and ";
  cout<<(srange.second - vec.begin())<<".\n";

  return 0;
}

The output of the above code will be:

Bounds for 20 in vec are at positions 1 and 4.

Example:

The example below shows how to use comp with algorithm::equal_range function.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool less_than (int i, int j) {
  return (i<j);
}

int main (){
  vector<int> vec= {10, 20, 20, 25, 25, 40, 60};
  pair<vector<int>::iterator, vector<int>::iterator> srange;

  //finding bound of 25 in vec
  srange = equal_range(vec.begin(), vec.end(), 25, less_than);

  cout<<"Bounds for 25 in vec are at positions ";
  cout<<(srange.first - vec.begin())<<" and ";
  cout<<(srange.second - vec.begin())<<".\n";

  return 0;
}

The output of the above code will be:

Bounds for 25 in vec are at positions 3 and 5.

❮ C++ <algorithm> Library