关联容器
关联容器支持高效的关键字查找和访问，两个主要的关联容器类型就是map和set，此篇博客主要围绕map展开。
标准库提供8个关联容器，这些容器间的不同体现在三个维度中：
（1）或者是一个map，或者是一个set
（2）或者要求不重复的关键字，或者允许重复关键字
（3）按顺序保存元素，或无序保存
允许重复关键字的容器的名字中都包含单词multi；不保持关键字按顺序存储的容器的名字都以unordered开头。
pair类型
在介绍关联容器操作之前，先来了解名为pair的标准库类型，它定义在头文件utility中。
一个pair保存两个数据成员。类似容器，pair是一个用来生成特定类型的模板。
pair<T1,T2> p; 创建一个空的pair对象，它的两个元素分别是T1和T2类型，采用值初始化
pair<T1,T2> p(v1,v2); 创建一个pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，second成员初始化为v2
pair<T1,T2> p = {v1,v2}; 等价于p(v1,v2)
make_pair(v1,v2) 返回一个用v1和v2初始化的pair。pair的类型从v1和v2的类型中推断出来
p.first 返回p中名为first的数据成员
p.second 返回p中名为second的数据成员
与其它标准库类型不同，pair的数据成员是public的。两个成员分别被命名为first，second，使用普通的成员访问符来访问它们。
创建pair对象的函数
在新标准下，我们可以对返回值进行列表初始化。
pair<string,int> process(vector<string> &v)
{
if(!v.empty())
return {
v.back(), v.back.size()}; //列表初始化
//return make_pair(v.back(),v.back.size()); //也可以
else
return pair<string,int> (); //隐式构造返回值
}
map类型
map是关键字-值对的集合。它定义在头文件map中，当定义一个map时，必须指明关键字类型又指明值类型。
1.map对象的定义与初始化
map<k,v> m; 创建一个名为m的空map对象，其键和值类型分别为k和v类型
map<k,v> m(m2); 创建一个m2的副本m，m和m2必须要有相同的键和值类型
map<k,v> m(b,e); 创建map类型的对象m，存储迭代器b和e标记范围内所有元素的副本。
2.map中的类型
key_type 关键字类型
mapped_type 与关键字关联的类型：只适用与map
value_type 为pair<const key_type,mapped_type>
map<string, int>::key_type v1; //v1是一个string
map<string, int>::mapped_type v2; //v2是一个int
map<string, int>::value_type v3; //v3是一个pair<const string, int>
3.map中添加元素
给map添加元素有两种方式：一是先用下标获取元素，让然后给获取的元素赋值。二是使用insert成员实现。
类似于我们用过的其它下标运算符，map下标运算符接收一个索引（即一个关键字）获取与此关键字相关联的值。但是，与其它下标运算符不同的是，如果关键字并不在map中，会为它创建一个元素并插入到map中，关联值将进行值初始化。
map<string,int> word_count;
word_count["Anna"]=1;
- 在word_count中查找键为Anna的元素，没有找到。
- 将一个新的键-值对插入到word_count容器中，键为Anna(const)，值初始化为0。
- 提取出新插入的元素，并将值1赋予它。
由于下标运算符可能插入一个新元素，所以我们只能对非const的map使用。
对一个map进行insert操作时，元素类型一定是pair。
c.insert(e) e是一个用在c上的vaule_type类型的值。如果键e.first不在m中，则插入一个键为e.first值为e.seconde的元素。
如果该键在c中已存在。则c保持不变。
该函数返回一个pair类型的对象，包含指向键为e.first的元素的map迭代器，以及一个bool类型的对象，表示是否插入成功。
c.insert(beg,end) beg和end是标记元素范围的迭代器，其中的元素必须为c.value_type类型的键-值对。
对于该范围内的所有元素，如果它的键在c中不存在，则将该键及其关联的值插入c。返回void
c.insert(iter,e) e是一个用在vaule_type类型的值。如果键不在c中，则创建新元素，并以迭代器iter为起点搜索新元素存储的位置。
返回一个迭代器，指向c中具有给定键的元素。
//添加元素的4种方法
word_count.insert({
word, 1});
word_count.insert(make_pair(word, 1));
word_count.insert(pair<string, size_t> (word, v1));
word_count.insert(map<string, size_t>::value_type(word, 1));
4.map中访问元素
关联容器提供多种查找一个指定元素的方法，使用那个操作依赖于我们要解决什么问题。
c.find(k) 返回一个迭代器，指向第一个关键字为k的元素，若k不在容器中，则返回尾后迭代器。
c.count(k) 返回关键字等于k的元素的数量（对map而言，返回值永远是0或1）。
c.lower_bound(k) 返回一个迭代器，只向第一个关键字不小于k的元素。
c.upper_bound(k) 返回一个迭代器，只向第一个关键字大于k的元素。.
c.equal_range(k) 返回一个迭代器pair，表示关键字等于k的元素的范围。若k不存在，pair的两个成员均等于c.end()。
对map使用find代替下标操作
上面我们提过，如果关键字未在map中，下标操作会插入一个具有给定关键字的元素。
但是，有时我们只是想知道此关键字是否在map中，而不想改变map。这种情况，应该使用find：
if(word_count.find("temp") == word_count.end())
cout << "temp is not in the map" << endl;
5.map中删除元素
c.erase(k) 删除c中键为k的元素。返回size_type类型的值，表示删除的元素个数
c.erase(p) 从c中删除迭代器p指向的元素。p必须指向c中确实存在的元素，而且不能等于c.end()。
返回一个指向p之后元素的迭代器，若p指向c中的尾元素，则返回c.end()。
c.erase(b,e) 删除迭代器对b和e所表示的范围中的元素，返回e。
6.map对象的迭代器
当解引用map时，我们会得到类型为容器的value_type( pair<const key_type, mapped_type> )的值的引用。
auto map_it = word_count.begin();
cout << map_it->first; //打印关键字
cout << map_it->second; //打印值
map_it->first = "new key"; //错误：关键字是const的
++map_it->second; //正确
一个map的value_type是一个pair，我们可以改变pair的值，但不能改变关键字的值
map也支持begin和end操作，可以用其来遍历。
auto map_it = word_count.begin();
while(map_it != word_count.end())
{
cout << map_it->first << "occurs" << map_it->second << "times"<<endl;
++map_it;
}