关联型容器
一、概述
关联性容器支持高效的关键字查找和訪问。当中元素是按关键字来保存和訪问的，主要关联型容器类型是map和set。map中的一些元素是pair<key, value>，即键值对，关键字起到索引的作用，值则表示与索引关联的数据。set中每一个元素仅仅包括一个关键字；set支持高效的关键字查询操作——检查一个给定关键字是否在set中。字典是使用map非常好的样例；
标准库提供8个关联容器，如图所看到的。
不同之处体如今三个维度：
1.或者是map，或者是set
2.或者是有序。或者是无序
3.或者是同意反复，或者不同意反复
map和multimap定义在头文件map中；
set和multiset定义在set文件里。
无序容器定义在unordered_map和unordered_set中
二、定义关联容器
定义map时。必须之名关键字类型和值类型。而定义set时。仅仅需指明关键字类型；
定义空容器：map<string, size_t> word;
列表初始化(C++11)：
map<string, size_t> m;
map<string, size_t> n{{"tubin", 1}, {"tufang", 2}, {"tianlan", 3}};
map<string, size_t> p(n.begin(), n.end());
for (const auto & w : p) {
cout << w.first << " " << w.second << endl;
}当初始化map时。必须提供关键字类型和值类型，用{}花括号扩起来；
三、关键字类型的要求
3.1 关键字类型
关联型容器对关键字类型有些限制。
对于有序容器，关键字类型必须定义元素比較的方法。
默认情况下，标准库使用关键字类型的<运算符来比較两个关键字。
能够提供自己定义的操作取代关键字的<运算符，仅仅是该操作必须在关键字类型上定义一个严格弱序。（<=）
在实际编程中，假设一个类型定义了“行为正常”的<运算符，则它能够用作关键字类型。
3.2使用关键字类型的比較函数
为了指定使用自己定义的操作。必须在定义关联容器时提供比較操作的类型。
自己定义操作类型必须在尖括号里紧跟着元素类型给出。
方法1
//自己定义比較函数
bool compare_size(const string &a, const string &b) {
return a.size() < b.size();
}
//指定比較函数
map<string, size_t, decltype(compare_size)*> word(compare_size);decltype指出自己定义操作的类型。但当它作用于函数时得到的并不是是函数指针，而是函数类型，因此必须加上*
再用compare_size来显示初始化word对象。此时将会调用map的explicit带參构造。
方法2
//定义
template <typename T>
struct Longer : public binary_function<T, T, bool> {
bool operator() (const T& x, const T& y) const {
return x.size() > y.size();
}
};
//使用
map<string, size_t, Longer<string>> word;
看过STL源代码之后，能够通过自己定义一个函数。继承自标准库的模版，就能够得到可配接(adaptable)的函数对象了。
3.3 简单应用
能够定义vector::iterator 到 int 的map，可是不能定义list::iterator 到 int 的map.
由于vector中迭代器即为原生指针。支持<运算符，但list的迭代器不支持<运算符，由于不是连续存储的。比較大小没有意义；
四、pair类型
pair标准库类型，定义在utility中。一个pair保存两个数据成员。相似容器，pair是一个用来省城特定类型的模版。创建pair时必须提供两个类型名，两者不要求一样。
创建pair
//使用默认构造
pair<string, string> p1;
pair<string, size_t> p2;
pair<string, vector<int> p3;
//提供初始化器
pair<string, string> author{"my", "mht"};
//make_pair();
pair<string, string> p = make_pair("al", "bd");
//显示构造
p3 = pair<string, vector<int>>();
使用pair
pair的数据成员是public的，两个成员分别命名为first和second。
用对象訪问：cout << author.first << author.second;
用指针訪问：cout << w->first << w->second;
五、简单使用关联容器
ex1：单词计数程序 map
//自己定义推断符号
map<string, size_t, Longer<string>> word_count;
string record;
while (cin >> record) {
++word_count[record];
}
for ( const auto & w : word_count) {
cout << w.first << ": " << w.second
<< (w.second > 1 ? "times": "time") << endl;
}ex2：忽略常见单词的计数程序 map set
/用set保存想忽略的单词，在统计前推断
map<string, size_t> word_count;
set<string> exclude = {"the", "The", "and", "And", "a", "A", "or", "Or"};
string word;
while (cin >> word) {
//不在exclude中
if (exclude.find(word) == exclude.end()) {
++word_count[word];
}
}
for (const auto& w : word_count) {
cout << w.first << ": " << w.second
<< (w.second > 1 ? " times" : " time")
<< endl;
}
六、关联容器操作
key_type 容器的关键字类型
mapped_type 每一个关键字关联的类型，仅仅适用于map
value_type 对于set，与key_type 同样;对于map，是pair
6.1 关联容器迭代器
迭代器
解引用一个迭代器得到一个容器的value_type值的引用。
当中，set的迭代器是const的，value_type即为key_type，是const的
对于map，value_type的first成员是key_type, 也是const的。
容器和算法
我们通常不正确关联容器使用泛型算法。关键字是const这一特性意味着不能使用mutable 算法。仅仅应用于制度的算法；但这类型的算法都要搜索序列，不能进行高速查找。
因此对于关联性容器使用泛型搜索算法。差点儿总是个坏主意。应该使用关联性容器专用的成员。
（见后文）
实际应用
在实际应用中。假设要使用算法，要么当作一个源序列，要么当一个目的位置。
6.2 加入元素
四种方法加入元素
map<string, size_t> m;
m.insert({"tubin", 1});
m.insert(make_pair("tufang", 2));
m.insert(pair<string, size_t>("lanlan", 3));
m.insert(map<string, size_t>::value_type("tiantian", 4));返回值
1.对于不包括反复关键字的容器，加入元素返回一个pair<iterator, bool>，bool标识插入成功与否。
2.对于包括反复关键字的容器，加入元素一定能成功，因此返回的是指向新元素的iterator
重写单词计数程序
map<string, size_t> word_count;
string word;
while (cin >> word) {
auto ret = word_count.insert({word, 1});
if (!ret.second) {
++ret.first->second;//解析例如以下
}
}解析：
ret保存返回值pair<iterator, bool>
ret.first 为iterator，指向value_type<key_type, mapped_type>
ret.first->second 为值mapped_type
++ret.first->second 递增此值
6.3 删除元素
标准库定义函数例如以下：
erase（k）：返回实际删除的元素的数量；
对于不反复容器。erase返回的值总是0(不存在) or 1(存在)；
对于反复容器。erase返回的值可能大于1；
6.4 map的下标操作
特定容器提供
map和unordered_map提供下标[ ]运算符和相应at函数；
set不提供，由于没有相关联的值；
multi-不提供；由于下标索引到的结果可能有多个。
特性
下标操作接受一个索引（关键字），获取与之相关联的值。但主要特性是。假设没有该索引，则创建一个元素并插入到map中。关联值将进行值初始化。
因此，仅仅能对非const版本号提供下标操作
at操作
訪问关键字为k的元素，带有參数检查；假设k不存在，则抛出异常；
返回值
通常情况下，解引用一个迭代器返回类型与下标运算返回类型一致；但对于map则不然。
对map。下标操作返回一个mapped_type对象； 解引用迭代器。得到value_type(pair)对象.
总结
下标和at操作仅仅指针对于非const的map和unordered_map
6.5 訪问元素
标准库定义例如以下查找元素的操作
对于不同意反复容器。count和find没差别；
对于同意反复容器，count还要统计个数；
因此。对于count。find，[]
假设指向知道给定关键字是否在map中。而不想改变map，则用find；否则用[]
假设不想计数。则用find。否则用count
在multimap,multiset中查找元素的三种方法
ex:在给定一个从作者到著作题目的映射。打印一个特定作者的全部著作，有三种方法
1 count + find
multimap<string, string> m{{"my", "tb"}, {"my", "tm"}, {"my", "zfb"}, {"mht", "QQ"}, {"mht", "wx"}};
string item = "my";
auto entries = m.count(item); //统计个数，假设没有返回0
auto iter = m.find(item); //找到第一个。假设没有返回end()
while (entries) {
cout << iter->second << endl;
++iter;
--entries;
}2 lower_bound ＋ upper_bound
lower_bound:返回迭代器指向第一个具有给定关键字的元素。
upper_bound:返回的迭代器指向最后一个匹配给定关键字的元素之后的位置；
假设关键字不存在。则lower_bound和upper_bound会返回相等的迭代器；（有可能都是尾后迭代器）
for (auto b = m.lower_bound(item), e = m.upper_bound(item);
b != e; ++b) {
cout << b->second << endl;
}3 equal_range
equal_range返回的是pair，当中两个成员各自是调用的lower_bound和upper_bound得到的迭代器。因此，此方法和上面方法没有本质的差别；唯一的差别是：不须要定义局部变量来保存元素范围；
for (auto p = m.equal_range(item); p.first != p.second; ++p.first) {
cout << p.first->second << endl;
}7 无序容器
新标准定义了4个无序容器。这些容器不是用比較运算符来组织元素，而是是哟过一个哈希函数和关键字类型的==运算符。
在关键字无明显的序的关系时，无序容器是非常实用的。
7.1使用无序容器
无序容器的使用和相应的有序容器的使用全然同样。唯一的差别就是内容是无序的。不能指望输出的结果是有序的。
通常，能够用一个无序容器替换相应的有序容器，反之亦然。
7.2 管理桶(bucket)
无序容器在存储上组织为一组桶，每一个桶保存0或多个元素。
(SGI STL源代码中哈希表採用分离链接法实现)。
对于同样的參数。哈希函数必须总是产生同样的鸡诶过。
7.3 对关键字类型的要求
1 默认情况哎。无序容器使用关键字类型==运算符来比較元素。他们还使用一个hash类型的对象来生成每一个元素的哈希值。
2 标准库为内置类型(包括指针类型)。string和智能指针类型定义了hash模版，因此我们能够直接定义相相应的无序容器。
3 可是我们不能直接定义关键字类型为自己定义类型的无序容器。除非我们提供自己的hash模版版本号。
7.4 自己定义类型容器
1 自己定义
相似于自己定义map关键字类型比較函数一样，我们也自己定义函数取代==运算符合哈希函数
//自己定义函数
size_t hasher(const A& s) {
return hash<string>()(s.name());
}
bool equal_A(const A& a1, const A& a2) {
return a1.name() == a2.name();
}
//使用这些函数来定义一个unordered_set
unordered_set<A, decltype(hasher)*, decltype(equal_A)*> usa1(43, hasher, equal_A);
//简化
//类型定义
using SD_Set = unordered_set<A, decltype(hasher)*, decltype(equal_A)*>;
//定义unordered_set
SD_Set s(43, hasher, equal_A);
2 模版特例化
对于内置类型直接定义：unordered_set<int> us;
为了让自己定义数据类型也能用默认方式，必须定义hash模版的一个特例版本号。
一个特例化hash类必须定义：
1.一个重载的调用运算符，接受一个容器关键字类型的对象。返回size_t
2.两个类型成员，result_type和argument_type，分别为调用运算符()的返回类型和參数类型
3.默认构造和拷贝赋值运算符(可隐式定义)
唯一复杂的地方就是须要在原模版定义所在的命名空间中特例化。
详细定义例如以下：
//假设A为自己定义类型
class A {
public:
string name() const { return name_; }
private:
int size_;
string name_;
};
／／为A类型特例化hash模版
namespace std {//打开命名空间
template<>//表示正在定义一个特例化版本号。模版參数为A
struct hash<A>
{
typedef size_t result_type;
typedef A argument_type;
size_t operator()(const A& s) const;
};
size_t hash<A>::operator()(const A &s) const {
return hash<string>()(s.name());
}
} //关闭命名空间。注意，此处无分号。
//定义A类型的无序容器
unordered_set<A> usa;