C++ std::multimap and Equal Range

Today I have encountered a problem: Given that there are multiple equivalent keys in an instance of std::multimap, how could we list all of the corresponding values? For example:

#include <map>
#include <iostream>

int main() {
  std::multimap<int, int> xs;
  xs.insert(std::make_pair(1, 12));
  xs.insert(std::make_pair(2, 21));
  xs.insert(std::make_pair(3, 32));
  xs.insert(std::make_pair(3, 33));
  xs.insert(std::make_pair(2, 22));
  xs.insert(std::make_pair(2, 23));
  xs.insert(std::make_pair(1, 11));
  xs.insert(std::make_pair(3, 31));

  // How to list all of the values associated with key 2?
}

My first attempt is to look for the values with the find() function, and then keep iterating until the iterator is equal to the returned value of end().

// XXX: INCORRECT SOLUTION
for (std::multimap<int, int>::iterator it = xs.find(2), end = xs.end();
     it != end; ++it) {
  std::cout << it->first << " : " << it->second << std::endl;
}

However, the output should shows:

2 : 21
2 : 22
2 : 23
3 : 32
3 : 33
3 : 31

This is incorrect at all!

After checking the documentation for std::multimap, I found that the find() member function only guarantees the returned iterator will point to one matching key-value pair (any will do.) In the other words, the standard doesn't even guarantee the code above would list all of the associated values.

Equal Range

The correct solution is to use the equal_range() member function to get a pair of iterators indicating the range of the associated values:

#include <iostream>
#include <map>
#include <utility>

int main() {
  std::multimap<int, int> xs;
  xs.insert(std::make_pair(1, 12));
  xs.insert(std::make_pair(2, 21));
  xs.insert(std::make_pair(3, 32));
  xs.insert(std::make_pair(3, 33));
  xs.insert(std::make_pair(2, 22));
  xs.insert(std::make_pair(2, 23));
  xs.insert(std::make_pair(1, 11));
  xs.insert(std::make_pair(3, 31));

  // List all of the values associated with key 2.
  std::pair<std::multimap<int, int>::iterator,
            std::multimap<int, int>::iterator> r = xs.equal_range(2);
  for (std::multimap<int, int>::iterator it = r.first;
       it != r.second; ++it) {
    std::cout << it->first << " : " << it->second << std::endl;
  }
}

The equal_range() member function is also available in the other associative containers (e.g. std::set, std::map, std::multiset, and std::multimap) and the unordered associative containers (e.g. std::unordered_set, std::unordered_map, std::unordered_multiset and std::unordered_multimap).

Lower Bound and Upper Bound

For the associative containers, I found that we can go even further. We can look for the keys between a and b with lower_bound(a) and upper_bound(b).

  • The lower_bound() function will return the iterator to the first element with the key which is NOT less than the given key.
  • The upper_bound() function will return the iterator to the first element with the key which is greater than the given key.

For example, we can list all of the values associated with the keys between 2 and 5 with:

// List all of the values associated with key betwen 2 and 5.
std::multimap<int, int>::iterator it = xs.lower_bound(2);
std::multimap<int, int>::iterator end = xs.upper_bound(5);
for (; it != end; ++it) {
  std::cout << it->first << " : " << it->second << std::endl;
}

Conclusion

To wrap up this post, I would like to recall that there are three member functions mentioned in this post: equal_range(), lower_bound(), and upper_bound(). With these functions, we can efficiently find the key in the associative containers and iterate the corresponding values. Hope you enjoy this article and thanks for your reading.