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.