C++ Standard Library C++ STL Library

C++ map - equal_range() Function



The C++ map::equal_range function returns the bounds of a range which includes all elements in the 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. This contains all elements with key in the range [pair::first, pair::second).

As a 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 zero length and both iterators will point to the first element with key that is considered to go after the specified value.

Syntax

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

Logarithmic i.e, Θ(log(n))

Example:

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

#include <iostream>
#include <map>
using namespace std;
 
int main (){
  map<int, string> MyMap;
  map<int, string>::iterator it;

  //populating map
  MyMap[101] = "John";
  MyMap[102] = "Marry";
  MyMap[103] = "Kim";
  MyMap[104] = "Jo";
  MyMap[105] = "Ramesh";

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

  //finding bound range of key=102
  pair<map<int, string>::iterator,
       map<int, string>::iterator> pit;
  pit = MyMap.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:

MyMap contains:
101  John
102  Marry
103  Kim
104  Jo
105  Ramesh

Lower bound - 102:Marry
Upper bound - 103:Kim

Example:

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

#include <iostream>
#include <map>
using namespace std;
 
int main (){
  map<int, string> MyMap;
  map<int, string>::iterator it;

  //populating map
  MyMap[101] = "John";
  MyMap[102] = "Marry";
  MyMap[103] = "Kim";
  MyMap[104] = "Jo";
  MyMap[105] = "Ramesh";

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

  //finding bound range of key=102
  pair<map<int, string>::iterator,
       map<int, string>::iterator> pit;
  pit = MyMap.equal_range(102);
  
  //erasing the elements from the map
  MyMap.erase(pit.first, pit.second);

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

  return 0;
}

The output of the above code will be:

MyMap contains:
101  John
102  Marry
103  Kim
104  Jo
105  Ramesh

MyMap contains:
101  John
103  Kim
104  Jo
105  Ramesh

❮ C++ <map> Library