关联容器

关联容器与顺序容器的本质差别在于：关联容器通过键值（key）存储和读取元素，而顺序容器则通过袁术在容器中的位置存储和访问元素。

1 关联容器类型概述

关联容器（Associative containers）支持通过键来高效地查找和读取元素。两个基本的关联容器类型是map 和 set。标准库提供了8个关联容器：

map类型通常被称为"关联数组"。map 的元素以键－值（key-value）对的形式组织：键用作元素在 map 中的索引，而值则表示所存储和读取的数据。关联数组与普通数组类似，不同之处在于其下标不必是整数，需要通过关键值而非位置来查找对应值。
set类型是简单关键词的集合，高效存储和访问不同的关键词。set 仅包含一个键，并有效地支持关于某个键是否存在的查询。
另外6个类型与map以及set类型相关，multi前缀类型支持重复的关键词，unorder前缀类型是无序集合，用哈希函数组织。

2 关键字要求

关联容器对其关键字有一些限制：

2.1 有序容器关键字

默认情况下，标准库使用关键字类型的<运算符来比较两个关键字。用户可以提供一个自己定义的操作来替代关键字上的<，所提供的操作必须是严格弱序的。所谓严格弱序，必须遵序以下几点：

不能同时出现a<= b, b<=a的情况
如果a<=b且b<=c，那么a<=c
如果存在a不小于c，c不小于等于a的情况，则a，c等价。如果a,c等价，b,c等价，则a,c等价。

2.2 无序容器关键字

默认情况下，使用关键字类型==运算符来比较元素，它们还使用一个hash<key_type>类型的对象为每个元素生成哈希值。标准库为内置类型，包括指针提供了哈希模板，还为string等标准库类型定义了哈希，因此上述类型可直接定义无需容器。

当使用自定义类型定义无序容器时，我们还需要通过模板特例化，提供自己的hash模板版本。

3 pair类型

在介绍关联容器之前，我们需要了解名为pair的标准库类型，它定义在头文件utility中。

一个pair保存两个数据成员。类似容器，pair是一个用来生成特定类型的模板。创建一个pair时，必须提供两个类型名，pair的数据成员将具有对应的类型。pair上定义的操作如下：

除了构造函数，标准库还定义了一个make_pair函数，由传递给它的两个实参生成一个新的pair对象，实例如下：

pair<string, string> example;
string first, second;
example = make_pair(first, second);

提示：pair类型定义较为繁琐，适当使用typedef可以提高编程的效率。

4 关联容器的操作

4.1 类型操作

关联容器支持以下类型：

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

4.2 迭代器

当解引用一个关联容器迭代器时，我们会得到一个类型为value_type的值的引用。对map而言，这是一个pair，其first是const的关键字，second成员保存值。对set而言，其迭代器是const的，其关键字不能修改，示例如下：

map<string, int> mWordCnt;
auto m_iter = mWordCnt.begin();
//*m_iter是指向pair<tring, int>对象的引用
//iter->first是const，不能修改；只能修改其关联的值
m_iter->first = "new key";  //错误
++m_iter->second;            //正确
cout << m_iter->first << " " << m_iter->second;

set<string> sNames;
auto s_iter = sNames.begin();
*s_iter = "new key";          //错误，关键字不能修改

map和set都支持用begin和end函数问出首尾迭代器，并以此进行关联容器的遍历。由于关键字是const这一特性，我们不能将关联容器传递给修改或者重排容器元素的算法。在实际编程中，我们不通常不对关联容器使用泛型算法，即使使用，也只是将其作为一个源序列，或者当做一个目标位置来存放计算结果。

4.3 添加元素

关联容器的inset成员可以向容器中添加一个元素或者一个元素的范围。由于map和set不包含重复的关键字，因此插入一个已经存在的元素没有任何影响。

向map添加元素

在C++11中，使用insert函数添加单个元素通常有以下四种操作方式：

