10.5. The multimap and multiset Types

10.5. multimap 和 multiset 类型

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.

map 和 set 容器中，一个键只能对应一个实例。而 multiset 和 multimap 类型则允许一个键对应多个实例。例如，在电话簿中，每个人可能有单独的电话号码列表。在作者的文章集中，每位作者可能有单独的文章标题列表。multimap 和 multiset 类型与相应的单元素版本具有相同的头文件定义：分别是 map 和 set 头文件。

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.

multimap 和 multiset 所支持的操作分别与 map 和 set 的操作相同，只有一个例外：multimap 不支持下标运算。不能对 multimap 对象使用下标操作，因为在这类容器中，某个键可能对应多个值。为了顺应一个键可以对应多个值这一性质，map 和 multimap，或 set 和 multiset 中相同的操作都以不同的方式做出了一定的修改。在使用 multimap 或 multiset 时，对于某个键，必须做好处理多个值的准备，而非只有单一的值。

10.5.1. Adding and Removing Elements

10.5.1. 元素的添加和删除

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.

表 10.5 描述的 insert 操作和表 10.7 描述的 erase 操作同样适用于 multimap 以及 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:

由于键不要求是唯一的，因此每次调用 insert 总会添加一个元素。例如，可如下定义一个 multimap 容器对象将作者映射到他们所写的书的书名上。这样的映射可为一个作者存储多个条目：

     // 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:

带有一个键参数的 erase 版本将删除拥有该键的所有元素，并返回删除元素的个数。而带有一个或一对迭代器参数的版本只删除指定的元素，并返回 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

10.5.2. 在 multimap 和 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.

注意到，关联容器 map 和 set 的元素是按顺序存储的。而 multimap 和 multset 也一样。因此，在 multimap 和 multiset 容器中，如果某个键对应多个实例，则这些实例在容器中将相邻存放。

We are guaranteed that iterating across a multimap or multiset returns all the elements with a given key in sequence. 迭代遍历 multimap 或 multiset 容器时，可保证依次返回特定键所关联的所有元素。

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.

在 map 或 set 容器中查找一个元素很简单——该元素要么在要么不在容器中。但对于 multimap 或 multiset，该过程就复杂多了：某键对应的元素可能出现多次。例如，假设有作者与书名的映射，我们可能希望找到并输出某个作者写的所有书的书名。

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.

事实证明，上述问题可用三种策略解决。而且三种策略都基于一个事实——在 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

使用 find 和 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:

使用 find 和 count 可有效地解决刚才的问题。count 函数求出某键出现的次数，而 find 操作则返回一个迭代器，指向第一个拥有正在查找的键的实例：

     // 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.

首先，调用 count 确定某作者所写的书籍数目，然后调用 find 获得指向第一个该键所关联的元素的迭代器。for 循环迭代的次数依赖于 count 返回的值。在特殊情况下，如果 count 返回 0 值，则该循环永不执行。

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.

另一个更优雅简洁的方法是使用两个未曾见过的关联容器的操作：lower_bound 和 upper_bound。表 10.8 列出的这些操作适用于所有的关联容器，也可用于普通的 map 和 set 容器，但更常用于 multimap 和 multiset。所有这些操作都需要传递一个键，并返回一个迭代器。

Table 10.8. Associative Container Operations Returning Iterators

表 10.8. 返回迭代器的关联容器操作

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.

在同一个键上调用 lower_bound 和 upper_bound，将产生一个迭代器范围（第 9.2.1 节），指示出该键所关联的所有元素。如果该键在容器中存在，则会获得两个不同的迭代器：lower_bound 返回的迭代器指向该键关联的第一个实例，而 upper_bound 返回的迭代器则指向最后一个实例的下一位置。如果该键不在 multimap 中，这两个操作将返回同一个迭代器，指向依据元素的排列顺序该键应该插入的位置。

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.

当然，这些操作返回的也可能是容器自身的超出末端迭代器。如果所查找的元素拥有 multimap 容器中最大的键，那么的该键上调用 upper_bound 将返回超出末端迭代器。如果所查找的键不存在，而且比 multimap 容器中所有的键都大，则 low_bound 也将返回超出末端迭代器。

