The equal_range function in C++ serves as a variant of binary search. Its purpose is to provide both the lower and upper bounds of the subrange containing all elements equal to val within the range [first, last).

Where sub range is defined by two iterators, one pointing to the first element that is not less than val and another pointing to the first element greater than val.

• ✅ The first version uses operator < to compare the elements and the second version uses the given comparison function i.e. comp.
• ✅ The range [first, last) must be partitioned with respect to comparison with val, i.e. it must satisfy all of the following conditions: partitioned with respect to element < val or comp(element, val) partitioned with respect to !(val < element) or !comp(val, element) for all elements, if element < val or comp(element, val) is true then !(val < element) or !comp(val, element) is also true.
• ✅ partitioned with respect to element < val or comp(element, val)
• ✅ partitioned with respect to !(val < element) or !comp(val, element)
• ✅ for all elements, if element < val or comp(element, val) is true then !(val < element) or !comp(val, element) is also true.

Syntax

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

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

Parameter

A forward iterator that points to the initial element within the specified range intended for searching.

last: A forward iterator indicating the element that comes after the last element in the range intended for searching.

The ```

include <iostream>

include <vector>

include <algorithm>

using namespace std;

int main

{

int a = {2, 3, 5, 6, 7, 7, 7, 8, 9, 10};

vector<int> v(a, a+10);

cout <<"\nHere are the contents of v:\n";

for (vector<int>::size_type i=0; i<v.size; i++)

cout <<v.at(i)<<" ";

pair<vector<int>::iterator, vector<int>::iterator> bounds;

bounds = equal_range(v.begin, v.end, 3);

if (bounds.first != v.end)

cout <<"\nLower bound of 3 in v = "<<*bounds.first;

if (bounds.first != v.end)

cout <<"\nUpper bound of 3 in v = "<<*bounds.second;

bounds = equal_range(v.begin, v.end, 4);

if (bounds.first != v.end)

cout <<"\nLower bound of 4 in v = "<<*bounds.first;

if (bounds.first != v.end)

cout <<"\nUpper bound of 4 in v = "<<*bounds.second;

bounds = equal_range(v.begin, v.end, 5);

if (bounds.first != v.end)

cout <<"\nLower bound of 5 in v = "<<*bounds.first;

if (bounds.first != v.end)

cout <<"\nUpper bound of 5 in v = "<<*bounds.second;

bounds = equal_range(v.begin, v.end, 7);

if (bounds.first != v.end)

cout <<"\nLower bound of 7 in v = "<<*bounds.first;

cout <<"\nThis is the first of the three 7's, since the value "

"before this 7 is "<<*(bounds.first-1)<<".";

if (bounds.first != v.end)

cout <<"\nUpper bound of 7 in v = "<<*bounds.second;

bounds = equal_range(v.begin, v.end, 0);

if (bounds.first != v.end)

cout <<"\nLower bound of 0 in v = "<<*bounds.first;

if (bounds.first != v.end)

cout <<"\nUpper bound of 0 in v = "<<*bounds.second;

bounds = equal_range(v.begin, v.end, 15);

if (bounds.first != v.end)

cout <<"\nLower bound of 15 in v = "<<*bounds.first;

if (bounds.first != v.end)

cout <<"\nUpper bound of 15 in v = "<<*bounds.second;

cout <<"\nNote that both the lower and upper bound locations "

"\nof 15 are the end (one-past-the-last) vector position.";

return 0;

}

val : An upper limit value used to compare the elements within the specified range.

## Return value

It provides a pair of iterators, where one indicates the initial element equal to or greater than val, and the other indicates the initial element greater than val.

If no such element is found then it returns last.

## Complexity

On average, the computational complexity increases logarithmically as the distance between the first and last elements grows: it can conduct a maximum of 2 times the logarithm base 2 of N, plus 1, element comparisons. Here, N represents the difference between the last and first elements.

## Data races

The elements within the range [first, last) are retrieved.

## Exceptions

This function will raise an exception if an exception is thrown during either an element comparison or an iterator operation.

Please be aware that using incorrect parameters can result in unpredictable behavior.

## Example 1

Let's explore a straightforward example to illustrate the implementation of equal_range():

include <iostream>

include <vector>

include <algorithm>

using namespace std;

int main

{

vector<int> v = {3, 1, 4, 2, 5};

sort(v.begin, v.end);

auto result = equal_range(v.begin, v.end, 3);

cout << "Lower Bound of 3 is: "<<*result.first << endl;

cout << "Upper Bound of 3 is: "<<*result.second << endl;

return 0;

}

Output:

Lower Bound of 3 is: 3

Upper Bound of 3 is: 4

## Example 2

Let's explore another straightforward example to contrast the elements by utilizing the operator<:

include <algorithm>

include <vector>

include <iostream>

using namespace std;

struct S

{

int number;

char name;

S ( int number, char name )

: number ( number ), name ( name )

{}

// only the number is relevant with this comparison

bool operator< ( const S& s ) const

{

return number < s.number;

}

};

int main

{

// note: not ordered, only partitioned w.r.t. S defined below

vector<S> vec = { {1,'A'}, {2,'B'}, {2,'C'}, {2,'D'}, {4,'G'}, {3,'F'} };

S value ( 2, '?' );

auto p = equal_range(vec.begin,vec.end,value);

for ( auto i = p.first; i != p.second; ++i )

cout << i->name << ' ';

return 0;

}

Output:

In the example provided, the < operator is utilized to compare elements and retrieve all elements within the specified range that are equal to 2.

## Example 3

Let's examine another straightforward example to contrast the elements utilizing a comparison function:

include <algorithm>

include <vector>

include <iostream>

using namespace std;

struct S

{

int number;

char name;

S ( int number, char name )

: number ( number ), name ( name )

{}

// only the number is relevant with this comparison

bool operator< ( const S& s ) const

{

return number < s.number;

}

};

struct Comp

{

bool operator ( const S& s, int i )

{

return s.number < i;

}

bool operator ( int i, const S& s )

{

return i < s.number;

}

};

int main

{

// note: not ordered, only partitioned w.r.t. S defined below

vector<S> vec = { {1,'A'}, {2,'B'}, {2,'C'}, {2,'D'}, {4,'G'}, {3,'F'} };

auto p = equal_range(vec.begin,vec.end,2,Comp);

for ( auto i = p.first; i != p.second; ++i )

cout << i->name << ' ';

return 0;

}

Output:

## Example 4

Let's see another simple example:

include <iostream>

include <vector>

include <algorithm>

using namespace std;

int main

{

int a = {2, 3, 5, 6, 7, 7, 7, 8, 9, 10};

vector<int> v(a, a+10);

cout <<"\nHere are the contents of v:\n";

for (vector<int>::size_type i=0; i<v.size; i++)

cout <<v.at(i)<<" ";

pair<vector<int>::iterator, vector<int>::iterator> bounds;

bounds = equal_range(v.begin, v.end, 3);

if (bounds.first != v.end)

cout <<"\nLower bound of 3 in v = "<<*bounds.first;

if (bounds.first != v.end)

cout <<"\nUpper bound of 3 in v = "<<*bounds.second;

bounds = equal_range(v.begin, v.end, 4);

if (bounds.first != v.end)

cout <<"\nLower bound of 4 in v = "<<*bounds.first;

if (bounds.first != v.end)

cout <<"\nUpper bound of 4 in v = "<<*bounds.second;

bounds = equal_range(v.begin, v.end, 5);

if (bounds.first != v.end)

cout <<"\nLower bound of 5 in v = "<<*bounds.first;

if (bounds.first != v.end)

cout <<"\nUpper bound of 5 in v = "<<*bounds.second;

bounds = equal_range(v.begin, v.end, 7);

if (bounds.first != v.end)

cout <<"\nLower bound of 7 in v = "<<*bounds.first;

cout <<"\nThis is the first of the three 7's, since the value "

"before this 7 is "<<*(bounds.first-1)<<".";

if (bounds.first != v.end)

cout <<"\nUpper bound of 7 in v = "<<*bounds.second;

bounds = equal_range(v.begin, v.end, 0);

if (bounds.first != v.end)

cout <<"\nLower bound of 0 in v = "<<*bounds.first;

if (bounds.first != v.end)

cout <<"\nUpper bound of 0 in v = "<<*bounds.second;

bounds = equal_range(v.begin, v.end, 15);

if (bounds.first != v.end)

cout <<"\nLower bound of 15 in v = "<<*bounds.first;

if (bounds.first != v.end)

cout <<"\nUpper bound of 15 in v = "<<*bounds.second;

cout <<"\nNote that both the lower and upper bound locations "

"\nof 15 are the end (one-past-the-last) vector position.";

return 0;

}

Output:

Here are the contents of v:

2 3 5 6 7 7 7 8 9 10

Lower bound of 3 in v = 3

Upper bound of 3 in v = 5

Lower bound of 4 in v = 5

Upper bound of 4 in v = 5

Lower bound of 5 in v = 5

Upper bound of 5 in v = 6

Lower bound of 7 in v = 7

This is the first of the three 7's, since the value before this 7 is 6.

Upper bound of 7 in v = 8

Lower bound of 0 in v = 2

Upper bound of 0 in v = 2

Note that both the lower and upper bound locations

of 15 are the end (one-past-the-last) vector position.