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.
