11.1
【出题思路】
理解顺序容器和关联容器的不同。
【解答】
学习关联容器，理解与顺序容器的不同，最关键的是理解其基础的数据结构，随后它所表现出来的一些性质就很自然能够理解了。
两类容器的根本差别在于，顺序容器中的元素是 “顺序” 存储的（链表容器中的元素虽然不是在内存中 “连续” 存储的，但仍然是按 “顺序” 存储的）。理解 “顺序” 的关键，是理解容器支持的操作形式以及效率。
对于 vector 这样的顺序容器，元素在其中按顺序存储，每个元素有唯一对应的位置编号，所有操作都是按编号（位置）进行的。例如，获取元素（头、尾、用下标获取任意位置）、插入删除元素（头、尾、任意位置）、遍历元素（按元素位置顺序逐一访问）。底层数据结构是数组、链表，简单但已能保证上述操作的高效。而对于依赖值的元素访问，例如查找（搜索）给定值（find），在这种数据结构上的实现是要通过遍历完成的，效率不佳。
而 map 这种关联容器，就是为了高效实现 “按值访问元素” 这类操作而设计的。为了达到这一目的，容器中的元素是按关键字值存储的，关键字值与元素数据建立起对应关系，这就是 “关联” 的含义。底层数据结构是红黑树、哈希表等，可高效实现按关键字值查找、添加、删除元素等操作。
11.2
【出题思路】
理解顺序容器和关联容器的适用范围。
【解答】
若元素很小（例如 int），大致数量预先可知，在程序运行过程中不会剧烈变化，大部分情况下只在末尾添加或删除，需要频繁访问任意位置的元素，则 vector 可带来最高的效率。若需要频繁在头部和尾部添加或删除元素，则 deque 是最后的选择。
如果元素较大（如大的类对象），数量预先不知道，或是程序运行过程中频繁变化，对元素的访问更多是顺序访问全部或很多元素，则 list 很合适。
map 很适合对一些对象按它们的某个特征进行访问的情形。典型的例如按学生的姓名来查询学生信息，即可将学生姓名作为关键字，将学生信息作为元素值，保存在 map 中。再比如统计单词出现的次数。
set，顾名思义，就是集合类型。当需要保存特定的值集合 —— 通常是满足/不满足某种要求的值集合，用 set 最为方便。比如黑名单。
11.3
【出题思路】
练习 map 的简单使用。
【解答】
参照本节例子完成完整程序即可。
#include <iostream>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
string &trans(string &s) {
for (int p = 0; p < s.size(); ++p) {
if (s[p] >= 'A' && s[p] <= 'Z')
s[p] += ('a' - 'A');
else if (s[p] == ',' || s[p] == '.')
s.erase(p, 1);
}
return s;
}
int main() {
// 统计每个单词在输入中出现的次数
map<string, size_t> word_count; // string 到 size_t 的空 map
string word;
while (cin >> word)
++word_count[trans(word)]; // 提取 word 的计数器并将其加 1
for (const auto &w : word_count) // 对 map 中的每个元素
// 打印结果
cout << w.first << " occurs " << w.second
<< ((w.second > 1) ? " times" : " time") << endl;
return 0;
}
// 运行结果
example. Cplusplus Primer example, Example primer
^D
cplusplus occurs 1 time
example occurs 3 times
primer occurs 2 times
Process finished with exit code 0
11.4
【出题思路】
此题并非练习 set 的使用，而是字符串的处理。
【解答】
编写函数 trans，将单词中的标点去掉，将大写都转换为小写。具体方法是：遍历字符串，对每个字符首先检查是否是大写（ASCII 值在 A 和 Z 之间），若是，将其转换为小写；否则，检查它是否带标点，若是，将其删除。最终，将转换好的字符串返回。
s.erase(pos, len); 删除从位置 pos 开始的 len 个字符。如果 len 被省略，则删除从 pos 开始直至 s 末尾的所有字符。返回一个指向 s 的引用。（书 C++ primer 5th 中文版 有有关修改 string 的介绍）
#include <iostream>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
string &trans(string &s) {
for (int p = 0; p < s.size(); ++p) {
if (s[p] >= 'A' && s[p] <= 'Z')
s[p] += ('a' - 'A');
else if (s[p] == ',' || s[p] == '.')
s.erase(p, 1);
}
return s;
}
int main() {
// 统计每个单词在输入中出现的次数
map<string, size_t> word_count; // string 到 size_t 的空 map
string word;
while (cin >> word)
++word_count[trans(word)]; // 提取 word 的计数器并将其加 1
for (const auto &w : word_count) // 对 map 中的每个元素
// 打印结果
cout << w.first << " occurs " << w.second
<< ((w.second > 1) ? " times" : " time") << endl;
return 0;
}
// 运行结果
example. Cplusplus Primer example, Example primer
^D
cplusplus occurs 1 time
example occurs 3 times
primer occurs 2 times
Process finished with exit code 0
11.5
【出题思路】
理解两种关联容器的差别。
【解答】
当需要查找给定值所对应的数据时，应使用 map，其中保存的是 <关键字, 值> 对，按关键字访问值。
如果只需判定给定值是否存在时，应使用 set，它是简单的值的集合。
11.6
【出题思路】
理解关联容器和顺序容器的差别。
【解答】
两者都可以保存元素集合。
如果只需要顺序访问这些元素，或是按位置访问元素，那么应使用 list。
如果需要快速判定是否有元素等于给定值，则应使用 set。
11.7
【出题思路】
理解 map 的稍复杂的使用。
【解答】
此 map 的关键字类型是 string，值类型是 vector<string>。
我们定义函数 add_family 添加一个家庭，注意，必须先检查是否已有这个家庭，若不做这个检查，则可能将已有家庭的孩子名字清空（如 main 函数中的王姓家庭的添加顺序）。若确实还没有这个家庭，则创建一个空的 vector<string>，表示这个家庭的孩子名字列表。
函数 add_child 向一个已有家庭添加孩子的名字：首先用 [] 运算符取出该家庭的 vector，然后调用 push_back 将名字追加到 vector 末尾。
#include <iostream>
#include <map>
#include <vector>
#include <string>
using namespace std;
void add_family(map<string, vector<string>> &families, const string &family) {
if (families.find(family) == families.end())
families[family] = vector<string>();
}
void add_child(map<string, vector<string>> &families, const string &family,
const string &child) {
families[family].push_back(child);
}
int main() {
map<string, vector<string>> families;
add_family(families, "张");
add_child(families, "张", "强");
add_child(families, "张", "三");
add_child(families, "王", "五");
add_family(families, "王");
for (auto f : families) {
cout << f.first << "家的孩子：";
for (auto c : f.second)
cout << c << " ";
cout << endl;
}
return 0;
}
// 运行结果
张家的孩子：强 三
王家的孩子：五
Process finished with exit code 0
【其他解题思路】
add_family 的函数体其实可以有一个非常简单的实现：
families[family];
当该家庭已存在时，此语句只是获取其 vector，不会导致 vector 有任何变化；若该家庭不存在，标准库 map 的实现机制是在容器中为该关键字创建一个对象，进行默认初始化，即构造一个空 vector。与 if 版本的效果完全一致。
这也是 add_child 为什么不需要检查家庭是否存在的原因，当家庭存在时，将孩子的名字追加到现有 vector 末尾；若家庭不存在，标准库会先创建一个新的空 vector，然后我们的程序将孩子名字添加进去。
11.8
【出题思路】
通过实际编程理解 set 和 vector 的差别。
【解答】
使用 vector 保存不重复单词，需要用 find 查找新读入的单词是否在 vector 中，若不在（返回尾后迭代器），才将单词加入 vector。
而使用 set，检查是否重复的工作是由 set 模版负责的，程序员无须编写对应代码，程序简洁很多。
更深层次的差别，vector 是无序线性表，find 查找指定值只能采用顺序查找方式，所花费的时间与 vector.size() 呈线性关系。而 set 是用红黑树实现的，花费的时间与 vector.size() 呈对数关系。当单词数量已经非常多时，set 的性能优势是巨大的。
当然，vector 也不是毫无用处。它可以保持单词的输入顺序，而 set 则不能，遍历 set，元素是按值的升序被遍历的。
vector 版本：
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
string &trans(string &s) {
for (int p = 0; p < s.size(); ++p) {
if (s[p] >= 'A' && s[p] <= 'Z')
s[p] += ('a' - 'A');
else if (s[p] == ',' || s[p] == '.')
s.erase(p, 1);
}
return s;
}
int main() {
vector<string> unique_word; // 不重复的单词
string word;
while (cin >> word) {
trans(word);
if (find(unique_word.begin(), unique_word.end(), word)
== unique_word.end())
unique_word.push_back(word); // 添加不重复单词
}
for (const auto &w : unique_word) // 打印不重复单词
// 打印结果
cout << w << " ";
cout << endl;
return 0;
}
// 运行结果
example. Cplusplus Primer example, Example primer
^D
example cplusplus primer
Process finished with exit code 0
set 版本：
#include <iostream>
#include <set>
#include <string>
#include <algorithm>
using namespace std;
string &trans(string &s) {
for (int p = 0; p < s.size(); ++p) {
if (s[p] >= 'A' && s[p] <= 'Z')
s[p] += ('a' - 'A');
else if (s[p] == ',' || s[p] == '.')
s.erase(p, 1);
}
return s;
}
int main() {
set<string> unique_word; // 不重复的单词
string word;
while (cin >> word) {
trans(word);
unique_word.insert(word); // 添加不重复单词
}
for (const auto &w : unique_word) // 打印不重复单词
// 打印结果
cout << w << " ";
cout << endl;
return 0;
}
// 运行结果
example. Cplusplus Primer example, Example primer
^D
cplusplus example primer
Process finished with exit code 0
11.9
【出题思路】
练习 map 的使用。
【解答】
map 的定义为：
map<string, list<int>> word_lineno;
完整程序如下所示。其中用 getline 读取一行，统计行号。再用字符串流读取这行中所有单词，记录单词行号。参见第 8 章内容。
#include <iostream>
#include <fstream>
#include <sstream>
#include <map>
#include <string>
#include <list>
using namespace std;
string &trans(string &s) {
for (int p = 0; p < s.size(); ++p) {
if (s[p] >= 'A' && s[p] <= 'Z')
s[p] += ('a' - 'A');
else if (s[p] == ',' || s[p] == '.')
s.erase(p, 1);
}
return s;
}
int main(int argc, char *argv[]) {
if (argc != 2) {
cerr << "请给出文件名" << endl;
return -1;
}
ifstream in(argv[1]);
if (!in) {
cerr << "无法打开输入文件" << endl;
return -1;
}
map<string, list<int>> word_lineno; // 单词到行号的映射
string line;
string word;
int lineno = 0;
while (getline(in, line)) { // 读取一行
++lineno; // 行号递增
istringstream l_in(line); // 构造字符串流，读取单词
while (l_in >> word) {
trans(word);
word_lineno[word].push_back(lineno); // 添加行号
}
}
for (const auto &w : word_lineno) { // 打印单词行号
cout << w.first << "所在行：";
for (const auto &i : w.second)
cout << i << " ";
cout << endl;
}
return 0;
}
运行程序前，在 CLion -> Run -> Edit Configurations 下配置 Program arguments 为 ../data 。
注：../data 即为文件 data 的文件名及其相对路径（是相对于可执行程序所在目录的相对路径）。
并在文件 data 中写入如下内容：
example. Cplusplus
Primer example, Example
primer
example.
Cplusplus
Primer example, Example primer
运行程序，程序执行结果如下所示：
cplusplus所在行：1 5
example所在行：1 2 2 4 6 6
primer所在行：2 3 6 6
Process finished with exit code 0
11.10
【出题思路】
理解关联容器对关键字类型的要求。
【解答】
由于有序容器要求关键字类型必须支持比较操作 <，因此
map<vector<int>::iterator, int> m1;
是可以的，因为 vector 的迭代器支持比较操作。而
map<list<int>::iterator, int> m2;
则不行，因为 list 的元素不是连续存储，其迭代器不支持比较操作。
11.11
【出题思路】
本题练习函数指针类型的定义。
【解答】
首先用 typedef 定义与 compareIsbn 相容的函数指针类型，然后用此类型声明 multiset 即可。
typedef bool (*pf)(const Sales_data &, const Sales_data &);
multiset<Sales_data, pf> bookstore(compareIsbn);
另一个参考的版本 使用关键字 using 定义：
#include "../ch07/ex7_26_sales_data.h"
#include <set>
bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs) {
return lhs.isbn() < rhs.isbn();
}
int main() {
using compareType = bool (*)(const Sales_data &lhs, const Sales_data &rhs);
// typedef bool(*compareType)(const Sales_data &lhs, const Sales_data &rhs);
std::multiset<Sales_data, compareType> bookstore(compareIsbn);
}
11.12
【出题思路】
本题练习 pair 的使用。
【解答】
#include <iostream>
#include <vector>
#include <utility>
#include <string>
using namespace std;
int main() {
vector<pair<string, int>> data; // pair 的 vector
string s;
int v;
while (cin >> s && cin >> v) // 读取一个字符串和一个整数
data.push_back(pair<string, int> (s, v));
for (const auto &d : data)
// 打印结果
cout << d.first << " " << d.second << endl;
return 0;
}
// 前两行是测试数据
// 运行结果
James 23 Jane 24 Charles 19
James 23 Jane 24 Charles 19
^D
James 23
Jane 24
Charles 19
James 23
Jane 24
Charles 19
Process finished with exit code 0
【其他解题思路】
我们还可以使用更简洁的列表初始化方式，将 while 的循环体改为
data.push_back({s, v});
即可。
还可以使用 make_pair：
data.push_back(make_pair(s, v));
11.13
【出题思路】
熟悉 pair 的不同初始化方式。
【解答】
显然，列表初始化方式最为简洁易懂。
11.14
【出题思路】
本题练习稍复杂的 pair 和关联容器的结合使用。
【解答】
在本题中，我们将家庭的姓映射到孩子信息的列表，而不是简单的孩子名的列表。因此，将在 vector 中的元素类型声明为 pair<string, string>，两个 string 分别表示孩子的名和生日。在添加孩子信息时，用列表初始化创建名和生日的 pair，添加到 vector 中即可。
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <utility>
using namespace std;
void add_family(map<string, vector<pair<string, string>>> &families,
const string &family) {
families[family];
}
void add_child(map<string, vector<pair<string, string>>> &families,
const string &family, const string &child, const string &birthday) {
families[family].push_back({child, birthday});
}
int main() {
map<string, vector<pair<string, string>>> families;
add_family(families, "张");
add_child(families, "张", "强", "1993-1-1");
add_child(families, "张", "三", "1999-1-2");
add_child(families, "王", "五", "2000-12-01");
add_family(families, "王");
for (auto f : families) {
cout << f.first << "家的孩子：";
for (auto c : f.second)
cout << c.first << "(生日" << c.second << "), ";
cout << endl;
}
return 0;
}
// 运行结果
张家的孩子：强(生日1993-1-1), 三(生日1999-1-2),
王家的孩子：五(生日2000-12-01),
Process finished with exit code 0
11.15
【出题思路】
理解关联容器的类型别名。
【解答】
mapped_type 是 vector<int>；
key_type 是 int；
value_type 是 pair<const int, vector<int>>。
11.16
【出题思路】
理解 map 的迭代器解引用的类型。
【解答】
解引用关联容器的迭代器，得到的是 value_type 的值的引用。因此对 map 而言，得到的是一个 pair 类型的引用，其 first 成员保存 const 的关键字，second 成员保存值。因此，通过迭代器只能修改值，而不能改变关键字。
#include <iostream>
#include <map>
#include <utility>
using namespace std;
int main() {
map<const int, int> m;
m[32] = 222;
map<const int, int>::iterator iter = m.begin();
iter->second = 0;
cout << iter->first << endl;
cout << iter->second;
return 0;
}
// 运行结果
32
0
Process finished with exit code 0
11.17
【出题思路】
理解容器迭代器的特点。
【解答】
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main() {
vector<string> v = {"abc", "xyz", "hhh"};
multiset<string> c = {"aag", "opq", "lll"};
copy(v.begin(), v.end(), inserter(c, c.end())); // YES。调用 insert 成员函数插入到 multiset 尾后迭代器之前
// copy(v.begin(), v.end(), back_inserter(c)); // NO。multiset 没有 push_back 成员函数，因此无法使用
// copy(c.begin(), c.end(), inserter(v, v.end())); // YES。调用 insert 成员函数插入到 vector 尾后迭代器之前
// copy(c.begin(), c.end(), back_inserter(v)); // YES。调用 push_back 成员函数插入到 vector 尾后迭代器之前
for(auto t : v) cout << t << " ";
cout << endl;
for(auto t : c) cout << t << " ";
cout << endl;
return 0;
}
11.18
【出题思路】
理解 map 的迭代器。
【解答】
map<const string, size_t>::iterator
11.19
【出题思路】
本题继续练习关联容器的迭代器。
本题与练习 11.11 相关
【解答】
typedef bool (*pf)(const Sales_data &, const Sales_data &);
multiset<Sales_data, pf> bookstore(compareIsbn);
...
multiset<Sales_data, pf>::iterator iter = bookstore.begin();
与 11.11 中链接相对应的版本：
using compareType = bool (*)(const Sales_data &lhs, const Sales_data &rhs);
std::multiset<Sales_data, compareType> bookstore(compareIsbn);
std::multiset<Sales_data, compareType>::iterator c_it = bookstore.begin();
11.20
【出题思路】
熟悉关联容器不同的插入方式。
用 insert 改写练习 11.3
【解答】
使用 insert 操作的方式是：构造一个 pair(单词, 1)，用 insert 将其插入容器，返回一个 pair。若单词已存在，则返回 pair 的 second 成员为 false，表示插入失败，程序员还需通过返回 pair 的 first 成员（迭代器）递增已有单词的计数器。判断单词是否已存在，并进行相应操作的工作完全是由程序员负责的。
使用下标操作的方式是：以单词作为下标获取元素值，若单词已存在，则提取出已有元素的值；否则，下标操作将 pair(单词, 1) 插入容器，提取出新元素的值。单词是否已存在的相关处理完全是由下标操作处理的，程序员不必关心，直接访问提取出的值就行了。
显然，对于单词计数问题来说，下标操作更简洁易读。
#include <iostream>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
string &trans(string &s) {
for (int p = 0; p < s.size(); ++p) {
if (s[p] >= 'A' && s[p] <= 'Z')
s[p] += ('a' - 'A');
else if (s[p] == ',' || s[p] == '.')
s.erase(p, 1);
}
return s;
}
int main() {
// 统计每个单词在输入中出现的次数
map<string, size_t> word_count; // string 到 size_t 的空 map
string word;
while (cin >> word) {
auto ret = word_count.insert({trans(word), 1});
if (!ret.second) // 插入失败，单词已存在
++ret.first->second; // 已有单词的计数加 1
}
for (const auto &w : word_count) // 对 map 中的每个元素
// 打印结果
cout << w.first << " occurs " << w.second
<< ((w.second > 1) ? " times" : " time") << endl;
return 0;
}
// 运行结果
example. Cplusplus Primer example, Example primer
^D
cplusplus occurs 1 time
example occurs 3 times
primer occurs 2 times
Process finished with exit code 0
11.21
【出题思路】
继续熟悉关联容器的 insert 操作。
【解答】
循环不断从标准输入读入单词（字符串），直至遇到文件结束或错误。
每读入一个单词，构造 pair {word, 0} ，通过 insert 操作插入到 word_count 中。insert 返回一个 pair，其 first 成员是一个迭代器。若单词（关键字）已存在于容器中，它（迭代器）指向已有元素；否则，它指向新插入的元素。
因此，.first 会得到这个迭代器，指向 word 对应的元素。继续使用 ->second ，可获得元素的值的引用，即单词的计数。若单词是新的，则其值为 0；若已存在，则值为之前出现的次数。对其（“0” 或 “之前出现的次数”）进行递增操作，即完成将出现次数加 1.
用这种方法，上一题可稍微简单些。
11.22
【出题思路】
继续熟悉关联容器的 insert 操作。
【解答】
map<string, vector<int>> m;
返回类型 ret = m.insert(参数类型);
参数类型是一个 pair，first 成员的类型是 map 的关键字类型 string ，second 成员的类型是 map 的值类型 vector<int> ：
pair<string, vector<int>>
返回类型也是一个 pair，first 成员的类型是 map 的迭代器，second 成员的类型是布尔型：
pair<map<string, vector<int>>::iterator, bool>
11.23
【出题思路】
本题练习允许重复关键字的关联容器的 insert 操作。
改写练习 11.7
【解答】
由于允许重复关键字，已经不需要 vector 保存同一家的孩子的名的列表，直接保存每个孩子的 (姓, 名) pair 即可。容器类型变为 multimap<string, string> 。
也不再需要 add_family 添加家庭，只保留 add_child 直接用 insert 操作添加孩子即可。
#include <iostream>
#include <map>
#include <vector>
#include <string>
using namespace std;
void add_child(multimap<string, string> &families, const string &family,
const string &child) {
families.insert({family, child});
}
int main() {
multimap<string, string> families;
add_child(families, "张", "强");
add_child(families, "张", "三");
add_child(families, "王", "五");
for (auto f : families)
cout << f.first << "家的孩子：" << f.second << endl;
return 0;
}
// 运行结果
张家的孩子：强
张家的孩子：三
王家的孩子：五
Process finished with exit code 0
11.24
【出题思路】
本题继续熟悉 map 的下标操作。
【解答】
若 m 中已有关键字 0，下标操作提取出其值，赋值语句将值置为 1。否则，下标操作会创建一个 pair (0, 0)，即关键字为 0， 值为 0（值初始化），将其插入到 m 中，然后提取其值，赋值语句将值置为 1。
11.25
【出题思路】
理解顺序容器和关联容器下标操作的不同。
【解答】
对于 m，“0” 表示 “关键字 0”。而对于 v，“0” 表示 “位置 0”。
若 v 中已有不少于一个元素，即，存在 “位置 0” 元素，则下标操作提取出此位置的元素（左值），赋值操作将其置为 1。而 map 的元素是 pair 类型，下标提取的不是元素，而是元素的第二个成员，即元素的值。
如 v 尚为空，则下标提取出的是一个非法左值（下标操作不做范围检查），向其赋值可能导致系统崩溃等严重后果。
11.26
【出题思路】
理解 map 的下标操作所涉及的各种类型。
【解答】
对 map 进行下标操作，应使用其 key_type，即关键字的类型。
而下标操作返回的类型是 mapped_type，即关键字关联的值的类型。
示例如下：
map 类型：map<string, int>
用来进行下标操作的类型：string
下标操作返回的类型：int
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
map<string, int> m{{"zhangsan", 22}, {"wangwu", 23}};
// 下标操作的类型 map<string, int>::key_type，即为 string
map<string, int>::key_type type_of_subscript = "wangwu";
// 下标运算符将会返回的类型 map<string, int>::mapped_type，即为 int
map<string, int>::mapped_type type_of_return = m[type_of_subscript];
return 0;
}
11.27
【出题思路】
理解关联容器上不同算法的区别。
【解答】
find 查找关键字在容器中出现的位置，而 count 则还会统计关键字出现的次数。
因此，当我们希望知道（允许重复关键字的）容器中有多少元素的关键字与给定关键字相同时，使用 count。
当我们只关心关键字是否在容器中时，使用 find 就足够了。特别是，对于不允许重复关键字的关联容器，find 和 count 的效果没有什么区别，使用 find 就可以了。或者，当我们需要获取具有给定关键字的元素（而不只是统计个数）时，也需要使用 find。
find 和下标操作有一个重要区别，当给定关键字不在容器中时，下标操作会插入一个具有该关键字的元素。因此，当我们想检查给定关键字是否存在时，应该用 find 而不是下标操作。
11.28
【出题思路】
理解 map 上的 find。
【解答】
find 返回一个迭代器，指向具有给定关键字的元素（若不存在则返回尾后迭代器），因此其返回类型是容器的迭代器。
// map 类型
map<string, vector<int>> m;
// 保存 find 返回结果的变量
map<string, vector<int>>::iterator iter;
11.29
【出题思路】
熟悉适合 multimap 和 multiset 的基于迭代器的关键字查找方法。
【解答】
lower_bound 和 upper_bound，这两个操作都接受一个关键字，返回一个迭代器。如果关键字在容器中，lower_bound 返回的迭代器将指向第一个具有给定关键字的元素，而 upper_bound 返回的迭代器则指向最后一个匹配给定关键字的元素之后的位置。若给定关键字不在容器中，则 lower_bound 和 upper_bound 会返回相等的迭代器 —— 都指向给定关键字的插入点，能保持容器中元素顺序的插入位置。
equal_range 函数接受一个关键字，返回一个迭代器 pair。若关键字存在，则第一个迭代器指向第一个与给定关键字匹配的元素，第二个迭代器指向最后一个匹配元素之后的位置。若未找到匹配的元素，则两个迭代器都指向关键字可以插入的位置。此 pair 的 first 成员保存的迭代器（第一个迭代器）与 lower_bound 返回的迭代器是一样的，second 成员保存的迭代器（第二个迭代器）与 upper_bound 的返回的迭代器是一样的。
11.30
【出题思路】
熟悉 equal_range 的使用。
【解答】
equal_range 返回一个迭代器 pair，其 first 成员与 lower_bound 的返回的迭代器相同，即指向容器中第一个具有给定关键字的元素。因此，对其解引用会得到一个 value_type 对象，即一个 pair，其 first 为元素的关键字，即给定关键字，而 second 为关键字关联的值。在本例中，关键字为作者，关联的值为著作的题目。因此 pos.first->second 即获得给定作者的第一部著作的题目。
11.31
【出题思路】
练习 multimap，需使用 insert 操作。
在 multimap 中查找具有给定关键字的元素，有几种方法：使用 find 只能查找第一个具有给定关键字的元素，要找到所有具有给定关键字的元素，需编写循环（如书 例子所示）；lower_bound 和 upper_bound 配合使用，可找到具有给定关键字的元素的范围；equal_range 最为简单，一次即可获得要查找的元素范围。
将找到的范围传递给 erase，即可删除指定作者的所有著作。
为了解决元素不在 multimap 中的情况，首先检查 equal_range 返回的两个迭代器，若相等（空范围），则什么也不做。范围不为空时，才将迭代器传递给 erase，删除所有元素。
#include <iostream>
#include <string>
#include <map>
using namespace std;
void remove_author(multimap<string, string> &books, const string &author) {
auto pos = books.equal_range(author); // 要查找的作者
if (pos.first == pos.second)
cout << "没有" << author << "这个作者" << endl;
else
books.erase(pos.first, pos.second); // 删除该作者及其所有作品
}
void print_books(multimap<string, string> &books) {
cout << "当前书目包括：" << endl;
for (auto &book : books) // 打印作者及其书目
cout << book.first << "：《" << book.second << "》" << endl;
}
int main() {
multimap<string, string> books;
books.insert({"Barth, John", "Sot-Weed Factor"});
books.insert({"Barth, John", "Lost in the Funhouse"});
books.insert({"金庸", "笑傲江湖"});
books.insert({"金庸", "天龙八部"});
books.insert({"金庸", "射雕英雄传"});
print_books(books);
remove_author(books, "张三");
remove_author(books, "Barth, John");
print_books(books);
return 0;
}
// 运行结果
当前书目包括：
Barth, John：《Sot-Weed Factor》
Barth, John：《Lost in the Funhouse》
金庸：《笑傲江湖》
金庸：《天龙八部》
金庸：《射雕英雄传》
没有张三这个作者
当前书目包括：
金庸：《笑傲江湖》
金庸：《天龙八部》
金庸：《射雕英雄传》
Process finished with exit code 0
【其他解题思路】
使用 find 或 lower_bound 和 upper_bound，也可实现本题目标，但复杂一些。
11.32
【出题思路】
本题要求理解 multimap 数据结构中关键字的顺序，以及利用它来实现关键字的有序输出。
【解答】
multimap 的数据结构是红黑树，它维护了元素的关键字的默认序。例如，对字符串关键字（作者），红黑树会维护它们的字典序。当我们遍历 multimap（如遍历 [begin(), end()) ，或更简单地使用范围 for 循环）时，就是按关键字的字典序来访问元素。
因此，上一题的 print_books 实际上已经实现了按字典序打印作者（作品没有实现字典序）。
但是，当我们要求的不是关键字的默认序（运算符 < 定义的顺序）时，就要复杂一些。由于 sort 算法要求给定的两个迭代器是随机访问迭代器，关联容器的迭代器不符合这一要求，所以不能直接对其使用 sort 算法。其实这不难理解，关联容器的根本特征就是维护了关键字的默认序，从而实现了按关键字的插入、删除和查找。是不可能通过 sort 使其内部元素呈现出另外一种顺序的。只有本身不关心元素的顺序容器，才可能随意安排元素顺序（位置）。我们可以在定义 multimap 时使用自己定义的比较操作来定义关键字的序，而不是使用 < 定于的序，但这只是令 multimap 以另外一种序来维护关键字，仍然不可能在使用 multimap 的过程中来改变关键字的顺序。为此，我们只能将 multimap 中的元素拷贝到一个顺序容器（如 vector）中，对顺序容器执行 sort 算法，来获取关键字的其他序。
下面是我参考网上的代码（该代码实现了关键字和关键字关联的值都字典有序输出。本质还是利用了关联容器的关键字的默认序 —— 字典序），对代码做的简单注释和运行结果：
#include <map>
#include <set>
#include <string>
#include <iostream>
using std::string;
int main()
{
std::multimap<string, string> authors{
{"alan", "DMA"}, {"pezy", "LeetCode"}, {"alan", "CLRS"},
{"wang", "FTP"}, {"pezy", "CP5"}, {"wang", "CPP-Concurrency"}};
/*
* multimap 默认是按关键字字典序访问元素，所以输出
* 也是关键字字典序；关键字关联的值无法保证有序
*/
for (const auto &author : authors)
std::cout << author.first << ": " << author.second << std::endl;
std::cout << std::endl;
/*
* 创建 map，实现作者和作品的映射
* key_type 类型为 string
* mapped_type 类型为 multiset<string>
* map 和 multiset 的关键字是有序的
* 这样就可以实现作者和著作都有序输出了
*/
std::map<string, std::multiset<string>> m;
// 将 authors 中的作者及其著作都插入到 m 中
for (const auto& author : authors)
m[author.first].insert(author.second);
// 遍历 m，实现作者有序，作者著作也有序
// 当然这里的有序指的是字典序
for (const auto& s : m) {
std::cout << s.first << ": ";
for (const auto& b : s.second)
std::cout << b << " ";
std::cout << std::endl;
}
return 0;
}
// 运行结果
alan: DMA
alan: CLRS
pezy: LeetCode
pezy: CP5
wang: FTP
wang: CPP-Concurrency
alan: CLRS DMA
pezy: CP5 LeetCode
wang: CPP-Concurrency FTP
Process finished with exit code 0
11.33
【出题思路】
关联容器的综合练习。
【解答】
本书配套网站（C++ Primer, 5th Edition Source Downloads）提供了书中的全部源代码，其中就有单词转换程序。尝试编译、运行它即可。
综合本小节内容、理解此程序，若仍有不能理解，可利用集成开发环境跟踪功能跟踪程序运行，观察变量值的变化，来帮助你理解程序。
下面是我运行书籍配套代码的结果：
/*
* This file contains code from "C++ Primer, Fifth Edition", by Stanley B.
* Lippman, Josee Lajoie, and Barbara E. Moo, and is covered under the
* copyright and warranty notices given in that book:
*
* "Copyright (c) 2013 by Objectwrite, Inc., Josee Lajoie, and Barbara E. Moo."
*
*
* "The authors and publisher have taken care in the preparation of this book,
* but make no expressed or implied warranty of any kind and assume no
* responsibility for errors or omissions. No liability is assumed for
* incidental or consequential damages in connection with or arising out of the
* use of the information or programs contained herein."
*
* Permission is granted for this code to be used for educational purposes in
* association with the book, given proper citation if and when posted or
* reproduced.Any commercial use of this code requires the explicit written
* permission of the publisher, Addison-Wesley Professional, a division of
* Pearson Education, Inc. Send your request for permission, stating clearly
* what code you would like to use, and in what specific way, to the following
* address:
*
* Pearson Education, Inc.
* Rights and Permissions Department
* One Lake Street
* Upper Saddle River, NJ 07458
* Fax: (201) 236-3290
*/
#include <map>
#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include <stdexcept>
#include <sstream>
using std::map; using std::string; using std::vector;
using std::ifstream; using std::cout; using std::endl;
using std::getline;
using std::runtime_error; using std::istringstream;
map<string, string> buildMap(ifstream &map_file)
{
map<string, string> trans_map; // holds the transformations
string key; // a word to transform
string value; // phrase to use instead
// read the first word into key and the rest of the line into value
while (map_file >> key && getline(map_file, value))
if (value.size() > 1) // check that there is a transformation
trans_map[key] = value.substr(1); // skip leading space
else
throw runtime_error("no rule for " + key);
return trans_map;
}
const string &
transform(const string &s, const map<string, string> &m)
{
// the actual map work; this part is the heart of the program
map<string, string>::const_iterator map_it = m.find(s);
// if this word is in the transformation map
if (map_it != m.end())
return map_it->second; // use the replacement word
else
return s; // otherwise return the original unchanged
}
// first argument is the transformations file;
// second is file to transform
void word_transform(ifstream &map_file, ifstream &input)
{
map<string, string> trans_map =
buildMap(map_file); // store the transformations
// for debugging purposes print the map after its built
cout << "Here is our transformation map: \n\n";
for (map<string, string>::const_iterator entry = trans_map.begin();
entry != trans_map.end(); ++entry)
cout << "key: " << entry->first
<< "\tvalue: " << entry->second << endl;
cout << "\n\n";
// do the transformation of the given text
string text; // hold each line from the input
while (getline(input, text)) { // read a line of input
istringstream stream(text); // read each word
string word;
bool firstword = true; // controls whether a space is printed
while (stream >> word) {
if (firstword)
firstword = false;
else
cout << " "; // print a space between words
// transform returns its first argument or its transformation
cout << transform(word, trans_map); // print the output
}
cout << endl; // done with this line of input
}
}
int main(int argc, char **argv)
{
// open and check both files
if (argc != 3)
throw runtime_error("wrong number of arguments");
ifstream map_file(argv[1]); // open transformation file
if (!map_file) // check that open succeeded
throw runtime_error("no transformation file");
ifstream input(argv[2]); // open file of text to transform
if (!input) // check that open succeeded
throw runtime_error("no input file");
word_transform(map_file, input);
return 0; // exiting main will automatically close the files
}
运行程序前，在 CLion -> Run -> Edit Configurations 下配置 Program arguments 为 ../map_file ../input 。
注：../map_file ../input 即为 map_file 和 input 文件的文件名及其相对路径（是相对于可执行程序所在目录的相对路径）。
并在文件 map_file 中写入如下内容（转换规则）：
brb be right back
k okay?
y why
r are
u you
pic picture
thk thanks!
18r later
input 文件中写入测试数据（待转换的数据）：
where r u
y dont u send me a pic
k thk 18r
运行程序，程序执行结果如下所示：
// 运行结果
Here is our transformation map:
key: 18r value: later
key: brb value: be right back
key: k value: okay?
key: pic value: picture
key: r value: are
key: thk value: thanks!
key: u value: you
key: y value: why
where are you
why dont you send me a picture
okay? thanks! later
Process finished with exit code 0
11.34
【出题思路】
继续理解 find 和下标操作的区别。
【解答】
如前所述，find 仅查找给定关键字在容器中是否出现，若容器中不存在给定关键字，它返回尾后迭代器。当关键字存在时，下标运算符的行为和 find 类似，但当关键字不存在时，下标运算符会构造一个 pair（进行值初始化），将其插入到容器中。对于单词转换程序，若将 find 替换为下标运算符，若给定关键字 s 不在 m 中，下标运算符会试图构建新 pair 插入到 m 中，但由于 m 被限定为 const，如无法插入，程序报错。而且构建新的 pair 的到 m 中，也不符合我们的预期。
transform(const string &s, const map<string, string> &m) {
... ...
}
11.35
【出题思路】
继续理解 insert 操作和下标操作的区别。
【解答】
当 map 中没有给定关键字时，insert 操作与下标操作+赋值操作的效果类似，都是将关键字和值的 pair 添加到 map 中。
但当 map 中已有给定关键字，也就是新的转换规则与一条已有规则要转换同一个单词（关键字）时，两者的行为是不同的。下标操作会获得具有该关键字的元素（也就是已有规则）的值，并将新读入的值赋予它，也就是用新读入的规则覆盖了容器中的已有规则。但 insert 操作遇到关键字已存在的情况，则不会改变容器内容，而是返回一个值指出插入失败。因此，当规则文件（map_file）中存在多条规则转换相同单词时，下标+赋值的版本最终会用最后一条规则进行文本转换，而 insert 版本则会用第一条规则进行文本转换。
11.36
【出题思路】
本题练习字符串处理的技巧。
【解答】
此题有误，书中程序已经处理了这种情况。
在 buildMap 函数中，当循环中读入要转换的单词和转换的内容后，会检查是否存在转换的内容（value.size() > 1），若不存在，则抛出一个异常。
当然，程序只处理这一种错误。你可以思考还有哪些错误，编写程序完成处理。
11.37
【出题思路】
理解无序关联容器和有序版本的差异。
【解答】
无须版本通常性能更好，使用也更为简单。有序版本的优势是维护了关键字的序。
当元素的关键字类型没有明显的序的关系，或是维护元素的代价非常高时，无序容器非常有用。
但当应用要求必须维护元素的序时，有序版本就是唯一的选择。
11.38
【出题思路】
本题练习使用无序关联容器。
【解答】
对单词计数程序（练习 11.3/11.4）仅有的两处修改是将包含的头文件 map 改为 unordered_map，以及将 word_count 类型由 map 改为 unordered_map。
尝试编译、运行此程序，你会发现，由于无序容器不维护元素的序，程序的输出结果与练习 11.3/11.4 输出结果的顺序是不同的。
#include <iostream>
#include <unordered_map>
#include <string>
#include <algorithm>
using namespace std;
string &trans(string &s) {
for (int p = 0; p < s.size(); ++p) {
if (s[p] >= 'A' && s[p] <= 'Z')
s[p] += ('a' - 'A');
else if (s[p] == ',' || s[p] == '.')
s.erase(p, 1);
}
return s;
}
int main() {
// 统计每个单词在输入中出现的次数
unordered_map<string, size_t> word_count; // string 到 size_t 的空 map
string word;
while (cin >> word)
++word_count[trans(word)]; // 提取 word 的计数器并将其加 1
for (const auto &w : word_count) // 对 map 中的每个元素
// 打印结果
cout << w.first << " occurs " << w.second
<< ((w.second > 1) ? " times" : " time") << endl;
return 0;
}
// 运行结果
example. Cplusplus Primer example, Example primer
^D
primer occurs 2 times
cplusplus occurs 1 time
example occurs 3 times
Process finished with exit code 0
单词转换程序的修改类似。程序如下所示：
/*
* This file contains code from "C++ Primer, Fifth Edition", by Stanley B.
* Lippman, Josee Lajoie, and Barbara E. Moo, and is covered under the
* copyright and warranty notices given in that book:
*
* "Copyright (c) 2013 by Objectwrite, Inc., Josee Lajoie, and Barbara E. Moo."
*
*
* "The authors and publisher have taken care in the preparation of this book,
* but make no expressed or implied warranty of any kind and assume no
* responsibility for errors or omissions. No liability is assumed for
* incidental or consequential damages in connection with or arising out of the
* use of the information or programs contained herein."
*
* Permission is granted for this code to be used for educational purposes in
* association with the book, given proper citation if and when posted or
* reproduced.Any commercial use of this code requires the explicit written
* permission of the publisher, Addison-Wesley Professional, a division of
* Pearson Education, Inc. Send your request for permission, stating clearly
* what code you would like to use, and in what specific way, to the following
* address:
*
* Pearson Education, Inc.
* Rights and Permissions Department
* One Lake Street
* Upper Saddle River, NJ 07458
* Fax: (201) 236-3290
*/
#include <unordered_map>
#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include <stdexcept>
#include <sstream>
using std::unordered_map; using std::string; using std::vector;
using std::ifstream; using std::cout; using std::endl;
using std::getline;
using std::runtime_error; using std::istringstream;
unordered_map<string, string> buildMap(ifstream &map_file)
{
unordered_map<string, string> trans_map; // holds the transformations
string key; // a word to transform
string value; // phrase to use instead
// read the first word into key and the rest of the line into value
while (map_file >> key && getline(map_file, value))
if (value.size() > 1) // check that there is a transformation
trans_map[key] = value.substr(1); // skip leading space
else
throw runtime_error("no rule for " + key);
return trans_map;
}
const string &
transform(const string &s, const unordered_map<string, string> &m)
{
// the actual unordered_map work; this part is the heart of the program
// 桶迭代器和容器迭代器是两个不同的概念，不要混淆
// const_local_iterator 和 local_iterator 是桶迭代器
// 而这里的 const_iterator 是无序容器 unordered_map 的迭代器
unordered_map<string, string>::const_iterator map_it = m.find(s);
// if this word is in the transformation unordered_map
if (map_it != m.end())
return map_it->second; // use the replacement word
else
return s; // otherwise return the original unchanged
}
// first argument is the transformations file;
// second is file to transform
void word_transform(ifstream &map_file, ifstream &input)
{
unordered_map<string, string> trans_map =
buildMap(map_file); // store the transformations
// for debugging purposes print the unordered_map after its built
cout << "Here is our transformation unordered_map: \n\n";
for (unordered_map<string, string>::const_iterator entry = trans_map.begin();
entry != trans_map.end(); ++entry)
cout << "key: " << entry->first
<< "\tvalue: " << entry->second << endl;
cout << "\n\n";
// do the transformation of the given text
string text; // hold each line from the input
while (getline(input, text)) { // read a line of input
istringstream stream(text); // read each word
string word;
bool firstword = true; // controls whether a space is printed
while (stream >> word) {
if (firstword)
firstword = false;
else
cout << " "; // print a space between words
// transform returns its first argument or its transformation
cout << transform(word, trans_map); // print the output
}
cout << endl; // done with this line of input
}
}
int main(int argc, char **argv)
{
// open and check both files
if (argc != 3)
throw runtime_error("wrong number of arguments");
ifstream map_file(argv[1]); // open transformation file
if (!map_file) // check that open succeeded
throw runtime_error("no transformation file");
ifstream input(argv[2]); // open file of text to transform
if (!input) // check that open succeeded
throw runtime_error("no input file");
word_transform(map_file, input);
return 0; // exiting main will automatically close the files
}
运行程序前，在 CLion -> Run -> Edit Configurations 下配置 Program arguments 为 ../map_file ../input 。
注：../map_file ../input 即为 map_file 和 input 文件的文件名及其相对路径（是相对于可执行程序所在目录的相对路径）。
并在文件 map_file 中写入如下内容（转换规则）：
brb be right back
k okay?
y why
r are
u you
pic picture
thk thanks!
18r later
input 文件中写入测试数据（待转换的数据）：
where r u
y dont u send me a pic
k thk 18r
注：map_file 和 input 文件内容与练习 11.33 相同。
运行程序，程序执行结果如下所示（可与练习 11.33 比较函数 builtMap 返回的 trans_map 的输出结果）：
// 运行结果
Here is our transformation unordered_map:
key: 18r value: later
key: u value: you
key: r value: are
key: brb value: be right back
key: y value: why
key: thk value: thanks!
key: pic value: picture
key: k value: okay?
where are you
why dont you send me a picture
okay? thanks! later
Process finished with exit code 0
评论区