C++ Container

关联容器支持高效的关键字查找和访问，两个主要的关联容器是 set 和 map。map 中的元素是一些键值对(key-value)，关键字起着索引的作用，值则表示与索引相关联的数据，set 中的元素只包含一个关键字。set 支持高效的关键字查找操作，底层应该是用的哈希表来实现的。

C++标准库提供了 8 个关联容器，这 8 个容器的不同体现在三个维度上：

1. set 或者 map
2. 有序或者无序---有无 unordered 前缀
3. 允许或禁止重复关键字---有无 multi 前缀

本文重点介绍 set 和 map，关于其他容器的相关内容可以查看 C++的 API

set 与 map 的使用

使用 map：

//统计每个单词在输入中出现的次数
map<string,size_t> word_count;	//新建map
string word;
while(cin>>word)
	++word_count[word];    //将该单词所对应的次数加1
for(const auto &w:word_count)
	cout<<w.first<<" occurs "<<w.second<<((w.second>1)?" times":" time")<<endl;

需要注意，对于 map 的下标操作如果使用 word_count[word]，在未找到 word 关键字的时候会添加一个关键字为 word 的元素，对其值进行初始化。如果使用 word_count.at(word)，在未找到 word 关键字的时候会抛出一个 out_of_range 异常。

使用 set：

//统计输入中每个单词出现的次数
map<string,size_t> word_count;
set<string> exclude={"The","But","And","Or","An"};
string word;
while(cin>>word)
	if(exclude.find(word)==exclude.end())   //当在set中未find时，返回尾迭代器
	++word_count[word];

##pair 类和关联容器中额外的类型别名 pair 类定义在头文件 utility 中，一个 pair 保存两个数据成员。类似于容器，pair 是一个用来生成特定类型的模板。当创建一个 pair 的时候，我们必须提供两个类型名。

pair<string,size_t> word_count;	//保存string和size_t

与其他的标准库类型不同，pair 的数据成员是 public 的，两个成员分别命名为 first 和 second，map 中保存的元素就是 pair 类型的。

关联容器还定义了其他的类型，这些类型表示容器关键字和值的类型：

• key_type 容器的关键字类型
• mapped_type 每个关键字关联的类型，只适用于 map
• value_type 对于 set，与 key_type 相同，对于 map，为 pair<const key_type,mapped_type>

set<string>::value_type v1;	//string
set<string>::key_type v2;  //string
map<string,int>::value_type v3;	//pair<const string,int>
map<string,int>::key_type v4;	//string
map<string,int>::mapped_type v5;//int

##关联容器的迭代器 当解引用一个关联容器的迭代器时，会得到一个类型为容器的 value_type 的值的引用。对 map 而言，value_type 是一个 pair 类型，其 first 成员保存 const 的关键字，second 成员保存值：

//获得指向word_count中一个元素的迭代器
auto map_it=word_count.begin();
//*map_it是指向一个pair<const string,size_t>对象的引用
cout<<map_it->first;
cout<<" "<<map_it->second;
map_it->first="new key";  //错误，关键字是const的
++map_it->second;   //值的元素是可以改变的

一个 set 中的关键字也是 const 的。可以用一个 set 来读取元素的值，但是不能修改：

set<int> iset={0,1,2,3,4,5,6,7,8,9};
set<int>::iterator set_it=iset.begin();
if(set_it!=iset.end()){
	*set_it=42;   //错误，const的关键字不能修改
	cout<<*set_it<<endl;
}