map<string, int> mWordCnt;
mWordCnt.insert({ "fiset", 1 });
mWordCnt.insert(make_pair("fiset", 1));
mWordCnt.insert(pair<string, int>("fiset", 1));
mWordCnt.insert(map<string, int>::value_type("fiset", 1));

除上述的四种方式，标准库还支持insert某个范围的元素。需要注意的是：在插入单个元素时，insert函数会返回一个pair，first是当前成员的迭代器，second是一个bool变量，当插入成功是返回true，如果该元素已经存在则返回false；在插入某个范围的元素时，函数只返回void。详细说明如下表：

向set添加元素

同样，可以使用insert向set容器添加元素：

set<string> sStr; // empty set
sStr.insert("the"); // sStr now has one element
sStr.insert("and"); // sStr now has two elements

另一种用法是，调用insert函数时，提供一对迭代器实参，插入其标记范围内所有的元素。该版本的insert函数类似于形参为一对迭代器的构造函数——对于一个键，仅插入一个元素：

vector<string> vStr = { "it`s", "a", "test" };
set<string> sStr2;  // empty set
sStr2.insert(vStr.begin(), vStr.end()); // sStr2 has 3 elements

4.4 删除元素

关联容器定义了三个版本的erase。与顺序容器一样，我们可以通过传递给erase一个迭代器或者迭代器对，来删除一个元素或者一个元素的范围。这与添加元素十分相似，不再赘述。

关联容器提供了一个额外的erase，它接受一个key_type参数。此版本删除所有匹配给定关键词的元素，并返回实际删除的数量。示例如下：

vector<string> vStr = { "a", "a", "a" };
multiset<string> sStr3;  // empty set
sStr3.insert(vStr.begin(), vStr.end()); // sStr2 has 3 elements
auto nCnt = sStr3.erase("a");// nCnt  == 3

4.5 map下标

set类型不支持下标，因为set中没有关键字相关联的“值”，“值”本身就是关键字。我们可以对map和unordermap容器进行下标运算符以及at函数的操作。但是，不能对multi的版本进行相应操作，因为后者可能出现多个值与一个关键字对应的情况。

与其他下标运算符不同的是，如果关键字不再map中，会为它创建一个元素并插入到map中，关键值将进行初始化。

map<string, int> mWordCnt;
mWordCnt["basketball"] = 1;

上述代码将会执行如下操作：

在mWordCnt中查找basketball关键字，未找到
将一个新的关键字-值对插入mWordCnt中，关键字是一个const string，保存basketball，并对second进行默认初始化（int初始化为0）
取出新插入的元素，并将1值赋予它

另外，需要注意的是，map下标运算法返回的是mapped_type对象，但在解引用一个map迭代器时，会得到一个value_type对象。

4.6 元素访问

find函数可以返回指向元素的迭代器，如果元素不存在，则返回尾后迭代器。count返回元素的个数，如果不需要计数，只需要知道是否存在，建议使用find，`可以减少函数工作了，提供效率。

对于multi前缀的类型，一个关键字可能对应多个值，其访问通常有三种方式：

1. 先用count问出数量，后用find问出第一个元素的位置，最后依次遍历

auto nCnt = mWordCnt.count("basketball");
auto iter = mWordCnt.find("c");
while (nCnt){
    cout << iter->second << endl;
    ++iter;
    --nCnt;
}

1. 使用lower_bound和upper_bound问出关键字的上下界。注意：无需容器不支持这两个函数

multimap<string, int> mWordCnt;
for (auto beg = mWordCnt.lower_bound("basketball"),
    end = mWordCnt.upper_bound("basketball");
    beg != end; ++beg){
        cout << beg->second << endl;
}

1. 使用equal_range函数，该函数返回一个迭代器pair类型，first是指向第一个元素的迭代器，second指向该关键字尾后迭代器的值。

multimap<string, int> mWordCnt;
for (auto range = mWordCnt.equal_range("basketball"); 
    range.first != range.second; ++range.first){
        cout << range.first->second << endl;
}