10.5. The multimap and multiset Types

Both map and set can contain only a single instance of each key. The types multiset and a multimap allow multiple instances of a key. In a phone directory, for example, someone might wish to provide a separate listing for each phone number associated with an individual. A listing of available texts by an author might provide a separate listing for each title. The multimap and multiset types are defined in the same headers as the corresponding single-element versions: the map and set headers, respectively.

The operations supported by multimap and multiset are the same as those on map and set, respectively, with one exception: multimap does not support subscripting. We cannot subscript a multimap because there may be more than one value associated with a given key. The operations that are common to both map and multimap or set and multiset change in various ways to reflect the fact that there can be multiple keys. When using either a multimap or multiset, we must be prepared to handle multiple values, not just a single value.

10.5.1. Adding and Removing Elements

The insert operations described in Table 10.5 (p. 365) and the erase operations described in Table 10.7 (p. 369) are used to add and remove elements of a multimap or multiset.

Because keys need not be unique, insert always adds an element. As an example, we might define a multimap to map authors to titles of the books they have written. The map might hold multiple entries for each author:

     // adds first element with key Barth
     authors.insert(make_pair(
       string("Barth, John"),
       string("Sot-Weed Factor")));

     // ok: adds second element with key Barth
     authors.insert(make_pair(
       string("Barth, John"),
       string("Lost in the Funhouse")));

The version of erase that takes a key removes all elements with that key. It returns a count of how many elements were removed. The versions that take an iterator or an iterator pair remove only the indicated element(s). These versions return void:

     multimap<string, string> authors;
     string search_item("Kazuo Ishiguro");

     // erase all elements with this key; returns number of elements removed
     multimap<string, string>::size_type cnt =
                               authors.erase(search_item);

10.5.2. Finding Elements in a multimap or multiset

We noted that maps and sets store their elements in order. The multimap and multiset types do so as well. As a result, when a multimap or multiset has multiple instances of a given key, those instances will be adjacent elements within the container.

Finding an element in a map or a set is a simple matterthe element is or is not in the container. For multimap and multiset the process is more complicated: the element may be present many times. For example, given our map from author to titles, we might want to find and print all the books by a particular author.

It turns out that there are three strategies we might use to find and print all the books by a given author. Each of these strategies relies on the fact that we know that all the entries for a given author will be adjacent within the multimap.

We'll start by presenting a strategy that uses only functions we've already seen. This version turns out to require the most code, so we will continue by exploring more compact alternatives.

Using find and count

We could solve our problem using find and count. The count function tells us how many times a given key occurs, and the find operation returns an iterator that refers to the first instance of the key we're looking for:

     // author we'll look for
     string search_item("Alain de Botton");

     // how many entries are there for this author
     typedef multimap<string, string>::size_type sz_type;
     sz_type entries = authors.count(search_item);

     // get iterator to the first entry for this author
     multimap<string,string>::iterator iter =
                              authors.find(search_item);

     // loop through the number of entries there are for this author
     for (sz_type cnt = 0; cnt != entries; ++cnt, ++iter) cout <<
            iter->second << endl; // print each title

We start by determining how many entries there are for the author by calling count and getting an iterator to the first element with this key by calling find. The number of iterations of the for loop depends on the number returned from count. In particular, if the count was zero, then the loop is never executed.

A Different, Iterator-Oriented Solution

Another, more elegant strategy uses two associative container operations that we haven't seen yet: lower_bound and upper_bound. These operations, listed in Table 10.8 (p. 379), apply to all associative containers. They can be used with (plain) maps or sets but are most often used with multimaps or multisets. Each of these operations takes a key and returns an iterator.

Calling lower_bound and upper_bound on the same key yields an iterator range (Section 9.2.1, p. 314) that denotes all the elements with that key. If the key is in the container, the iterators will differ: the one returned from lower_bound will refer to the first instance of the key, whereas upper_bound will return an iterator referring just after the last instance. If the element is not in the multimap, then lower_bound and upper_bound will return equal iterators; both will refer to the point at which the key could be inserted without disrupting the order.

Of course, the iterator returned from these operations might be the off-the-end iterator for the container itself. If the element we look for has the largest key in the multimap, then upper_bound on that key returns the off-the-end iterator. If the key is not present and is larger than any key in the multimap, then the return from lower_bound will also be the off-the-end iterator.

Using these operations, we could rewrite our program as follows:

     // definitions of authors and search_item as above

     // beg and end denote range of elements for this author
     typedef multimap<string, string>::iterator authors_it;
     authors_it beg = authors.lower_bound(search_item),
                end = authors.upper_bound(search_item);

     // loop through the number of entries there are for this author
     while (beg != end) {
         cout << beg->second << endl; // print each title
         ++beg;
     }

This program does the same work as the previous one that used count and find but accomplishes its task more directly. The call to lower_bound positions beg so that it refers to the first element matching search_item if there is one. If there is no such element, then beg refers to first element with a key larger than search_item. The call to upper_bound sets end to refer to the element with the key just beyond the last element with the given key.

If there is no element for this key, then lower_bound and upper_bound will be equal: They will both refer to the same element or they will both point one past the end of the multimap. They both will refer to the point at which this key could be inserted while maintaining the container order.

If there are elements with this key, then beg will refer to the first such element. We can increment beg to traverse the elements with this key. The iterator in end will signal when we've seen all the elements. When beg equals end, we have seen every element with this key.

Given that these iterators form a range, we can use the same kind of while loop that we've used to traverse other ranges. The loop is executed zero or more times and prints the entries, if any, for the given author. If there are no elements, then beg and end are equal and the loop is never executed. Otherwise, we know that the increment to beg will eventually reach end and that in the process we will print each record associated with this author.

Table 10.8. Associative Container Operations Returning Iterators

m.lower_bound(k)	Returns an iterator to the first element with key not less than k.
m.upper_bound(k)	Returns an iterator to the first element with key greater than k.
m.equal_range(k)	Returns a pair of iterators. The first member is equivalent to m.lower_bound(k) and second is equivalent to m.upper_bound(k).

The equal_range Function

It turns out that there is an even more direct way to solve this problem: Instead of calling upper_bound and lower_bound, we can call equal_range. This function returns a pair of iterators. If the value is present, then the first iterator refers to the first instance of the key and the second iterator refers one past the last instance of the key. If no matching element is found, then both the first and second iterator refer to the position where this key could be inserted.

We could use equal_range to modify our program once again:

     // definitions of authors and search_item as above

     // pos holds iterators that denote range of elements for this key
     pair<authors_it, authors_it>
                      pos = authors.equal_range(search_item);

     // loop through the number of entries there are for this author
     while (pos.first != pos.second) {
         cout << pos.first->second << endl; // print each title
         ++pos.first;
     }

This program is essentially identical to the previous one that used upper_bound and lower_bound. Instead of using local variables, beg and end, to hold the iterator range, we use the pair returned by equal_range. The first member of that pair holds the same iterator as the one lower_bound would have returned. The iterator that upper_bound would have returned is in the second member.

Thus, in this program pos.first is equivalent to beg, and pos.second is equivalent to end.