C++ unordered_map - equal_range() Function

The C++ unordered_map::equal_range function returns the bounds of a range which includes all elements in the unordered_map container with keys that are equivalent to the specified value. It returns a pair, with pair::first member as the lower bound of the range, and pair::second member as the upper bound of the range.

As a unordered_map contains unique keys, therefore the range will contain a single element at most. If no match is found, it will return the range with end as both its lower and upper range bounds.

Syntax

C++11

pair<const_iterator,const_iterator> 
  equal_range (const key_type& k) const;

pair<iterator,iterator> 
  equal_range (const key_type& k);

Parameters

`k`	Specify key to compare.

Return Value

Returns a pair, with pair::first member as the lower bound of the range, and pair::second member as the upper bound of the range.

Time Complexity

Average case: Constant i.e, Θ(1).
Worst case: Linear in container sizei.e, Θ(n).

Example:

In the example below, the unordered_map::equal_range function returns the bounds of a range for specified key of uMap.

#include <iostream>
#include <unordered_map>
using namespace std;
 
int main (){
  unordered_map<int, string> uMap;
  unordered_map<int, string>::iterator it;
  uMap = {{101, "John"}, {102, "Marry"}, {103, "Kim"}, {104, "Jo"}};

  cout<<"uMap contains:\n";
  for(it = uMap.begin(); it != uMap.end(); ++it)
    cout<<it->first<<"  "<<it->second<<"\n";

  //finding bound range of key=102
  pair<unordered_map<int, string>::iterator,
       unordered_map<int, string>::iterator> pit;
  pit = uMap.equal_range(102);

  cout<<"\nLower bound - "<<pit.first->first<<":"<<pit.first->second<<"\n";
  cout<<"Upper bound - "<<pit.second->first<<":"<<pit.second->second<<"\n";

  return 0;
}

The output of the above code will be:

uMap contains:
104  Jo
103  Kim
102  Marry
101  John

Lower bound - 102:Marry
Upper bound - 101:John

Example:

Lets consider another example where equal_range() function is used to specify bound range to delete elements from the unordered_map.

#include <iostream>
#include <unordered_map>
using namespace std;
 
int main (){
  unordered_map<int, string> uMap;
  unordered_map<int, string>::iterator it;
  uMap = {{101, "John"}, {102, "Marry"}, {103, "Kim"}, {104, "Jo"}};

  cout<<"uMap contains:\n";
  for(it = uMap.begin(); it != uMap.end(); ++it)
    cout<<it->first<<"  "<<it->second<<"\n";

  //finding bound range of key=102
  pair<unordered_map<int, string>::iterator,
       unordered_map<int, string>::iterator> pit;
  pit = uMap.equal_range(102);

  //erasing the elements from the map
  uMap.erase(pit.first, pit.second);

  cout<<"\nuMap contains:\n";
  for(it = uMap.begin(); it != uMap.end(); ++it)
    cout<<it->first<<"  "<<it->second<<"\n";

  return 0;
}

The output of the above code will be:

uMap contains:
104  Jo
103  Kim
102  Marry
101  John

uMap contains:
104  Jo
103  Kim
101  John

❮ C++ <unordered_map> Library