equal_range() in Set C++ STL


Reading time: 20 minutes | Coding time: 5 minutes

equal_range() is a built in function for Set container in C++ STL which is used to determine the range of a number or key value passed as a parameter. If the value is present in the set then the function return a pair of iterator where first includes lower bound of the range and the second includes the upper bound. Since in set there are unique elements only which result into the value of lower bound as the original position(counting starting from 1) and the next postion is the upper bound. If the value is not present then the lower bound and upper bound have same value.

Syntax :

set_name.equal_range(key_value) 
  • Parameters: The key value is passed whose range is to be determined.
  • Return value: A pair of iterator

Some background on set:

Set is a data structure that stores elements. It is a simple yet effective data structure when used correctly. In C++'s Standard Template library (STL), we have set as a container that is used to store the values which are unique i.e no value in a set can be repeated or edited. If you want to edit the value added by you the only way is to remove the wrong element and add the correct one.

A set can defined as:

set<int> s; 
s.insert(0);

Example 1

Consider this C++ example which we have explained following it:

#include <bits/stdc++.h> 
using namespace std; 
int main() 
{
    set<int> s; 
  
    s.insert(0); 
    s.insert(2); 
    s.insert(4); 
    s.insert(6); 
    s.insert(8); 

    cout << "The set elements are: "; 
    for (auto it = s.begin(); it != s.end(); it++) 
        cout << *it << " "; 
  
    auto it = s.equal_range(2); 
    cout << "\nThe lower bound of 2 is " << *it.first; 
    cout << "\nThe upper bound of 2 is " << *it.second; 
  
    it = s.equal_range(10); 
    cout << "\nThe lower bound of 10 is " << *it.first; 
    cout << "\nThe upper bound of 10 is " << *it.second; 
  
    it = s.equal_range(0); 
    cout << "\nThe lower bound of 0 is " << *it.first; 
    cout << "\nThe upper bound of 0 is " << *it.second; 
  
    return 0; 
}

Output :

The set elements are: 0 2 4 6 8  
The lower bound of 2 is 2
The upper bound of 2 is 3
The lower bound of 10 is 5
The upper bound of 10 is 5
The lower bound of 0 is 1
The upper bound of 0 is 2

As explained above the function returns a pair of iterator where the lower bound is the original position of the key value and the upper bound is the original position + 1 i.e postition after the occurance of key value.

If the key value is not present then if have 2 cases :

  1. Key value less than the first value in set then upper bound = lower bound = 0.
  2. Key value greater than the last value in the set then upper bpund = lower bound = size of set.(for key value = 10)

Example 2

Consider this C++ example which we have explained following it:

#include <bits/stdc++.h> 
using namespace std; 
int main() 
{
    set<char> s; 
  
    s.insert(b); 
    s.insert(c); 
    s.insert(d); 
    s.insert(e); 
    s.insert(f); 

    cout << "The set elements are: "; 
    for (auto it = s.begin(); it != s.end(); it++) 
        cout << *it << " "; 
  
    auto it = s.equal_range(c); 
    cout << "\nThe lower bound of c is " << *it.first; 
    cout << "\nThe upper bound of c is " << *it.second; 
  
    it = s.equal_range(A); 
    cout << "\nThe lower bound of A is " << *it.first; 
    cout << "\nThe upper bound of A is " << *it.second; 
   
    it = s.equal_range(b); 
    cout << "\nThe lower bound of b is " << *it.first; 
    cout << "\nThe upper bound of b is " << *it.second; 
  
    return 0; 
}

Output :

The set elements are: b c d e f 
The lower bound of c is 2
The upper bound of c is 3
The lower bound of A is 1
The upper bound of A is 1
The lower bound of b is 1
The upper bound of b is 2

As explained above the function returns a pair of iterator where the lower bound is the original position of the key value and the upper bound is the original position + 1 i.e postition after the occurance of key value.

If the key value is not present then if have 2 cases :

  1. Key value less than the first value in set then upper bound = lower bound = 0(for key value = A).
  2. Key value greater than the last value in the set then upper bpund = lower bound = size of set.

Note: Comparing the ASCII values in case of char or string set.

With this, you have the complete knowledge of using equal_range() function for Set container in C++ Standard Template Library (STL).