【C++基础】系列博客为参考《C++ Primer中文版（第5版）》（C++11标准）一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.关联容器概述
关联容器（有序的和无序的）都支持【C++基础】第五十一课：[顺序容器]容器库概览中介绍的普通容器操作（见表9.2）。关联容器不支持顺序容器的位置相关的操作，例如push_front或push_back。原因是关联容器中元素是根据关键字存储的，这些操作对关联容器没有意义。而且，关联容器也不支持构造函数或插入操作这些接受一个元素值和一个数量值的操作。
除了与顺序容器相同的操作之外，关联容器还支持一些顺序容器不支持的操作和类型别名。此外，无序容器还提供一些用来调整哈希性能的操作。
关联容器的迭代器都是双向的。
2.定义关联容器
当定义一个map时，必须既指明关键字类型又指明值类型；而定义一个set时，只需指明关键字类型，因为set中没有值。每个关联容器都定义了一个默认构造函数，它创建一个指定类型的空容器。我们也可以将关联容器初始化为另一个同类型容器的拷贝，或是从一个值范围来初始化关联容器，只要这些值可以转化为容器所需类型就可以。在新标准下，我们也可以对关联容器进行值初始化：
1
2
3
4
5
map<string, size_t> word_count;//空容器
//列表初始化
set<string> exclude = {"the","but","and","or","an","a","The","But","And","Or","An","A"};
//三个元素
map<string, string> authors = { {"Joyce","James"},{"Austen","Jane"},{"Dickens","Charles"} };
与以往一样，初始化容器必须能转换为容器中元素的类型。对于set，元素类型就是关键字类型。
当初始化一个map时，必须提供关键字类型和值类型。我们将每个关键字-值对包围在花括号中：
1
{key, value}
来指出它们一起构成了map中的一个元素。在每个花括号中，关键字是第一个元素，值是第二个。
2.1.初始化multimap或multiset
一个map或set中的关键字必须是唯一的，即，对于一个给定的关键字，只能有一个元素的关键字等于它。容器multimap和multiset没有此限制，它们都允许多个元素具有相同的关键字。
下面的例子展示了具有唯一关键字的容器与允许重复关键字的容器之间的区别。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<vector>
#include<map>
#include<set>
using namespace std;
int main()
{
//定义一个有20个元素的vector，保存0到9每个整数的两个拷贝
vector<int> ivec;
for(vector<int>::size_type i=0;i!=10;i++)
{
ivec.push_back(i);
ivec.push_back(i);//每个数重复保存一次
}
//iset包含来自ivec的不重复的元素；miset包含所有20个元素
set<int> iset(ivec.cbegin(), ivec.cend());
multiset<int> miset(ivec.cbegin(), ivec.cend());
cout<<ivec.size()<<endl;//打印出20
cout<<iset.size()<<endl;//打印出10
cout<<miset.size()<<endl;//打印出20
return 0;
}
测试下map：
1
map<string,int> m={ {"1",1},{"1",1},{"2",2} };//m只有2个不重复的元素，第1个是{"1",1}，第2个是{"2",2}
3.关键字类型的要求
关联容器对其关键字类型有一些限制。对于有序容器——map、multimap、set以及multiset，关键字类型必须定义元素比较的方法。默认情况下，标准库使用关键字类型的<运算符来比较两个关键字。
传递给排序算法的可调用对象必须满足与关联容器中关键字一样的类型要求。
3.1.有序容器的关键字类型
可以提供自己定义的操作来代替关键字上的<运算符。所提供的操作必须在关键字类型上定义一个严格弱序（strict weak ordering）。可以将严格弱序看作“小于等于”，它必须具备如下基本性质：
- 两个关键字不能同时“小于等于”对方；如果k1“小于等于”k2，那么k2绝不能“小于等于”k1。
- 如果k1“小于等于”k2，且k2“小于等于”k3，那么k1必须“小于等于”k3。
- 如果存在两个关键字，任何一个都不“小于等于”另一个，那么我们称这两个关键字是“等价”的。如果k1“等价于”k2，且k2“等价于”k3，那么k1必须“等价于”k3。
如果两个关键字是等价的（即，任何一个都不“小于等于”另一个），那么容器将它们视作相等来处理。当用作map的关键字时，只能有一个元素与这两个关键字关联，我们可以用两者中任意一个来访问对应的值。
3.2.使用关键字类型的比较函数
用来组织一个容器中元素的操作的类型也是该容器类型的一部分。为了指定使用自定义的操作，必须在定义关联容器类型时提供此操作的类型。如前所述，用尖括号指出要定义哪种类型的容器，自定义的操作类型必须在尖括号中紧跟着元素类型给出。
在尖括号中出现的每个类型，就仅仅是一个类型而已。当我们创建一个容器（对象）时，才会以构造函数参数的形式提供真正的比较操作（其类型必须与在尖括号中指定的类型相吻合）。
比如定义一个自定义的操作：
1
2
3
4
bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs)
{
return lhs.isbn() < rhs.isbn();
}
为了使用自己定义的操作，在定义multiset时我们必须提供两个类型：关键字类型Sales_data，以及比较操作类型——应该是一种函数指针类型，可以指向compareIsbn。
1
2
3
//bookstore中多条记录可以有相同的ISBN
//bookstore中的元素以ISBN的顺序进行排列
multiset<Sales_data, decltype(compareIsbn)*> bookstore(compareIsbn);
此处，我们使用decltype来指出自定义操作的类型。记住，当用decltype来获得一个函数指针类型时，必须加上一个*来指出我们要使用一个给定函数类型的指针。用compareIsbn来初始化bookstore对象，这表示当我们向bookstore添加元素时，通过调用compareIsbn来为这些元素排序。即，bookstore中的元素将按它们的ISBN成员的值排序。可以用compareIsbn代替&compareIsbn作为构造函数的参数，因为当我们使用一个函数的名字时，在需要的情况下它会自动转化为一个指针。当然，使用&compareIsbn的效果也是一样的。
4.pair类型
pair定义在头文件utility中。一个pair保存两个数据成员。类似容器，pair是一个用来生成特定类型的模板。当创建一个pair时，我们必须提供两个类型名，pair的数据成员将具有对应的类型。两个类型不要求一样：
1
2
3
pair<string, string> anon;//保存两个string
pair<string, size_t> word_count;//保存一个string和一个size_t
pair<string, vector<int>> line;//保存string和vector<int>
pair的默认构造函数对数据成员进行值初始化。因此，anon是一个包含两个空string的pair，line保存一个空string和一个空vector。word_count中的size_t成员值为0，而string成员被初始化为空。
我们也可以为每个成员提供初始化器：
1
pair<string, string> author{"James", "Joyce"};
与其他标准库类型不同，pair的数据成员是public的。两个成员分别命名为first和second。我们用普通的成员访问符号来访问它们，例如：
1
2
//打印结果
cout << w.first << " occurs " << w.second << ((w.second>1) ? " times" : " time") << endl;
此处，w是指向map中某个元素的引用。map的元素是pair。标准库只定义了有限的几个pair操作，表11.2列出了这些操作。
4.1.创建pair对象的函数
想象有一个函数需要返回一个pair。在新标准下，我们可以对返回值进行列表初始化：
1
2
3
4
5
6
7
8
pair<string, int> process(vector<string> &v)
{
//处理v
if(!v.empty())
return {v.back(), v.back().size()};//列表初始化
else
return pair<string, int>();//隐式构造返回值
}
我们还可以用make_pair来生成pair对象，pair的两个类型来自于make_pair的参数：
1
2
if(!v.empty())
return make_pair(v.back(), v.back().size());