The iterator returned from lower_bound may or may not refer to an element with the given key. If the key is not in the container, then lower_bound refers to the first point at which this key could be inserted while preserving the element order within the container. lower_bound 返回的迭代器不一定指向拥有特定键的元素。如果该键不在容器中，则 lower_bound 返回在保持容器元素顺序的前提下该键应被插入的第一个位置。

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.

这个程序实现的功能与前面使用 count 和 find 的程序相同，但任务的实现更直接。调用 lower_bound 定位 beg 迭代器，如果键 search_item 在容器中存在，则使 beg 指向第一个与之匹配的元素。如果容器中没有这样的元素，那么 beg 将指向第一个键比 search_item 大的元素。调用 upper_bound 设置 end 迭代器，使之指向拥有该键的最后一个元素的下一位置。

These operations say nothing about whether the key is present. The important point is that the return values act like an iterator range. 这两个操作不会说明键是否存在，其关键之处在于返回值给出了迭代器范围。

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.

若该键没有关联的元素，则 lower_bound 和 upper_bound 返回相同的迭代器：都指向同一个元素或同时指向 multimap 的超出末端位置。它们都指向在保持容器元素顺序的前提下该键应被插入的位置。

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.

如果该键所关联的元素存在，那么 beg 将指向满足条件的元素中的第一个。可对 beg 做自增运算遍历拥有该键的所有元素。当迭代器累加至 end 标志时，表示已遍历了所有这些元素。当 beg 等于 end 时，表示已访问所有与该键关联的元素。

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.

假设这些迭代器标记某个范围，可使用同样的 while 循环遍历该范围。该循环执行 0 次或多次，输出指定作者所写的所有书的书名（如果有的话）。如果没有相关的元素，那么 beg 和 end 相等，循环永不执行。否则，不断累加 beg 将最终到达 end，在这个过程中可输出该作者所关联的记录。

The equal_range Function

enual_range 函数

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.

事实上，解决上述问题更直接的方法是：调用 equal_range 函数来取代调用 upper_bound 和 lower_bound 函数。equal_range 函数返回存储一对迭代器的 pair 对象。如果该值存在，则 pair 对象中的第一个迭代器指向该键关联的第一个实例，第二个迭代器指向该键关联的最后一个实例的下一位置。如果找不到匹配的元素，则 pair 对象中的两个迭代器都将指向此键应该插入的位置。

We could use equal_range to modify our program once again:

使用 equal_range 函数再次修改程序：

     // 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.

这个程序段与前面使用 upper_bound 和 lower_bound 的程序基本上是相同的。本程序不用局部变量 beg 和 end 来记录迭代器范围，而是直接使用 equal_range 返回的 pair 对象。该 pair 对象的 first 成员存储 lower_bound 函数返回的迭代器，而 second 成员则记录 upper_bound 函数返回的迭代器。

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

因此，本程序的 pos.first 等价于前一方法中的 beg，而 pos.second 等价于 end。

Exercises Section 10.5.2 Exercise 10.26: Write a program that populates a multimap of authors and their works. Use find to find an element in the multimap and erase that element. Be sure your program works correctly if the element you look for is not in the map. 编写程序建立作者及其作品的 multimap 容器。使用 find 函数在 multimap 中查找元素，并调用 erase 将其删除。当所寻找的元素不存在时，确保你的程序依然能正确执行。 Exercise 10.27: Repeat the program from the previous exercise, but this time use equal_range to get iterators so that you can erase a range of elements. 重复上一题所编写的程序，但这一次要求使用 equal_range 函数获取迭代器，然后删除一段范围内的元素。 Exercise 10.28: Using the multimap from the previous exercise, write a program to generate the list of authors whose name begins with the each letter in the alphabet. Your output should look something like: 沿用上题中的 multimap 容器，编写程序以下面的格式按姓名首字母的顺序输出作者名字： Author Names Beginning with 'A': Author, book, book, ... ... Author Names Beginning with 'B': ... Exercise 10.29: Explain the meaning of the operand pos.first->second used in the output expression of the final program in this section. 解释本节最后一个程序的输出表达式使用操作数 pos.first->second 的含义。