C++ Standard Library C++ STL Library

C++ multimap - equal_range() Function



The C++ multimap::equal_range function returns the bounds of a range which includes all elements in the multimap 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).

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 multimap::equal_range function returns the bounds of a range for specified key of MMap.

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

  //populating multimap
  MMap.insert(pair<string, string>("CAN", "Montreal"));
  MMap.insert(pair<string, string>("IND", "Mumbai"));
  MMap.insert(pair<string, string>("IND", "Delhi"));
  MMap.insert(pair<string, string>("USA", "New York"));
  MMap.insert(pair<string, string>("USA", "Washington"));  

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

  //finding bound range of key='IND'
  pair<multimap<string, string>::iterator,
       multimap<string, string>::iterator> pit;
  pit = MMap.equal_range("IND");

  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:

MMap contains:
CAN  Montreal
IND  Mumbai
IND  Delhi
USA  New York
USA  Washington

Lower bound - IND:Mumbai
Upper bound - USA:New York

Example:

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

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

  //populating multimap
  MMap.insert(pair<string, string>("CAN", "Montreal"));
  MMap.insert(pair<string, string>("IND", "Mumbai"));
  MMap.insert(pair<string, string>("IND", "Delhi"));
  MMap.insert(pair<string, string>("USA", "New York"));
  MMap.insert(pair<string, string>("USA", "Washington"));  

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

  //finding bound range of key='IND'
  pair<multimap<string, string>::iterator,
       multimap<string, string>::iterator> pit;
  pit = MMap.equal_range("IND");

  //erasing the elements from the multimap
  MMap.erase(pit.first, pit.second);

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

  return 0;
}

The output of the above code will be:

MMap contains:
CAN  Montreal
IND  Mumbai
IND  Delhi
USA  New York
USA  Washington

MMap contains:
CAN  Montreal
USA  New York
USA  Washington

❮ C++ <map> Library

5