【C++基础】系列博客为参考《C++ Primer中文版（第5版）》（C++11标准）一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.关联容器
关联容器和顺序容器有着根本的不同：关联容器中的元素是按关键字来保存和访问的。与之相对，顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的。
虽然关联容器的很多行为与顺序容器相同，但其不同之处反映了关键字的作用。
关联容器支持高效的关键字查找和访问。两个主要的关联容器（associative-container）类型是map和set。map中的元素是一些关键字-值（key-value）对：关键字起到索引的作用，值则表示与索引相关联的数据。set中每个元素只包含一个关键字；set支持高效的关键字查询操作——检查一个给定关键字是否在set中。
标准库提供8个关联容器，如表11.1所示。这8个容器间的不同体现在三个维度上：每个容器（1）或者是一个set，或者是一个map；（2）或者要求不重复的关键字，或者允许重复关键字；（3）按顺序保存元素，或无序保存。允许重复关键字的容器的名字中都包含单词multi；不保持关键字按顺序存储的容器的名字都以单词unordered开头。因此一个unordered_multi_set是一个允许重复关键字，元素无序保存的集合，而一个set则是一个要求不重复关键字，有序存储的集合。无序容器使用哈希函数来组织元素。
类型map和multimap定义在头文件map中；set和multiset定义在头文件set中；无序容器则定义在头文件unordered_map和unordered_set中。
2.使用关联容器
map是关键字-值对的集合。例如，可以将一个人的名字作为关键字，将其电话号码作为值。map类型通常被称为关联数组（associative array）。关联数组与“正常”数组类似，不同之处在于其下标不必是整数。我们通过一个关键字而不是位置来查找值。
与之相对，set就是关键字的简单集合。当只是想知道一个值是否存在时，set是最有用的。
2.1.使用map
一个经典的使用关联数组的例子是单词计数程序：
1
2
3
4
5
6
7
8
//统计每个单词在输入中出现的次数
map<string, size_t> word_count;//string到size_t的空map
string map;
while(cin >> word)
++word_count[word];//提取word的计数器并将其加1
for(const auto &w : word_count)//对map中的每个元素
//打印结果
cout << w.first << " occurs " << w.second << ((w.second>1) ? " times" : " time") << endl;
类似顺序容器，关联容器也是模板。为了定义一个map，我们必须指定关键字和值的类型。在此程序中，map保存的每个元素中，关键字是string类型，值是size_t类型。
在while循环中，如果word还未在map中，下标运算符会创建一个新元素，其关键字为word，值为0。
当从map中提取一个元素时，会得到一个pair类型的对象。简单来说，pair是一个模板类型，保存两个名为first和second的（公有）数据成员。map所使用的pair用first成员保存关键字，用second成员保存对应的值。
2.2.使用set
上一个示例程序的一个合理扩展是：忽略常见单词，如“the”、“and”、“or”等。我们可以使用set保存想忽略的单词，只对不在集合中的单词统计出现次数：
1
2
3
4
5
6
7
8
//统计输入中每个单词出现的次数
map<string, size_t> word_count;//string到size_t的空map
set<string> exclude = {"The","But","And","Or","An","A","the","but","and","or","an","a"};
string word;
while(cin >> word)
//只统计不在exclude中的单词
if(exclude.find(word) == exclude.end())
++word_count[word];//获取并递增word的计数器
与其他容器类似，set也是模板。为了定义一个set，必须指定其元素类型，本例中是string。与顺序容器类似，可以对一个关联容器的元素进行列表初始化。
find调用返回一个迭代器。如果给定关键字在set中，迭代器指向该关键字。否则，find返回尾后迭代器。
