关联容器支持高效的关键字查找和访问。两个主要的关联容器（associative-container）类型是map和set。标准库提供8个关联容器，它们的不同体现在三个维度上：
- 或者是一个set，或者是一个map
- 或者要求不重复的关键字，或者允许重复关键字
- 按顺序保存元素，或无序保存。
允许重复关键字的容器的开头名字中都包含单词multi；不保持关键字按顺序存储的容器的名字都以单词unordered开头。
类型map和multimap定义在头文件map中；set和multiset定义在头文件set中，无序容器则定义在unordered_map和unordered_set中。
关联容器概述
定义关联容器
每个关联容器都定义了一个默认构造函数，它创建一个指定类型的空容器。也可以将关联容器初始化为另一个同类型容器的拷贝，或是从一个值范围来初始化关联容器，只要这些值可以转化为容器所需类型就可以。在新标准下，也可以对关联容器进行值初始化。
map<string, size_t> word_count; //空容器
set<string> exclude = {"the", "but", "and", "or"}; //列表初始化
//三个元素：authors将姓映射为名
map<string, string> authors = {
{"Joyce", "James"},
{"Austen", "Jane"},
{"Dickens", "Charles"}
};初始化一个map时，必须提供关键字和值类型。我们将每个关键字-值对包围在花括号中: {key,value}
来指出它们一起构成了map中的一个元素。
初始化multimap和multiset
一个map或set中的关键字必须是唯一的，multimap和multiset则没有此限制。
vector<int> ivec;
for(vector<int>::size_type i = 0; i != 10; i++)
{
ivec.push_back(i);
ivec.push_back(i);
}
set<int> iset(ivec.begin(), ivec.end());
multiset<int> miset(ivec.begin(), ivec.end());
cout<<ivec.size()<<endl; //打印出20
cout<<iset.size()<<endl; //打印出10
cout<<miset.size()<<endl; //打印出20pair类型
定义在头文件utility中。
一个pair保存两个数据称愿。类似容器，pair是一个用来生成特定类型的模板。当创建一个pair时，我们必须提供两个类型名，pair 的数据成员将具有对应的类型。两个类型不要求一样。
pair<string, string> anon;
pair<string, size_t> word_count;
pair<string, vector<int>> line;pair的默认构造函数对函数成员进行值初始化（string被初始化为空字符串，size_t被初始化为0）。也可以为每个成员提供初始化器：
pair<string, string> author("James", "Joyce");
pair<string, string> author()与其他标准库类型不同，pair的数据成员是public的，两个成员分别命名为first和second，我们用普通的成员访问符号来访问它们。
其他操作：
pair<string, string> author;
pair<string, string> author1("aaaa","dddd");
pair<string, string> author2{"aaaa","dddd"};
pair<string, string> author3 = {"aaaa","dddd"};
//返回一个用v1和v2初始化的pair，pair的类型从v1和v2的类型推断出来
auto p = make_pair(11,22);
auto q = make_pair("aaaa", "bbbb");关联容器操作
| 类型别名 | 含义 |
|---|---|
| key_type | 此容器类型的关键字类型 |
| mapped_type | 每个关键字关联的类型；只适用于map |
| value_type | 对于set，与key_type相同 对于map，为 pari<const key_type, mapped_type>
|
由于我们不能改变一个元素的关键字，因此这些pair的关键字部分是const的。只有map类型才定义了mapped_type。
一个map的value_type是一个pair，我们可以改变pair的值，但不能改变关键字成员的值。
添加元素
c.insert(v) //v是value_type类型的对象
c.emplace(args)
c.insert(b,e) //b,e是迭代器
c.insert(il) //il是value_type类型值的花括号列表
c.insert(p, v) //类似于`insert(v)`，但将迭代器p作为一个提示，指出从哪里开始搜索新元素应该存储的位置
c.emplace(p, args)删除元素
c.erase(k) //从c中删除每个关键字为k的元素，返回一个size_t类型的值，指出删除的元素的数量
c.erase(p) //从c中删除迭代器p指定的元素，返回一个指向p之后元素的迭代器
c.erase(b, e) 删除迭代器对b和e所表示的范围中的元素。返回e。map的下标操作
类似于其他下标操作符，map下标操作符接受一个索引，获取与此关键字相关联的值。与其他下标操作不同的是，如果关键字不存在于map中，会为它创建一个元素并插入到map中，关联值将进行值初始化。
| 操作 | 含义 |
|---|---|
| c[k] | 返回关键字为k的元素；如果不存在则添加一个关键字为k的元素，对其进行值初始化 |
| c.at(k) | 访问关键字为k的元素，带参数检查；若k不在c中，抛出一个out_of_range异常 |
map的下标操作符返回一个左值，既可以读也可以写。
访问元素
| 操作 | 含义 |
|---|---|
| c.find(k) | 返回一个迭代器，指向第一个关键字为k的元素，若k不在容器中，则返回尾后迭代器 |
| c.count(k) | 返回关键字等于k的元素的数量。对于不允许重复的容器，返回值永远是0或1 |
| c.lower_bound(k) | 返回一个迭代器，指向第一个关键字不小于k的元素 |
| c.upper_bound(k) | 返回一个迭代器，指向第一个关键字大于k的元素 |
| c.equal_range(k) | 返回一个迭代器pair，表示关键字等于k的元素的范围。若k不存在，pair的两个成员均等于c.end() |
无序容器
新标准定义了4个无序关联容器（unordered associative container）。这些容器不是使用比较运算符来组织元素，而是使用一个哈希函数（hash function）和关键字类型的==运算符。
除了哈希管理操作之外，无序容器还提供了与有序容器相同的操作。
有序容器的迭代器通过关键字有序访问容器中的元素。无论在有序容器中还是在无序容器中，具有相同关键字的元素都是相邻存储的。
哈希函数（hash function）将给定类型的值映射到整型(size_t)值的函数。相等的值必须映射到相同的整数；不相等的值应尽可能映射到不同整数。
严格弱序：关联容器所使用的关键字间的关系。在一个严格弱序中，可以比较任意两个值并确定哪个更小。若任何一个都不小于另一个，则认为这两个值相等。
转载：http://blog.csdn.net/foreverling/article/details/44274699