原创 【博客大赛】《C++ Primer》学习笔记（29）关联容器

顺序容器按照位置来存储它们的元素，关联容器使用key。
两种基本的关联容器类型是map和set，map包含有key-value pair，set仅仅包含了key。
set可以用来保存那些我们希望忽略的文本，而map非常适合用来存储字典。

关联容器的类型：
map
set
multimap
multiset
unordered_map
unordered_set
unordered_multimap
unordered_multiset

关联容器的头文件：
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

11.1 Using an Associative Container
----------------------------------------------------------------
map通常被称为关联矩阵（associative array），因为它的特性类似array，
map和array的区别是，map的下标不一定是整型数。

如果用map存储号码簿，人名就是key，电话号码就是value，我们可以通过人名索引到号码。
再比如下面这段用于计算字符串出现次数的代码：
map<string, size_t> word_count;
string word;
while (cin >> word)
    ++word_count[word];
for (const auto &w : word_count)
    cout << w.first << " occurs " << w.second << endl;

执行结果是：
[marianna@localhost Debug]$ ./hello
hello
hello
world
world
world
hello occurs 2
world occurs 3

和顺序容器一样，关联容器也是模板，这意味着它需要参数才能完成初始化。
比如在上面的代码里，string就是key的类型，size_t是value的类型，使用key来索引value。

下面是一段有关set的代码：
map<string, size_t> word_count;
set<string> exclude = {"hello", "world"};
string word;
while (cin >> word) {
    if (exclude.find(word) == exclude.end())
        ++word_count[word];
}
for (const auto &w : word_count)
    cout << w.first << " occurs " << w.second << endl;

执行结果是：
[marianna@localhost Debug]$ ./hello
hello
world
world
maria
maria
here
here occurs 1
maria occurs 2

11.2 Overview of the Associative Container
----------------------------------------------------------------
关联容器支持大部分的和顺序容器一样的操作，比如size()、clear()等。
关联容器不支持push_front或者push_back，这两个操作对关联容器没有意义。
关联容器不支持使用element和count构成的构造函数或者insert函数。

另外，关联容器具备自己独特的方法，比如对hach值的tuning。
另外，关联容器的迭代器是双向的。

关联容器的初始化：
map<string, string> authors = {
        {"Joyce", "James"},
        {"Austen", "Jane"},
        {"Dickens", "Charles"}
};

map和set的key必须是独一无二的，但是multimap和multiset的key可以有很多个元素。
比如下面的代码：
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;
cout << iset.size() << endl;
cout << miset.size() << endl;

执行结果是：
[marianna@localhost Debug]$ ./hello
20
10
20

key的类型，必须使得元素之间可以比较。
我们也可以自定义key的比较方式，称为strict weak ordering：
 * 两只key不能同时小于对方。
 * 如果k1小于k2，k2小于k3，那么k1一定会小于k3.
 * 如果两只key都没有小于对方，则它们相等，如果k1=k2，k2=k3，则k1=k3。
如果多只key相等，那么它们都会索引到同一个value。

为了自定义一个可比较的multiset，我们必须指定了两个类型，一是key，一是comparion类型。
比如下面的代码：
bool compare(const Sales_data &lhs, const Sales_data &rhs)
{
    return lhs.isbn() < rhs.isbn();
}
int main(int argc, char *argv[])
{
    multiset<Sales_data, decltype(compare) *> bookstore(compare);
    return 0;
}

pair是一种library type，定义在utility头文件中，它包含了两个（可不一样的）数据。
比如：
pair<string, size_t> word_count;
pair<string, string> author{"James", "Joyce"};

pair的元素是public的，成员分别称为first和second。
map的元素就是pair类型。
可对pair进行的操作很少，只有构造、取元素和比较等几种。

11.3 Operations on Associative Containers
----------------------------------------------------------------
关联容器定义了如下的类型：
key_type      key的类型
mapped_type   value的类型，map才有，set没有
value_type    pair类型，set的与key一样，map的是一个pair

当我们dereference一个迭代器时，返回的时value_type的引用。
由于value_type的key是const的，因此我们可以通过迭代器获取key，但不能更改它。

练习题：
multiset<string> c = {"hello", "world"};
vector<string> v = {"goodbye", "maria"};

copy(v.begin(), v.end(), inserter(c, c.end()));  //正确
copy(v.begin(), v.end(), back_inserter(c));      //错误，没有push_back
copy(c.begin(), c.end(), inserter(v, v.end()));  //正确
copy(c.begin(), c.end(), back_inserter(v));      //正确

关联容器如何添加元素呢？
使用insert函数。
因为map和set的key是唯一的，因此添加已有的key不会产生任何影响。
insert函数的返回值是一个pair<iterator, bool>，分别是迭代器和bool flag。
insert函数对于multimap的返回值仅仅是迭代器，因为bool对它没有意义，它总是成功的。

关联容器如何删除元素呢？
使用erase函数。

关联容器如何使用下标？
仅仅只有map和unordered_map可以使用下标，其他关联容器都不行。
下标是key。
c[k]，如果没有此元素则添加；
c.at[k]，如果没有此元素则throw一个out_of_range异常。

关联容器如何搜索元素？
如果我们关心这个特定的元素是否存在，则使用find；
如果我们关心这个特定的multimap元素是否存在，则使用count。
另外，使用lower_bound配合upper_bound也是一个好办法。
另外，equal_range更直接，它的返回值pair刚好对应lower_bound和upper_bound。

11.4 The Unordered Containers
----------------------------------------------------------------
无序容器的key，通过hash值来存储。。
如果我们无法对key进行排序的话，就可以考虑使用无序容器。

无序容器实际上是把它的各个元素放置在了n个木桶里，再通过hash索引过去。

hash表，也称散列表，是根据关键码值(key value)而直接进行访问的数据结构。也就是说，
它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。做法是，通过把Key使用固定
的算法函数即所谓的哈希函数转成一个整型数字，然后将该数字对数组长度取余，取余结果就当作数组
的下标，将value值存储再以该数字为下标的数组空间里。

 * 有关无序容器的内容有些复杂，后面还需要深入学习！