关联容器的元素是按关键字来保存和访问的。
而顺序容器是按容器位置的顺序访问。
学过Python就可以理解成列表和字典的关系。
关联容器支持高效的关键字查找和访问。两个主要的关联容器(associative-container)类型是map和set。
map的元素是关键字-值(key-value)对：关键字起到索引的作用，值表示和索引相关联的数据。set里每个元素只有一个关键字：set支持高效的关键字查询操作——检查一个给定关键字是否存在set里
比如在某些文本处理过程中，可以用一个set来保存想要忽略的单词。字典则是使用map的好例子，可以把单词作为关键字，释义作为值。
标准库提供8个关联容器：
| 关联容器类型 | 含义 | 包含在头文件 |
|---|---|---|
| 按关键字有序保存元素 | ||
map |
关联数组：保存关键字-值对 | map |
set |
关键字即值，只保存关键字的容器 | set |
multimap |
关键字可以重复出现的map |
map |
multiset |
关键字可以重复出现的set |
set |
| 无序集合 | ||
unordered_map |
用哈希函数组织的map |
unordered_map |
unordered_set |
用哈希函数组织的set |
unordered_set |
unordered_multimap |
用哈希函数组织的map，关键字可以重复出现 |
unordered_map |
unordered_multiset |
用哈希函数组织的set，关键字可以重复出现 |
unordered_set |
上述8个容器的不同主要体现在三个维度：
- 每个容器或者是个
set或者是个map - 或者要求不重复的关键字，或者允许重复的关键字
- 按顺序保存元素，按无序保存元素。
不保存关键字按顺序存储的容器都以unordered单词开头。所以unordered_multiset是个允许重复关键字，元素无序保存的集合；而set则是要求不重复关键字、有序存储的集合。
map类型常称关联数组(associative array)。关联数组和"正常"数组类似，不同之处在于其下标不必是整数。
set就是关键字的简单集合。只想知道一个值是否存在的时候，用set最好。
map制作单词计数程序示例：
// 统计每个单词在输入中出现的次数
map<string, size_t> word_count; // string到size_t的空map
string word;
while (cin >> word)
++word_count[word]; // 提取word到计数器并将其加1
for (const auto &w : word_count) // 对map里的每个元素
// 打印结果
cout << w.first << " occurs" << w.second << ((w.second > 1) ? " times" : " time") << endl;此程序读取输入，报告每个单词出现了几次。
关联容器也是模板。
为定义map，必须指定关键字和值的类型。此例程序，string是关键字的类型(类似Python的键)，值是size_t类型。
而string就是容器map的下标。
如果word还不在map里面，那么下标运算符就会创建一个新元素，其关键字是word，值是0。不管元素是不是新建的，我们把它的值加1。
上个示例程序的一个扩展：忽略常见单词：the、and、or。
可以用set保存想要忽略的单词，只对不再集合里的单词统计次数：
// 统计输入中每个单词出现的次数
map<string, size_t> word_count; // string到size_t的空map
set<string> exclude = {"The", "But", "And", "Or", "An", "A", "the", "but", "and", "or", "an", "a"};
string word;
while (cin >> word)
// 只统计不在exclude中的单词
if (exclude.find(word) == exclude.end()) ++word_count[word]; // 获取并递增word的计数器
for (const auto &w : word_count) // 对map里的每个元素
// 打印结果
cout << w.first << " occurs" << w.second << ((w.second > 1) ? " times" : " time") << endl;set也是模板。定义set需要指定其元素类型，如本例的string。可以对关联容器的元素进行列表初始化。集合exclude中保存了12个像忽略的单词。
if(exclude.find(word) == exclude.end())find调用返回一个迭代器。如果给定关键字在迭代器里，迭代器指向该关键字。否则find返回尾后迭代器。只有word不在exclude的时候才更新word计数器.
关联容器支持第九章介绍的普通容器操作。关联容器不支持顺序容器的位置相关的操作，例如push_front和push_back。原因是关联容器中元素是根据关键字存储的，这些操作对于关联容器没有意义。
除此之外关联容器还支持一些顺序容器不支持的操作和类型别名。无序容器还提供一些用来调整哈希性能的操作。关联容器的迭代器都是双向的。
每个关联容器都定义了一个默认构造函数，它创建了一个指定类型的空容器。
也可以把关联容器初始化成另一个同类型容器的拷贝，或者是从一个值范围来初始化关联容器。
在C++11后，也可以对关联容器进行值初始化：
map<string, size_t> word_count; // 空容器
// 列表初始化
set<string> exclude = {"the", "but", "and", ...};
// 三个元素 authors将姓映射为名
map<string, string> authors = {
{"Joyce", "James"}, // 关键字"Joyce"的值是"James"
{"Austen", "Jane"},
{"Dickens", "Charles"}
};和以往一样，初始化器必须要可以转换成容器里元素的类型。对于set，元素类型就是关键字类型。
当初始化一个map时，必须提供关键字类型和值类型。将每个关键字-值对包含在花括号中：{key, value}。
一个map或set里的关键字必须是唯一的。容器multimap和multiset没有这个限制。
也就可以理解成multimap定义的单词可以有多个词义，而非map那样一个单词只能一个词义。
创建名为ivec的保存int的vector，包含20个元素：0到9每个整数有两个拷贝。将此vector初始化一个set和multiset：
// 定义一个有20个元素的vector 保存0到9每个整数的两个拷贝
vector<int> ivec;
for (vector<int>::size_type i = 0; i != 10; ++1) {
ivec.push_back(i);
ivec.push_back(i); // 每个数多复制一次
}
set<int> iset(ivec.cbegin(), ivec.cend()); // iset包含来自ivec的不重复的元素
multiset<int> miset(ivec.cbegin(), ivec.end()); // miset包含所有20个元素
cout << ivec.size() << endl; // 打印20
cout << iset.size() << endl; // 打印10
cout << miset.size() << endl; //打印20即使用整个ivec容器来初始化iset，它也只有10个元素(不同元素)。而miset有20个元素，和ivec一样多。
有序容器的关键字类型必须定义元素比较的方法。默认情况下，标准库使用关键字类型的<运算符来比较两个关键字。
- 在集合类型里，关键字类型就是元素类型
- 在映射类型里，关键字类型是元素的第一部分的类型
如map<string, size_t> word_count;的word_count和set<string> exclude的exclude的关键字类型就是string
传递给排序算法的可调用对象必须满足和关联容器中关键字一样的类型要求
也可以提供自己定义的操作来代替关键字上的<。所提供的操作必须在关键字类型上定义一个严格弱序(strict weak ordering)。
可以把严格弱序看成是"小于等于"，实际定义的操作可能是个复杂函数。但是不管怎么定义函数，都必须具备如下基本性质：
- 两个关键字不能同时"小于等于"对方；如果
k1小于等于k2，那么k2就不能小于等于k1。 - 如果
k1小于等于k2，且k2小于等于k3，那么k1必须小于等于k3 - 如果存在两个关键字，任何一个都不小于等于另一个，那么我们称这两个关键字是等价的。如果
k1等价于k2，且k2等价于k3，那么k1必须等价于k3。
如果两个关键字是等价的，那么容器把他们当作相等来处理。当用作map的关键字时，只能有一个元素与这两个关键字关联，可以用两者中任意一个来访问对应的值。
实际编程中，如果一个类型定义了"行为正常"的<运算符，那么它可以用作关键字类型。
用来组织容器中元素的操作的类型也是该容器类型的一部分。
例如不能直接定义一个Sales_data的multiset，因为Sales_data里没有<运算符。但是可以用compareIsbn函数来定义一个multiset。该函数在Sales_data对象的ISBN成员上定义了一个严格弱序。函数compareIsbn应该向如下这么定义：
bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs)
{
return lhs.isbn() < rhs.isbn();
}为使用自定义的操作(compareIsbn)，在定义multiset时候必须提供两个类型：
-
关键字类型
Sales_data -
比较操作类型——应该是一种函数指针类型，可以指向
compareIsbn。当定义该容器类型的对象时，需要提供想要使用的操作的指针。
// 提供一个指向compareIsbn的指针
// bookstore中多条记录可以有相同的ISBN
// bookstore中的元素以ISBN的顺序进行排列
multiset<Sales_data, decltype(compareIsbn)*> bookstore(compareIsbn);使用decltype来指出自定义操作的类型。当用decltype获得一个函数指针类型的时候，必须加上*来表明我们要用一个给定函数类型的指针。用compareIsbn来初始化bookstore对象，表明向bookstore添加元素的时候，通过调用compareIsbn来为这些元素排序。
可以用compareIsbn代替&compareIsbn作为构造函数的参数，因为在我们使用一个函数的名字时候，在需要的情况下它会自动转换成一个指针。使用&compareIsbn也一样。
pair是定义在头文件utility中的标准库类型
一个pair保存两个数据成员。
pair是个用来生成特定类型的模板。
创建pair的时候，必须提供两个类型名，pair的数据成员将具有对应的类型。
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，word_count是个空string和0而line则是空string和空vector
也可以给每个成员提供初始化器：
// 创建一个pair类型的author,它的两个成员是"James"和"Joyce"
pair<string, string> author("James", "Joyce");pair的数据成员是public的。两个成员分别命名为first和second。可以用普通的成员访问符号访问他们，如前面示例中的：
cout << w.first << " occurs " << w.second << ((w.second) > 1) ? " times" : " time") << endl;w是指向map某个元素的引用。map的元素是pair。这条语句中，首先打印关键字元素的first成员，然后打印关键字的计数器second成员。
标准库定义的pair操作：
pair上的操作 |
|
|---|---|
pair<T1, T2> p; |
p是个pair，两个类型分别对T1和T2的成员进行了值初始化 |
pair<T1, T2> p<v1, v2>pair<T1, T2> p=(v1, v2); |
p是个成员类型是T1和T2的pairfirst和second使用v1和v2进行初始化 |
make_pair(v1, v2) |
返回一个用v1和v2初始化的pair。pair的类型从v1和v2的类型推断出来 |
p.first |
返回p的名为first的公有数据成员 |
p.second |
返回p的名为second的公有数据成员 |
p1 relop p2 |
关系运算符按字典序定义 ： 例如当 p1.first < p2.first或!(fp.first<p1.first)为真时，就表示 p1<p2。关系运算使用元素的<来实现 |
p1 == p2p1 != p2 |
当first和second成员分别相等时候，两个pair相等。 |
假设有个函数需要返回一个pair。新标准中，可以对返回值进行列表初始化
pair<string, int> process(vector<string> &v)
{
// 处理v
if (!v.empty())
return (v.back(), v.back().size()); // 列表初始化
else
return pair<string, int>(); // 隐式构造返回值
}若v不为空，就返回一个由v中最后一个string及其大小组成的pair。否则隐式构造一个空pair，并返回它
早期C++中，不允许使用花括号包围的初始化器来返回pair这种类型的对象，必须是显示构造返回值：
if (!v.empty())
return pair<string, int> (v.back(), v.back().size());还可以用make_pair来生成pair对象，pair的两个类型来自于make_pair的参数：
if (!v.empty())
return make_pair(v.back(), v.back().size());| 关联容器额外的类型别名 | |
|---|---|
key_type |
此容器类型的关键字类型 |
mapped_type |
每个关键字关联的类型：只适用于map |
value_type |
对于set，和key_type相同对于 map，是pair<const key_type, mapped_type> |
map元素是关键字-值对，也就是map的每个元素就是一个pair对象。因为不能改变元素的关键字，所以这些pair的关键字部分是const的。
set<string>::value_type v1; // v1是个string
set<string>::key_type v2; // v2是个string
map<string, int>::value_type v3; // v3是个pair<const string, int>
map<string, int>::key_type v4; // v4是个string
map<string, int>::mapped_type v5; // v5是个int解引用关联容器迭代器的时候，会得到一个类型是容器的value_type的值的引用。对于map来说，value_type是个pair类型，它的first成员保存const的关键字，second成员保存值
// 获得指向word_count中一个元素的迭代器
auto map_it = word_count.begin();
// *map_it是指向一个pair<const string, size_t>对象的引用
cout << map_it->first; // 打印该元素的关键字
cout << " " << map_it->second; // 打印该元素的值
map_it->first = "new key"; // 错误 关键字是const的
++map_it->second; // 正确 可以通过迭代器改变元素虽然set类型同时定义了iterator和const_iterator类型，但是两种类型都只允许访问set里的元素。
可以用一个set迭代器来读元素的值，但是不能修改：
set<int> iset = {0,1,2,3,4,5,6,7,8,9};
set<int>::iterator set_it = iset.begin();
if (set_it != iset.end()) {
*set_it = 42; // 错误 set的关键字是只读的
cout << *set_it << endl; // 正确 可以读关键字
}循环打印单词计数程序的结果：
// 获得一个指向首元素的迭代器
auto map_it = word_count.cbegin();
// 比较当前迭代器和尾后迭代器
while (map_it != word_count.cend()) {
// 解引用迭代器 打印关键字-值对
cout << map_it->first << " occurs" << map_it->second << " times" << endl;
++map_it; // 递增迭代器 移动到下个元素
}需要注意的是，因为单词计数程序是用的有序关联容器，所以此处的打印是按照关键字在字典中的升序遍历的。
通常不会对关联容器使用泛型算法。
关键字是const这一特性意味着不能把关联容器传递给修改或这重排容器元素的算法，因为这类算法需要向元素写入值，而set类型里的元素是const的，map中的元素是pair，第一个成员是const的。
关联容器的insert成员向容器中添加一个元素或者一个元素范围。
对不重复关联容器插入已经存在的元素对容器没有任何的影响。
vector<int> ivec = {2,4,6,8,2,4,6,8} // ivec有8个元素
set<int> set2; // 空集合
set2.insert(ivec.cbegin(), ivec.cend()); // set2有4个元素
set2.insert({1,3,5,7,1,3,5,7}); // set2现在有8个元素insert有两个版本，一个接受一对迭代器，一个接受一个初始化器列表
因为map的元素类型是pair，想要插入可以在insert里创建一个pair：
// 向word_count插入word的4种方法
word_count.insert({word, l});
word_count.insert(make_pair(word, l));
word_count.insert(pair<string, size_t>(word, l));
word_count.insert(map<string, size_t>::value_type(word, l));C++11后最简单的方法是在参数列表里直接用花括号初始化。也可以调用make_pair或显式构造pair。
| 关联容器insert操作 | 操作含义 | 返回 |
|---|---|---|
c.insert(v)c.emplace(args) |
v是value_type类型的对象args用来构造一个元素对于 map和set，只有在元素的关键字不在c里面的时候才插入或者构造元素。 |
返回一个pair，包含一个迭代器，指向具有指定关键字的元素，以及一个指示插入是否成功的bool值 |
c.insert(b, e)c.insert(il) |
b和e是迭代器，表示一个c::value_type类型值的范围il是这种值得花括号列表。 |
返回void |
c.insert(p, v)c.emplace(p, args) |
类似insert(v)或emplace(args)，但是把迭代器p作为一个提示，指出从哪里开始搜索新元素应该存储的位置。 |
返回一个迭代器，指向具有给定关键字的元素。 |
insert或emplace返回的值依赖于容器类型和参数。因为使用单一元素的insert或者emplace插入版本会返回一个pair，而pair的first是指向具有关键字的元素，而second成员是个表示插入是否成功的bool值，所以其实可以拿来重写单词计数程序。
使用insert重写单词计数程序：
// 统计每个单词在输入中出现次数的一种更繁琐的方式
map<string, size_t> word_count; // 从string到size_t的空map
string word;
while(cin >> word) {
// 插入一个元素 关键字等于word 值是1
// 如果word已经存在word_count当中 那么insert啥也不干
auto ret = word_count.insert({word, l});
if (!ret.second) // word如果已经在word_count中
++ret.first->second; // 递增计数器
}关于second成员的bool值：若关键字已在容器中，则insert啥也不干，且返回值返回一个false。如果不在容器里面，就表示插入成功，也就返回true了。
可以用一些括号来反映出运算符的优先级：
++((ret.first)->second);ret：保存insert的返回值，是个pairret.first：是指向具有给定关键字的map迭代器ret.first->second：表示解引用那个迭代器，提取map元素，元素是个pair，再提出该pair的值++ret.first->second：递增，指向map(也就是word_count)的下个位置
如果是旧版本编译器，或是阅读新标准推出前的代码，ret声明和初始化可能更加复杂：
pair<map<string, size_t>::iterator, bool> ret = word_count.insert(make_pair(word, l));multimap<string, string> authors;
// 插入第一个元素 关键字是Barth, John
authors.insert({"Barth, John", "Sot-Weed Factor"});
// 正确 添加第二个元素 关键字也是Barth, John
authors.insert({"Barth, John", "Lost in the Funhouse"});对允许重复关键字的容器，接受单个元素的insert操作返回一个指向新元素的迭代器。
不需要返回一个是否插入成功的bool值，因为multi允许重复。
| 操作 | 含义 | 返回值 |
|---|---|---|
c.erase(k) |
从c中删除每个关键字为k的元素 |
size_type值，指出删除的元素的数量 |
c.erase(p) |
从c中删除迭代器p指定的元素。p必须指向c中的一个真实存在的元素 |
指向p之后元素的迭代器，若p指的是c的尾元素，则返回c.end() |
c.erase(b, e) |
删除迭代器对b和e所表示的范围中的元素 |
e |
// 删除一个关键字 返回删除的元素数量
if (word_count.erase(removal_word))
cout << "ok: " << removal_word << " removed\n";
else cout << "oops: " << removal_word << " not found!\n";对于保存不重要关键字的容器，erase的返回值总是0或者1。返回0表示删除对象不在容器中，对允许重复关键字的容器，删除元素的数量可能会大于1：
auto cnt = authors.erase("Barth, John");| map和unordered_map的下标操作 | 含义 |
|---|---|
c[k] |
返回关键字是k的元素如果 k不在c里面，添加一个关键字是k的元素，并对其初始化 |
c.at(k) |
访问关键字是k的元素，带参数检查如果 k不在c里面，抛出一个out_of_range异常 |
set类型不支持下标，因为set中没有和关键字相关联的"值"。也不能对multi开头的进行下标操作，因为它们可能有多个相同的关键字(或者说是多个值和一个关键字相关联！)。
map <string, size_t> word_count; // empty map
// 插入一个关键字是Anna的元素 关联值进行值初始化 然后把数字1赋予它
word_count["Anna"] = 1- 它会先找是不是有
Anna这个关键字 - 因为是没有的，所以它会创建一个
Anna关键字，并且初始化一个值，这里初始化的值还不是1，而是0(因为size_t) - 最后再给它赋值，这里赋的值就是
1了。
- 对一个
map进行下标操作的时候，获得到一个mapped_type对象 - 当解引用一个
map迭代器的时候，会获得一个value_type对象
和其它下标运算符一样的是，map的下标运算符也返回一个左值。因为返回的是个左值，所以可以读也可以写元素：
cout << word_count["Anna"]; // 用Anna作为下标提取元素 会打印1
++word_count["Anna"]; // 提取元素 将其加1
cout << word_count["Anna"]; // 用Anna作为下标提取元素 会打印2有时指向知道一个元素是不是已经在map里面，如果不存在并不想添加元素，这时候就不要用下标运算符了。
| 在一个关联容器中查找元素的操作 | 返回值 |
|---|---|
lower_bound和upper_bound不适合用在无序容器 |
|
下标和at操作只适用于非const的map和unordered_map |
|
c.find(k) |
指向第一个关键字是k的元素的迭代器，如果不存在，就返回尾后迭代器 |
c.count(k) |
关键字等于k的数量。对于不允许重复关键字的容器，返回值永远是0或1 |
c.lower_bound(k) |
指向第一个关键字不小于k的元素的迭代器 |
c.upper_bound(k) |
指向第一个关键字大于k的元素的迭代器 |
c.equal_range(k) |
返回一个迭代器pair，表示关键字等于k的元素的范围。若k不存在，pair的两个成员军等于c.end() |
如果不需要计数，最好使用find
set<int> iset = {0,1,2,3,4,5,6,7,8,9};
iset.find(1); // 返回一个迭代器 指向key=1的元素
iset.find(11); // 返回一个迭代器 值是iset.end()
iset.count(1); // 返回1
iset.count(11); // 返回0有时指向知道一个元素是不是已经在map里面，如果不存在并不想添加元素，这时候就得用find或者count，但是find的目的更纯粹一些，所以显然用find比count更好
if (word_count.find("foobar") == word_count.end())
cout << "foobar is not in the map" << endl;查找元素对于允许重复关键字的关联容器来说，过程要复杂。
如果multimap或者multiset里有多个元素具有给定关键字，那么这些元素在容器里会相邻存储。
例如：给定一个从作者到著作题目的映射，可能想打印一个特定作者的所有著作，可以用三种不同方式解决该问题。最直观的方法是用find或者count：
string search_item("Alain de Botton"); // 要查找的作者
auto entries = authors.count(search_item); // 元素的数量
auto iter = authors.find(search_item); // 此作者的第一本书
// 用一个循环来找出这个作者的所有著作
while(entries) {
cout << iter->second << endl; // 打印每个题目
++iter; // 前进到下一本书
--entries; // 记录已经打印了多少本书
}使用lower_bound和upper_bound也可以解决该问题。这两个返回的迭代器组合起来可以表示一个迭代器范围，表示所有具有该关键字的元素的范围。当然这两个操作返回的迭代器也可能是容器的尾后迭代器(查找的关键字不在容器中)。
给定给lower_bound的关键字如果不存在容器中，那么lower_bound会返回关键字的第一个安全插入位置，也就是插入之后也不会影响原来容器元素顺序的地方。
用这两个操作，可以重写前面的程序：
// authors和search_item的定义和之前一样
// beg和end表示对此作者的元素的范围
for (
auto beg = authors.lower_bound(search_item), end = authors.upper_bound(search_item);
beg != end;
++beg // 递增beg 使其指向该作者下个著作
)
cout << beg->second << endl; // 打印每个题目解决该问题的最后一种方法是三种方法里最直接的，原理与使用lower_bound和upper_bound类似，都是范围。
因为equal_range返回的也是关键字的范围
// pos保存迭代器对 表示与关键字匹配的元素范围
for (
auto pos = authors.equal_range(search_item);
pos.first != pos.second;
++pos.first
)
cout << pos.first->second << endl; // 打印每个题目给定一个string，用它来转换另一个string。程序的输入是两个文件。第一个文件保存一些规则，用于转换第二个文件中的文本。每条规则由两部分组成：
- 一个可能出现在输入文件中的单词
- 一个用来替换它的短语。
若单词转换文件的内容如下：
brb be right back
k okay?
y why
r are
u you
pic picture
thk thanks!
18r later
希望转换的文本为
where r u
y dont u send me a pic
okay? thanks! later
将使用三个函数：
word_transform管理整个过程，接受两个ifstream参数：- 第一个参数绑定到单词转换文件
- 第二个参数绑定要转换的文本文件
buildMap会读取转换规则文件，并创建一个map，用于保存每个单词到其转换内容的映射transform接受一个string，如果存在转换规则，返回转换后的内容。
示例程序：单词转换程序
void word_transform(ifstream &map_file, ifstream &input)
{
auto trans_map = buildMap(map_file); // 保存转换规则
string text; // 保存输入中的每一行
while (getline(input, text)) { // 读取一行输入
istringstream stream(text); // 读取每个单词
string word;
bool firstword = true; // 控制是否打印空格
while (stream >> word) {
if (firstword)
firstword = false;
else
cout << " "; // 在单词间打印一个空格
// transform返回它的第一个参数或其转换后的形式
cout << transform(word, trans_map); // 打印输出
}
}
}- 调用
buildMap生成单词转换map，将其保存在trans_map中 while循环用getline一行一行读取文件- 使用嵌套
while循环，其中有个istringstream来处理当前行中的每个单词 - 输出过程中，内层
while循环使用一个bool变量firstword来确定是否打印一个空格。它通过调用transform来获得要打印的单词。transform的返回值或者是word中原来的string，或者是trans_map中指出的对应的转换内容
读入给定文件，建立起转换映射。
map<string, string> buildMap(ifstream &map_file)
{
map<string, string> trans_map; // 用于保存转换规则
string key; // 要转换的单词
string value; // 替换后的内容
// 读取第一个单词存入key中 行内剩余内容存入value
while (map_file >> key && getline(map_file, value))
if (value.size() > 1) // 检查是否有转换规则
trans_map[key] = value.substr(1); // 跳过前导空格
else
throw runtime_error("no rule for " + key);
return trans_map;
}map_file每行对应一条规则。每条规则由一个单词和一个短语组成，短语可能包含多个单词。用>>读取要转换的单词，存入key中，并调用getline读取这一行中的剩余部分存入value- 使用
substr从指定开始获取内容，此处为1的含义表示跳过key和value的那个空格 - 将得到的字符串传入
trans_map
我们使用下标运算符添加关键字-值对。隐含地忽略了单词在转换文件中出现多次的情况。若真有单词出现多次，循环会把最后一个对应短语存入trans_map。
循环结束后trans_map会保存用来转换输入文本的规则
const string & transform(const string &s, const map<string, string> &m)
{
// 实际的转换工作 该部分是程序核心
auto map_it = m.find(s);
// 若单词在转换规则map中
if (map_it != m.cend())
return map_it->second; // 返回替换短语
else
return s; // 否则返回string
}- 先用
find来确定给定string是否在map里面。- 如果在，则
find返回一个指向对应元素的迭代器。那么我们解引用迭代器，获得一个保存关键字和值的pair，然后函数返回成员second，也就是用来替换s的内容 - 否则
find返回一个尾后迭代器。然后函数返回s的内容
- 如果在，则
C++11定义了四个无序关联容器(unordered associative conatiner)。
这些容器使用哈希函数(has function)和关键字类型的==运算符来组织元素。
理论上哈希计数能够获得更好的平均性能，但在实际中要达到很好的效果还需要进行一些性能测试和调优工作。所以无序容器通常更加简单(通常也有更好的性能)。
无序容器提供了与有序容器相同的操作。
使用unordered_map重写单词计数程序：
// 统计出现次数 但是单词不会按照字典序排列
unordered_map<string, size_t> word_count;
string word;
while (cin >> word)
++word_count[word]; // 提取并递增word的计数器
for (const auto &w : word_count) // 对map的每个元素
// 打印结果
cout << w.first<< " occurs " << w.second << ((w.second > 1) ? " times" : "time") << endl;和map版本的唯一区别是word_count的类型。
无序容器在存储上组织为一组桶，每个桶保存零个或者多个元素。无需容器使用一个哈希函数将元素映射到桶。
为了访问一个元素，容器首先计算元素的哈希值，它指出应该搜索哪个桶。容器将具有一个特定哈希值的所有元素都保存在相同的桶里。如果容器允许重复关键字，所有具有相同关键字的元素也都会在同一个桶里。所以无序容器的性能依赖于哈希函数的质量和桶的数量的大小。
当一个桶保存多个元素是，需要顺序搜索这些元素来查找我们想要的那个。
计算一个元素的哈希值和在同种搜索通常都是很快的操作，但是如果桶里有很多元素，那么查找一个特定元素就需要很多比较操作了。
无序容器提供了一组管理桶的函数。这些成员函数允许我们查询容器的状态以及在必要时强制容器进行重组：
| 无序容器管理操作 | 含义 |
|---|---|
| 桶接口 | |
c.bucket_count() |
正在使用的桶的数目 |
c.max_bucket_count() |
容器能容纳的最多的桶的数量 |
c.bucket_size(n) |
第n个桶中有多少个元素 |
c.bucket(k) |
关键字为k的元素在哪个桶里 |
| 桶迭代 | |
local_iterator |
可以用来访问桶中元素的迭代器类型 |
const_local_iterator |
桶迭代器的const版本 |
c.begin(n)，c.end(n) |
桶n的首元素迭代器和尾后迭代器 |
c.cbegin(n)，c.cend(n) |
和上面类似，但是返回const_local_iterator |
| 哈希策略 | |
c.load_factor() |
每个桶的平均元素数量，返回float值 |
c.max_load_factor() |
c试图维护的平均桶大小，返回float值。c会在需要时添加新的桶，以使得load_factor<=max_load_factor |
c.rehash(n) |
重组存储，使得bucket_count同时小于n和size/max_load_factor |
c.reserve(n) |
重组存储，使得c可以保存n个元素且不必rehash |
无序容器用一个hash<key_type>类型的对象生成每个元素的哈希值。
标准库给内置类型包括指针提供了hash模板，还为一些标准库类型(包括string和将在十二章介绍的智能指针类型)定义了hash。所以可以直接定义关键字是内置类型、string、智能指针类型的无序容器。
但是不能直接定义关键字类型为自定义类类型的无序容器。和容器不一样，不能直接用哈希模板，而必须提供我们自己的hash模板版本。和后面会介绍到。
我们不使用默认的hash，而是用类似给有序容器重载关键字类型的默认比较操作。
为了能够把Sales_data用作关键字，可以提供函数来替代==和哈希值计算函数。从定义这些重载函数开始：
size_t hasher(const Sales_data &sd)
{
return hash<string>(sd.isbn());
}
bool eqOp(const Sales_data &lhs, const Sales_data &rhs)
{
return lhs.isbn() == rhs.isbn();
}hasher函数使用标准库hash类型对象来计算ISBN成员的哈希值，该hash类型建立在string类型之上。
eqOp函数通过比较ISBN来比较两个Sales_data。
用这些函数来定义一个unordered_multiset：
using SD_multiset = unordered_multiset<Sales_data, decltype(hasher)*, decltype(eqOp)*>;
// 参数是桶大小、哈希函数指针和相等性判断运算符指针
SD_multiset bookstore(42, hasher, eqOp);此集合的哈希跟 相等性判断操作与hasher还有eqOp函数有着相同的类型。通过这种类型，在定义bookstore的时候可以把我们希望它使用的函数的指针传递给它。
如果我们的类定义了==运算符，则可以只重载哈希函数：
// 使用FooHash生成哈希值；Foo必须有==运算符
unordered_set<Foo, decltype(FooHash)*> fooSet(10, FooHash);存在继承关系时，派生类的作用域嵌套在基类的作用域内。如果一个名字在派生类的作用域内无法解析，则编译器将继续在外层的基类作用域中寻找改名字的定义。