C++拾遗（七）——关联容器

　　关联容器（Associative containers）支持通过键来高效地查找和读取元素。两个基本的关联容器类型是 map 和set。map 的元素以键－值（key-value）对的形式组织：键用作元素在 map 中的索引，而值则表示所存储和读取的数据。set仅包含一个键，并有效地支持关于某个键是否存在的查询。set 和 map 类型的对象所包含的元素都具有不同的键，不允许为同一个键添加第二个元素。如果一个键必须对应多个实例，则需使用 multimap 或 multiset，这两种类型允许多个元素拥有相同的键。

map	关联数组：元素通过键来存储和读取
set	大小可变的集合，支持通过键实现的快速读取
multimap	支持同一个键多次出现的 map 类型
multiset	支持同一个键多次出现的 set 类型

pair 类型

pair 包含两个数据值。与容器一样，pair 也是一种模板类型。但又与之前介绍的容器不同，在创建 pair 对象时，必须提供两个类型名：pair 对象所包含的两个数据成员各自对应的类型名字，这两个类型不必相同。
与其他标准库类型不同，对于 pair 类，可以直接访问其数据成员：其成员都是仅有的，分别命名为 first 和 second。只需使用普通的点操作符——成员访问标志即可访问其成员：
```
1 string firstBook;
2 // access and test the data members of the pair
3 if (author.first == "James" && author.second == "Joyce")
4     firstBook = "Stephen Hero";
```

除了构造函数，标准库还定义了一个 make_pair 函数，由传递给它的两个实参生成一个新的 pair 对象。

map 类型

map 是键－值对的集合。map 类型通常可理解为关联数组（associative array）：可使用键作为下标来获取一个值，正如内置数组类型一样。而关联的本质在于元素的值与某个特定的键相关联，而并非通过元素在数组中的位置来获取。
在使用关联容器时，它的键不但有一个类型，而且还有一个相关的比较函数。默认情况下，标准库使用键类型定义的 < 操作符来实现键（key type）的比较。所用的比较函数必须在键类型上定义严格弱排序（strict weak ordering）。所谓的严格弱排序可理解为键类型数据上的“小于”关系。用做 map 对象的键时，可使用任意一个键值来访问相应的元素。
map 对象的元素是键－值对，也即每个元素包含两个部分：键以及由键关联的值。map 的 value_type 就反映了这个事实。该类型比前面介绍的容器所使用的元素类型要复杂得多：value_type 是存储元素的键以及值的 pair 类型，而且键为 const。在学习 map 的接口时，需谨记 value_type 是 pair 类型，它的值成员可以修改，但键成员不能修改。

map<K,V>::key_type	在 map 容器中，用做索引的键的类型
map<K,V>::mapped_type	在 map 容器中，键所关联的值的类型
map<K,V>::value_type	一个 pair 类型，它的 first 元素具有 const map<K,V>::key_type 类型，而 second 元素则为 map<K,V>::mapped_type 类型

定义了 map 容器后，下一步工作就是在容器中添加键－值元素对。该项工作可使用 insert 成员实现；或者，先用下标操作符获取元素，然后给获取的元素赋值。在这两种情况下，一个给定的键只能对应于一个元素这一事实影响了这些操作的行为。

使用下标访问 map 对象

map <string, int> word_count; // empty map

// insert default initialzed element with key Anna; then assign 1 to its value

word_count["Anna"] = 1;

　　对于 map 容器，如果下标所表示的键在容器中不存在，则添加新元素，这一特性可使程序惊人地简练：

1 // count number of times each word occurs in the input
3 map<string, int> word_count; // empty map from string to int
5 string word;
6 
7 while (cin >> word)
8　　 ++word_count[word];

map::insert 的使用

 1 // count number of times each word occurs in the input
 2 map<string, int> word_count; // empty map from string to int
 3 string word;
 4 
 5 while (cin >> word) {
 6 // inserts element with key equal to word and value 1;
 7 // if word already in word_count, insert does nothing
 8 pair<map<string, int>::iterator, bool> ret =
 9     word_count.insert(make_pair(word, 1));
10 
11 if (!ret.second) 
12 // word already in word_count
13     ++ret.first->second; // increment counter
14 }

map 对象的迭代遍历

 1 // get iterator positioned on the first element
 2 map<string, int>::const_iterator
 3     map_it = word_count.begin();
 4 
 5 // for each element in the map
 6 while (map_it != word_count.end()) {
 7 // print the element key, value pairs
 8     cout << map_it->first << " occurs "
 9             << map_it->second << " times" << endl;
10     ++map_it; // increment iterator to denote the next element
11 }

set 类型

set 容器只是单纯的键的集合。set 不支持下标操作符，而且没有定义 mapped_type 类型。在 set 容器中，value_type 不是 pair 类型，而是与 key_type 相同的类型。它们指的都是 set 中存储的元素类型。这一差别也体现了 set 存储的元素仅仅是键，而没有所关联的值。与 map 一样，set 容器存储的键也必须唯一，而且不能修改。

multimap 和 multiset 类型

map 和 set 容器中，一个键只能对应一个实例。而 multiset 和 multimap类型则允许一个键对应多个实例。
注意到，关联容器 map 和 set 的元素是按顺序存储的。而 multimap 和multset 也一样。因此，在 multimap 和 multiset 容器中，如果某个键对应多个实例，则这些实例在容器中将相邻存放。以下介绍查找元素的几种策略。

使用 find 和 count 操作

 1 // author we'll look for
 2 string search_item("Alain de Botton");
 3 
 4 // how many entries are there for this author
 5 typedef multimap<string, string>::size_type sz_type;
 6 sz_type entries = authors.count(search_item);
 7 // get iterator to the first entry for this author
 8 multimap<string,string>::iterator iter =
 9 authors.find(search_item);
10 
11 // loop through the number of entries there are for this autho
12 for (sz_type cnt = 0; cnt != entries; ++cnt, ++iter) 
13     cout <<iter->second << endl; // print each title

另一个更优雅简洁的方法是使用两个未曾见过的关联容器的操作：lower_bound 和 upper_bound。m.lower_bound(k) 返回一个迭代器，指向键不小于 k 的第一个元素m.upper_bound(k) 返回一个迭代器，指向键大于 k 的第一个元素。

 1 // definitions of authors and search_item as above
 2 // beg and end denote range of elements for this author
 3 typedef multimap<string, string>::iterator authors_it;
 4 
 5 authors_it beg = authors.lower_bound(search_item),
 6     end = authors.upper_bound(search_item);
 7 
 8 // loop through the number of entries there are for this author
 9 while (beg != end) 
10 {
11     cout << beg->second << endl; // print each title
12     ++beg;
13 }

最后，更为简洁的是使用equal_range操作。m.equal_range(k) 返回一个迭代器的 pair 对象。它的 first 成员等价于 m.lower_bound(k)。而 second 成员则等价于 m.upper_bound(k)

// 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;
}