通过例子学习现代C++ ：7 关联容器和文件

大家好，欢迎来到IT知识分享网。

本章涵盖

• 填充和使用关联容器
• 对和元组
• 从文件中读取
• 随机样本

我们已经多次使用了向量，但还没有使用过关联容器。关联容器保存键值对，为我们提供查找表或字典。在本章中，我们将使用字典来创建一个答案撞击游戏。我们将提供两个线索，每个线索都是一个单词的定义。第一个单词的结尾将与下一个单词的开头重叠，从而给出答案。例如，向量是“支持动态调整大小的顺序容器”，而火炬可以定义为“手中携带的点燃的棍子”，因此将单词向量和火炬结合在一起就得到了答案 vectorch。

我们将首先在 map 头文件中定义的 std::map 中存储一个字典，该头文件在 C++11 之前就已存在，然后再考虑其他类型的关联容器。我们将在下一章中使用更新的 std::unordered_map ，因此在本章中使用 std::map 将是一个有用的复习，我们将在此过程中了解 std::pair 和更一般的 std::tuple 。我们将从硬编码字典开始，然后使用随机样本从文件中读取数据，以在玩游戏时创造多样性。

7.1 硬编码答案激活成功教程

我们将首先硬编码单词和定义。我们可以将这些直接放入字典或 map 中。一个 map 允许我们将值存储在键下。如果一个键已经存在，我们可以替换现有条目，但我们不能有两个具有相同键的条目。现在，一个语言字典可以对同一个单词有多个定义，因此当我们使用一个合适的字典时，我们需要一个允许每个键有多个值的数据结构。我们将从每个单词一个定义开始，但 map 头部也提供了一个 multimap ，它确实支持多个条目，因此我们可以稍后有多个定义。让我们从老式的 std::map 开始，每个键使用一个值。

7.1.1 创建和使用 std::map

与所有容器一样， map 是一个类模板，因此我们需要声明键和值的类型。两者都是字符串，因此我们需要一个 map 的 string s 来 string s：

std::map<std::string, std::string> dictionary;

我们可以使用 operator[] 来查询和插入键值对。要添加或覆盖一个条目，我们说

dictionary["assume"] = "take for granted, take to be the case";

我们在 dictionary 中有一个项目，键为 “assume” ，值为 “take for granted, take to be the case” 。我们可以使用相同的运算符查找字符串；例如：

std::string new_value = dictionary["fictional"]; 

当我们这样做时， new_value 是一个默认字符串，因为 “fictional” 不在字典中。在对 operator[] 的调用之后，新的键 “fictional” 和默认的 string 值最终出现在字典中，这可能不是我们的意图。让我们做一个 map 并证明这一点。

我们将创建一个 map 的 string 键到 string 值，并将内容流式传输到 std::cout ，因此我们需要包含 map 、 string 和 iostream 头部 . 当我们流式传输一个 vector 时，我们使用了基于范围的 for 循环，类似于

for(auto item: my_vector)

我们可以对一个 map 做同样的事情，并且我们将使用一个 const 引用来避免复制。每个 map 项目由两个字符串捆绑在一起作为一个 std::pair ，它具有一个 first 和 second 方法来访问每个元素。我们稍后会更详细地看一下这个。目前，我们可以尝试查询一个 map 以获取一个不存在的元素，看看会发生什么。

清单 7.1 创建和显示一个 map

#include <iostream> #include <map> #include <string> void warm_up() { std::map<std::string, std::string> dictionary; ❶ dictionary["assume"] = "take for granted, take to be the case"; ❷ std::string new_value = dictionary["fictional"]; ❸ for (const auto & item : dictionary) ❹ { std::cout << item.first << " : " << item.second << '\n'; ❺ } } int main() { warm_up(); }

❶ 声明字典

❷ 添加一个项目

查询不存在的项目

❹ const auto & 以避免复制

❺ 显示配对

当我们运行这段代码时，我们可以看到 “fictional” 的查询已将一个空字符串添加到字典中：

assume : take for granted, take to be the case fictional :

这种行为不直观，可能会导致问题。我们故意在将容器作为参数传递给函数时使用了 const 引用。我们希望使用引用，因此不复制整个容器，但我们通常只想查询而不是更改元素，因此将参数标记为 const 。如果我们尝试对 map 做同样的事情。

void unexpected(const std::map<std::string, std::string> & lookup) { auto value = lookup["cheese"]; }

我们遇到了编译错误，提示我们没有 operator[] 来接受 const 映射。相反，我们可以调用 at 方法，这是一个 const 成员函数：

auto value = lookup.at("cheese");

如果键不存在，将抛出一个 std::out_of_range 异常。使用这种替代方法允许我们通过 const 引用传递一个 map ，这将非常有用。

operator[] 还将替换现有条目，因为 map 每个键只有一个值。如果我们说

dictionary["fictional"] = "made up";

虚构条目的值为 “made up” 。如果我们改用 insert 方法，则可以避免覆盖现有条目。 insert 有多种重载（请参见 http://mng.bz/5oEq），但最简单的版本返回两个东西，一个迭代器和一个 bool ，也作为 std::pair 打包。当我们尝试插入新项时，可以传递一个初始化列表作为键和值：

auto result = dictionary.insert({ "insert", "place inside" });

result 的第二个项目是正确的，因为新条目已被添加。第一个项目持有对新添加项目的迭代器。如果我们尝试覆盖现有项目

auto next_result = dictionary.insert({ "fictional", "not factual" });

next_result 的第二个项是假的，第一个项持有对现有项的迭代器，这使我们能够看到现有的值。

我们现在可以制作一个字典，这是一个有用的开始。在构建我们的答案击碎游戏之前，让我们暂停一下，考虑一下 std::pair ，它已经出现了几次，稍微详细一点。

7.1.2 对偶、元组和结构化绑定

std::pair 生活在 utility 头部，并由一个类 template 定义，基于两种类型：

template<typename T1, typename T2> struct pair;

我们已经使用了成员变量 first 和 second 。 utility 头文件还提供了一个辅助函数，称为 make_pair ，它创建我们想要的对并为我们推导类型。如果我们说

auto two_words = std::make_pair("Hello,", "world!");

我们得到一对 const char *s 。我们可以使用字符串字面量 operator “”s 来获得一对 std::string 。

using namespace std::string_literals; auto two_words = std::make_pair("Hello,"s, "world!"s);

与其使用 auto ，我们可以说 std::pair 并使用初始化列表：

std::pair two_words{"Hello,"s, "world!"s};

我们不需要明确说明这对项目的类型，因为 CTAD 会为每个项目推导出一个 std::string 。类型不需要相同，因此如果我们愿意，可以有一对两种不同类型的项目。例如

std::pair two_numbers{1, 1.23};

是 std::pair 持有一个 int 和一个 double 。

现在，一对包含两个元素，但 C++11 引入了一种称为 tuple 的泛化，可以容纳任意数量的项。没有人一致同意如何发音 tuple，因此可以选择“two-pel”、“tupp-ell”或“chewple”中的一个。 tuple 位于 tuple 头文件中，并使用我们之前遇到的参数包（三个点）进行定义：

template<typename... Types> class tuple;

有一个 make_tuple 函数可以创建元组，因此我们可以像这样创建一个包含三个字符串的元组：

auto three_words = std::make_tuple("Hello "s, "again, "s, "World!"s); 

然而，我们也可以说

std::tuple three_words = {"Hello "s, "again, "s, "World!"s};

和 CTAD 将启动，推断我们有一个包含三个 std::string 的元组。与 std::pair 一样，我们可以在元组中拥有各种类型，所以下面继续。

std::tuple three_numbers{ 1, 1.23, 4.5f };

是一个 std::tuple 的 int ， double 和 float 。

现在， std::pair 有 first 和 second 成员来访问任一元素，但 std::tuple 可能不包含两个元素。我们在第 5 章中使用了 variant ，当时我们有一张卡片或一个小丑，并使用 std::get 来访问这些元素。 tuple 头有一个重载的 std::get ，我们可以用它来检索一个 tuple 元素，指定我们想要的项目的索引。例如，调用

auto first = std::get<0>(three_words);

将返回第一个字符串。

在列表 7.1 中，我们在显示字典时使用了一个 std::pair ，隐藏在 auto 后面。

for (const auto & item : dictionary) 

item 实际上是一对字符串，因此我们需要调用 first 和 second 来显示字典条目。我们可以做得更整洁。C++17 引入了结构化绑定，允许我们将名称绑定到对、元组等（请参见 http://mng.bz/g7De）。如果我们想要我们的三个数字

std::tuple three_numbers{ 1, 1.23, 4.5f };

解包到三个变量中，我们可以自己获取每个元素：

int x = std::get<0>(three_numbers); double y = std::get<1>(three_numbers); float z = std::get<2>(three_numbers);

结构绑定允许我们在一行中获取所有三个项目：

auto [x, y, z] = three_numbers;

我们必须使用 auto ，后面跟着我们想要的变量名 [] 。实际上，结构化绑定是手动解包的语法糖，但它会复制一个隐藏的元组或对。使用 C++ Insights（请参见
https://cppinsights.io/s/0579bdbb）来查看我们的三个数字，我们看到一个 tuple 的副本，带有一个虚构的名称 __three_numbers6 和三个命名变量，分别引用这三个元素：

std::tuple<int, double, float> three_numbers = std::tuple<int, double, float>{1, 1.23, 4.5F}; std::tuple<int, double, float> __three_numbers6 = std::tuple<int, double, float>(three_numbers); int && x = std::get<0UL>(static_cast<std::tuple<int, double, float> &&>(__three_numbers6)); double && y = std::get<1UL>(static_cast<std::tuple<int, double, float> &&>(__three_numbers6)); float && z = std::get<2UL>(static_cast<std::tuple<int, double, float> &&>(__three_numbers6));

我们在第二章中见过 rvalue 引用 && 。如果我们使用引用而不是复制，我们可以避免复制：

auto &[x, y, z] = three_numbers;

隐藏的 __three_numbers6 然后成为一个引用，为我们提供每个数字的引用，因为 && 受到引用折叠的影响，因此它愉快地绑定到引用上。

我们可以绑定到数组，甚至结构的非静态成员。例如，给定

struct DataObject { int x{ 0 }; double y{ 1.23 }; };

我们可以写

DataObject data {}; auto [x, y] = data;

在每种情况下，我们使用 auto 并绑定到现有对象。该书的技术编辑 Tim van Deurzen 在 2019 年的 Meeting C++上做了一个关于结构化绑定的精彩闪电演讲，如果你想了解更多（请参见
https://www.youtube.com/watch?v=YC_TMAbHyQU）。

我们在考虑如何使用 std::pair 来显示列表 7.1 中的 dictionary 。我们现在可以将 dictionary 的键值对绑定到两个名称，写作

for (const auto & [key, value] : dictionary)

因此我们可以直接使用 key 和 value ，而无需在该对上调用 first 和 second 。

清单 7.2 使用结构绑定访问 map 项目

#include <iostream> #include <map> #include <string> void structure_bindings() { std::map<std::string, std::string> dictionary; dictionary["assume"] = "presume, take for granted"; std::string new_word = dictionary["fictional"]; for (const auto & [key, value] : dictionary) ❶ { std::cout << key << " : " << value << '\n'; ❷ } }

❶ 将结构绑定到键和值

❷ 显示键和值

同样，如果我们使用 insert ，我们可以使用结构化绑定来保存结果：

auto [it, result] = dictionary.insert({ "insert", "place inside" })

我们可以直接使用迭代器 it 和布尔值 result ，而不是使用 first 来获取迭代器和 second 来获取 result 。

pair 和 tuple 可以在多种情况下使用，包括从函数返回多个值，正如我们在考虑 map 的 insert 函数时所看到的。结构化绑定还使我们在使用返回值时能够编写更清晰的代码。掌握了 map 和 pair 的基础知识后，我们现在可以制作一个简单的答案击碎游戏。

7.1.3 一个简单的回答击碎游戏

我们将创建两个字典来进行答案撞击游戏。第一个字典将包含 C++关键字和类型及其定义，以便我们在游戏时可以稍作复习。第二个字典将包含英语单词及其定义。我们可以使用 operator[] 来制作关键字字典。

列表 7.3 使用 operator [] 填充 map

std::map<std::string, std::string> keywords; ❶ keywords["char"] = "type for character representation which can be" " most efficiently processed on the target system"; ❷ keywords["class"] = "user defined type with private members by default"; keywords["struct"] = "user defined type with public members by default"; keywords["vector"] = "sequential container supporting dynamic resizing"; keywords["template"] = "family of classes or functions parameterized" " by one or more parameters";

构建字典

填充字典

要使用 operator[] ，我们需要一个可变的而不是 const map ，但一旦我们设置了字典，就不需要更改它们。现在，我们注意到可以为键和值传递一个初始化列表给 insert ：

dictionary.insert({ "insert", "place inside" });

同样，我们可以使用一对对的初始化列表，甚至是由两个字符串组成的初始化列表的初始化列表来构建我们的字典。

清单 7.4 使用初始化列表填充 map

const std::map<std::string, std::string> dictionary{ ❶ {"assume", "take for granted, take to be the case"}, ❷ {"harsh", "coarse, large-grained or rough to the touch"}, {"table", "piece of furniture"}, {"tease", "mock, make fun of"}, {"torch", "lit stick carried in one's hand"}, };

构建字典

❷ 用成对的初始化列表填充它

第二种方法意味着我们可以将字典标记为 const ，以确保我们不会意外更改其内容。

我们可以遍历关键字，使用结构化绑定将键和值通过 const 引用，以避免复制字符串：

for (const auto & [word, definition] : keywords)

对于每个关键词，我们需要一个与之重叠的字典中的单词，这样我们就可以将关键词和字典单词结合在一起。给定单词 “char” ，我们可以在字典中寻找以 “char” 开头的单词，但整个单词可能会被吞掉而不是重叠。这没关系，但避免这种情况可能会更有趣。相反，我们可以尝试寻找以 “har” 开头的单词。因此，我们需要从第二个字符开始的子字符串，或索引 1 ，并制作一个词干或单词的开头进行查找：

size_t offset = 1; auto stem = word.substr(offset);

我们可以通过字典查找以该词干开头的单词。我们需要检查一个键的子字符串，从索引 0 开始，长度为 stem.size() ，是否等于词干 “har” ，因此我们将在字典中找到 “harsh” 。在最坏的情况下，这确实意味着我们将逐个检查每个键，可能找不到单词。我们将很快看到一种更有效的方法来查找 map 中的键。

如果没有与词干 “har” 匹配的内容，我们可以从下一个字母开始重新尝试，因此我们使用 “ar” 。恰好有一个与 “har” 匹配的词，所以我们有一个合适的单词，不需要进一步检查。一些单词，如 “struct” ，需要更多的搜索。我们去掉初始的 ‘s’ ，并搜索词干 “truct” 。然而，字典中没有以 “truct” 开头的词，因此我们可以尝试 “ruct” ，并继续尝试，直到我们尝试匹配单个字母 “t” 。我们需要至少一个重叠字母才能将两个单词合并在一起。有些单词可能根本没有匹配，因此我们可以用空字符串来表示这一点。我们可以返回一个 optional ，或者甚至一个 tuple ，用布尔值表示我们找不到合适的单词，但空字符串也可以。尝试这些不同的方法以获得额外的练习。

将搜索写入一个单独的函数意味着我们可以对其进行测试。我们可以将该函数放在一个新的源文件中，称为 Smash.cpp ，并使用命名空间以及头文件 Smash.h 来声明我们需要的函数。搜索函数接受我们想要匹配的单词和一个要搜索的字典。如果找到一个单词，我们需要从字典中返回一个键，否则返回一个空字符串。如果我们也返回使用的偏移量，调用代码可以将两个单词合并在一起，而不必重新发现重叠的位置。正如我们所看到的，从函数返回两个值的一个简单方法是通过 std::pair ，因此我们可以在这里这样做，将代码放在 Smash.cpp 中，并在相应的头文件中声明该函数。

清单 7.5 查找重叠单词

#include <map> #include <string> #include <utility> #include "Smash.h" std::pair<std::string, int> find_overlapping_word(std::string word, const std::map<std::string, std::string>& dictionary) { size_t offset = 1; ❶ while (offset < word.size()) { auto stem = word.substr(offset); for (const auto & [k, v] : dictionary) ❷ { ❷ auto key_stem = k.substr(0, stem.size()); ❷ if (key_stem == stem) ❸ { ❸ return { k, offset }; ❸ } } ++offset; ❹ } ❹ return { "", -1 }; ❹ }

从单词的第二个字母开始

❷ 考虑每个键的开始

找到匹配项

❹ 未找到匹配项

尽管我们可能会检查所有的键，但重叠函数对于首次尝试答案碰撞来说已经足够好。我们需要一个函数，接受两个字典，一个是关键词字典，另一个是更一般的单词字典，两个字典都有定义作为线索。对于每个关键词，我们将尝试找到一个重叠的单词，如果找到一个单词，我们将显示两个定义作为线索。如果没有找到，我们将返回一个空字符串和偏移量 -1 ，因此我们将继续下一个关键词。如果找到一个合适的单词，正确答案是关键词的开头与第二个单词连接在一起。我们可以使用 operator+: 来创建答案。

word.substr(0, offset) + second_word

现在，子字符串创建了一个临时字符串，而连接操作又创建了另一个字符串，因此这种方法效率不高。我们不需要复制子字符串。C++17 在 string_view 头文件中引入了 string_view ，它提供了一个视图而不是字符串的副本。 std::string_view 使我们可以只读访问现有字符串，这意味着现有字符串需要保持在作用域内，以便视图有效。我们可以获取第一个单词的第一部分的视图，避免复制，并使用 std::format ，我们在第二章中看到过，以得出答案。因此我们可以说

std::string answer = std::format("{}{}", std::string_view(word).substr(0, offset), second_word);

并避免子字符串的临时副本。有关更多详细信息，请参见 http://mng.bz/amzj。使用 string_view 通常更有效，但由于它是另一个对象的视图，我们需要小心在原始字符串超出范围后不要使用该视图。为了简单起见，我们在这个例子中将坚持使用 operator+ 。值得注意的是，我们正在制作一个额外的副本，而实际上并不需要这样做。

我们可以使用 std::getline 来读取猜测。玩家可以简单地按下回车键放弃。我们可以将响应与答案进行比较，以确定猜测是否正确，再次将代码放入 Smash.cpp 并在 Smash.h 中声明函数。

清单 7.6 一个简单的答案破坏游戏

#include <iostream> #include <map> #include <string> #include "Smash.h" void simple_answer_smash( const std::map<std::string, std::string> &keywords, const std::map<std::string, std::string> &dictionary) { for (const auto & [word, definition] : keywords) ❶ { auto [second_word, offset] = find_overlapping_word(word, dictionary); ❷ if (offset == -1) ❸ { ❸ std::cout << "Not match for " << word << '\n'; ❸ continue; ❸ } std::string second_definition = dictionary.at(second_word); ❹ std::cout << definition << "\nAND\n" << second_definition << '\n'; ❺ std::string answer = word.substr(0, offset) + second_word; ❻ std::string response; ❼ std::getline(std::cin, response); ❼ if (response == answer) ❽ { std::cout << "CORRECT!!!!!!!!!\n"; } else { std::cout << answer << '\n'; } std::cout << word << ' ' << second_word << "\n\n\n"; } }

每个关键词

找到重叠部分

❸ 检查我们是否有合适的词汇

❹ 对于常量映射使用 at 而不是 operator[]

❺ 显示两个定义

❻ 将这两个词合并在一起

获取响应

❽ 查看猜测是否正确

我们可以从 main 调用这个并玩我们的游戏。

清单 7.7 播放答案击碎的第一个版本

#include "Smash.h" ❶ int main() { const std::map<std::string, std::string> keywords{ {"char", "type for character representation which can be most" "efficiently processed on the target system"}, {"class", "user defined type with private members by default"}, {"struct", "user defined type with public members by default"}, {"vector", "sequential container supporting dynamic resizing"}, {"template", "used for generic code"}, }; ❷ const std::map<std::string, std::string> dictionary{ {"assume", "take for granted, take to be the case"}, {"harsh", "coarse, large-grained or rough to the touch"}, {"table", "piece of furniture"}, {"tease", "mock, make fun of"}, {"torch", "lit stick carried in one's hand"}, }; ❸ simple_answer_smash(keywords, dictionary); ❹ }

包含声明 simple_answer_smash 的头部

❷ 设置关键词

❸ 设置字典

❹ 玩游戏

我们考虑了第一个关键词 “char” 和字典词 “harsh” 。对于这个组合，我们看到了线索。

type for character representation which can be most efficiently processed on the target system AND coarse, large-grained or rough to the touch

我们可以尝试猜测或者直接按回车键看看答案：

charsh char harsh

我们有一个简单的游戏。如果我们深入研究 map 和其他关联容器，我们将看到如何使重叠搜索更高效，并学习更多 C++。

7.2 关联容器

我们使用 std::map 构建了一个硬编码的游戏。如果我们了解结构内部发生的事情，我们将能够进行一些轻微的性能改进。有了这些，我们需要一个相关的数据结构 std::multimap ，以便存储一个合适的语言字典，这样我们就可以为每个键存储多个值。毕竟，单词有时有多个定义，因此当我们在本章的最后部分使用一个合适的字典时，我们可能需要为单个键存储多个值。

7.2.1 地图类型的详细信息

我们知道 vector 和 array 都是连续存储它们的元素，并且我们可以动态调整 vector 的大小，但不能调整 array 的大小。如果我们在 vector 中搜索一个项目，我们可能需要遍历所有元素才能找到我们需要的东西，可能会到达末尾而没有找到该项目。如果我们在 vector 中有 n 个元素，我们可能需要检查所有 n 个元素，这被描述为 O(n) ，或线性复杂度。我们已经看到我们可以动态地向 map 添加对，但我们还没有考虑元素是如何存储的，因此我们不知道搜索是如何工作的。

一个 map 的设计是为了让我们能够更快速地搜索项目。与将元素存储在彼此旁边不同，映射将它们存储在二叉树中。二叉树有节点，存储元素和指向其他子节点的指针，就像树中的分支，并且每个节点最多有两个分支；因此得名二叉。节点是有序的，形成一个二叉搜索树，较小的元素位于左侧，较大的元素位于右侧。对于一个 map ，我们的元素是一个键和值，键用于决定一个项目是放在左侧还是右侧。

如果我们将 {1:a} 、 {3:c} 和 {5:e} 放入 map 中，我们从一个单一节点 {1:a} 开始，然后添加 {3:c} 。由于关键字 3 大于 1 ，新元素 {3:c} 将移到右侧，如图 7.1 所示。

当我们添加最后一个元素 {5:e} 时，会发生两件事。首先，新节点比 {3:c} 大，因此它会位于下方和右侧，但在这里添加子节点意味着树是不平衡的。实际上，我们有一条 {1:a} 、 {3:c} 和 {5:e} 的链，而不是一个平衡的树，因为我们有很多右分支而没有左分支。将 {3:c} 提升为顶节点重新平衡了树，保持较小的元素在左侧，较大的元素在右侧，布局如图 7.2 所示。

将元素放入 map 后，我们现在可以对其进行搜索。如果我们想知道 {2:b} 是否在 map 中，我们从顶部节点 {3:c} 开始，由于键 2 小于 3 ，我们向下移动到左节点 {1:a} 。这与 2 不相等，并且是一个叶子或终止节点，因此我们的搜索结束。我们只考虑了树的一半。因为树是一个平衡二叉树，我们将搜索左分支或右分支，所以我们具有对数复杂度 O(log(n)) 。实际上，搜索、删除和插入操作都具有对数复杂度。如果我们将元素数量加倍，在搜索时只需要额外的一组比较。对于向量，搜索是 O(n) 。如果我们将元素数量加倍，在搜索时可能会将比较次数加倍。我们可能会幸运地在开始时找到一个元素，但在最坏的情况下，我们必须检查所有项目。图 7.3 显示了常数大 O 的最坏情况 O(n) 和对数大 O 的最坏情况 O(log(n)) 。

重新平衡保持搜索的高效性。C++ 映射通常实现为红黑树。颜色是每个节点的额外信息，在插入或删除时使用。为了保持搜索在 O(log(n)) ，树需要保持平衡。如果一条分支上的节点比另一条多得多，搜索较大一侧会花费更长时间。关于树数据结构和算法的经典资源是唐纳德·克努斯的《计算机程序设计艺术》第三卷（阿迪森-韦斯利专业出版社，1998 年）。

如果我们查看 CppReference（请参见
https://en.cppreference.com/w/cpp/container/map），我们会发现 map 是一个排序的关联容器。C++11 引入了无序容器，我们将在下一章中讨论。我们必须为我们的 map 指定键和值类型，但 map 还需要一个比较类型，用于在树中放置节点。比较默认为 std::less<Key> 。对于 std::string ，我们得到一个默认值 std::less<std::string> ，这对于 std::string 等于 operator< 。我们可以指定其他比较方式。例如，我们可能想先将所有字符串转换为小写。对于用户定义的类型，我们可能需要编写一个比较运算符或定义太空船运算符，以便在 map 中使用我们的类型。如果我们有一个用户定义的类型，即使是一个简单的结构体，例如

struct Stuff { int x; };

如果我们尝试在映射中使用 Stuff 作为键，则会出现编译错误：

std::map<Stuff, int> lookup; lookup[Stuff{ 1 }] = 1;

我们需要做的就是将飞船运算符添加到结构体中

friend auto operator <=> (const Stuff &, const Stuff&) = default;

然后我们可以在查找中使用它。

C++标准通常告诉我们容器上操作的复杂性，帮助我们在编码时做出明智的选择。大 O 或复杂性是最坏情况。例如，描述为 O(n) 的搜索如果第一个检查的元素是匹配项，可能只会查看一个元素。在最坏的情况下，所有元素都会被比较。复杂性是对可能发生的操作数量的指导，而不是效率的保证。我们可能仍然需要基准测试我们的代码以查看其速度，分析器可以帮助我们找到瓶颈。

现在，当我们在列表 7.6 中构建我们的简单答案时，我们手动检查了键，因此我们可能将我们的词干与所有 n 键进行了比较，给我们带来了 O(n) 。在没有分析的情况下，我们可以利用 std::map 提供的其他功能来改进这一点。

7.2.2 使用下界和上界更有效地查找键

std::map 具有 lower_bound 和 upper_bound 功能，帮助我们更有效地查询地图。这两个功能找到元素插入的位置。 lower_bound 找到大于或等于查询元素的第一个元素，而 upper_bound 找到具有更大值的元素的位置。尼古拉·乔苏蒂斯的书《C++标准库（第二版）》（阿迪森-韦斯利专业出版社，2012 年）是进一步了解的优秀参考书。 std::set 和 std::multiset 也支持这些功能。我们还没有使用这些容器。集合允许我们保留唯一值的集合，像 map 但仅有键，而多重集合允许我们有重复的键。

还有免费的函数 std::lower_bound 和 std::upper_bound ，可以在其他容器上使用，前提是元素按 operator< 排序。因此，我们可以在排序后的 vector 上使用这些函数：

const std::vector<int> data{ 1, 2, 4, 5, 6, 7 }; auto lower = std::lower_bound(data.begin(), data.end(), 3); auto upper = std::upper_bound(data.begin(), data.end(), 3);

这可能比逐个遍历元素寻找 3 更快。上下界都指向第三个元素 4 ，如图 7.4 所示。

当下界和上界匹配时，项不存在。如果我们插入 3 并再次运行查询， lower_bound 将返回一个迭代器到 3 ，而 upper_bound 仍将返回一个迭代器到值 4 。因为位置不匹配，我们找到了值 3 。下界大于或等于元素，上界始终大于元素，因此匹配的界限意味着它们都更大，而不同的界限意味着下界位于第一个这样的元素。

我们还可以在一次调用 equal_range 中找到下界和上界。这将返回一个 std::pair 的迭代器，因此我们可以再次使用结构化绑定来获取下界和上界：

auto [lb, ub] = std::equal_range(data.begin(), data.end(), 3);

std::map 及其他提到的容器具有相同的成员函数行为。我们有时会发现容器出于性能原因具有通用函数的专用版本。

我们可以使用 lower_bound 和 upper_bound 成员函数重写我们的查找重叠函数，从而避免可能检查所有键。之前，在列表 7.5 中，我们遍历了所有键，如果找到与词干匹配的项就退出循环。现在，我们可以使用 equal_range 来查找词干的下界和上界，因为这个函数将 lower_bound 和 upper_bound 的结果捆绑到一个 std::pair 中。下界在单词不存在时找到插入点，因此我们可能处于字典的末尾或在一个不匹配的单词处。在将词干与下界键的第一部分进行比较之前，我们需要检查下界是否不在字典的末尾。

lb->first.substr(0, stem.size()) 

以确定我们是否找到了合适的词。将这些汇总在一起给我们以下函数。

清单 7.8 更高效地查找重叠单词

std::pair<std::string, int> find_overlapping_word(std::string word, const std::map<std::string, std::string>& dictionary) { size_t offset = 1; while (offset < word.size()) { auto stem = word.substr(offset); auto [lb, ub] = dictionary.equal_range(stem); ❶ if (lb != dictionary.end() && stem == lb->first.substr(0, stem.size())) ❷ { return {lb->first, offset}; ❸ } ++offset; } return {"", -1}; }

不再有 for 循环

我们找到合适的重叠了吗？

❸ 返回单词和偏移量

我们可以在我们的游戏中使用这个功能，而不是我们在列表 7.5 中编写的原始版本。

我们在调用 find_overlapping_word 时只会找到第一个匹配的单词，这一点我们可以改进。可能会有多个重叠的单词，而且，合适的字典可能会为一个单词提供多个条目。当我们有多个合适的单词时，我们可以随机选择，这将为我们的游戏增添一些变化。我们还可以使用 std::multimap 来支持每个键的多个条目。在考虑关联容器时，让我们了解多重映射，然后我们就可以准备使用合适的字典制作我们游戏的新版本。

7.2.3 多重映射

一个 std::multimap 也存在于 map 头部，并使用一个键和值；例如：

std::multimap<std::string, std::string> dictionary;

multimap 支持相同键的多个值，并且表现得像一个 std::map ，但每个键有 vector 个值。

要插入项目，我们可以使用 insert :

dictionary.insert({ key, value });

或 emplace:

dictionary.emplace(key, value);

正如我们在第二章中看到的， insert 需要一个元素，因此我们将使用 std::pair 来处理 multimap 版本，而 emplace 从提供的参数构建元素。键值对仍然存在于树中的节点中，但我们可以有多个节点进行搜索，如图 7.5 所示。

要检索值，我们需要处理每个键可能有多个值的情况。此外， std::multimap 没有 operator[] 或 at 功能，因此我们需要做其他事情。幸运的是，使用 lower_bound 和 upper_bound 或 equal_range 可以满足我们的需求，使我们能够找到与给定键对应的所有值。这些函数返回迭代器，让我们可以使用与键对应的所有值（如果有的话）。

让我们考虑以下示例。使用命名空间字面量，我们可以制作一个与图 7.5 匹配的 multimap ：

std::multimap<int, std::string> mm{ {1,"a"s}, {1,"a"s}, {3,"c"s}, {3,"g"s}, {5,"e"s}, {5,"h"s}, };

如果我们搜索 mm.equal_range(2) ，我们会得到一个迭代器指向元素为 3:c 的节点，适用于下界和上界。这意味着一个键为 2 的元素将被插入到那里。如果我们改为搜索 mm.equal_range(3) ，下界为 3:c ，是第一个不小于键 3 的元素，上界为 5:e ，是第一个大于键 3 的元素。然后我们有一对迭代器可以用来遍历所有键为 3 的元素。

我们需要找到一个以词干开头的词，以便找到下界

auto stem = word.substr(offset); auto lb = dictionary.lower_bound(stem);

当字典是一个 multimap 时。我们需要的上界是词干之后的任何单词。如果我们复制词干

auto beyond_stem = stem;

我们可以在 ‘z’ 后添加一个字符，以超越单词的可能词干

beyond_stem += ('z' + 1);

并使用此来找到上界：

auto ub = dictionary.upper_bound(beyond_stem);

我们然后获取匹配的单词范围的开始和结束。如果有匹配，我们将使用 multimap 来构建一个更好的游戏，随机选择这个范围内的一个合适单词。

7.3 基于文件的答案击碎

我们制作了一个简单的答案击碎游戏，使用了硬编码的关键词和一个小字典。我们可以通过从文件加载数据来制作一个更有趣的游戏。本书提供的代码在本章的文件夹中有两个 csv 文件。一个包含了一些 C++关键词，使用基于 CppReference 的定义（请参见
https://en.cppreference.com/w/cpp/keyword），另一个包含了基于 Wordnetcode 子集的各种英语单词（请参见 http://mng.bz/M9KQ）。

7.3.1 从文件加载数据

我们还没有使用文件，但我们使用了流，例如 std::cout 和 std::cin ，C++ 将文件视为流。文件位于 fstream 头文件中。我们可以使用文件名打开输入文件 ifstream 。

std::ifstream infile{ filename };

并在布尔上下文中使用流以查看它是否打开：

if (infile) // all good

当变量超出作用域时，文件会自动关闭，因此文件流使用资源获取即初始化（RAII），我们在上一章中遇到过。

文件可以以文本或二进制格式写入，因此我们可以在构造函数中指定模式（请参见 http://mng.bz/yZDp）。我们的字典是文本，因此默认的文本模式适合我们。如果我们想写入文件，我们使用输出文件流， ofstream 。输出文件流也可以是文本或二进制，但我们可能还想截断现有文件或在末尾追加。我们可以使用输入输出流（ ios ）的按位 OR (|) 指定打开以进行输出和追加的模式，openmodes out 和 app 。

std::ofstream f1("test.txt", std::ios::out | std::ios::app); 

以及其他（请参见 http://mng.bz/Xqy9）。要从文件中读取，我们可以使用 operator>> 或 std::getline ，我们在第 3 章中与 std::cin 一起使用过。对于输出流，我们将使用 operator<< 。

我们文件中的单词以混合大小写存储，但我们不希望 Int 和 int 被视为不同的单词。因此，我们应该将键转换为小写，以便可以直接与小写输入进行比较。我们需要自己编写一些代码，因此在 CppReference 的指导下，我们可以转换 string ，使每个字符都变为小写。我们可以使用来自 algorithm 头文件的 transform 和来自 cctype 头文件的 C 语言 tolower 函数（请参见
https://shortener.manning.com/QR66）。 tolower 函数操作的是 int ，而不是 char ，所以我们必须小心。我们需要将每个字符视为 unsigned char ，因为如果参数的值既不是文件结束（EOF）也不能表示为无符号 char ，则 std::tolower 的行为是未定义的。因此，我们在转换中使用一个接受 unsigned char 的 lambda。

清单 7.9 将字符串转换为小写

#include <algorithm> #include <cctype> std::string str_tolower(std::string s) { std::transform(s.begin(), s.end(), s.begin(), [](unsigned char c) { return std::tolower(c); } ); return s; }

我们现在可以编写一个函数，从文件中加载字典。每一行将包含一个单词、一个逗号和一个定义：

struct,user defined type with public members by default

我们可以逐行查看文件，尝试找到第一个逗号：

size_t position = line.find(',');

如果 position 是 std::string::npos ，我们有一行无效的内容，可以记录并忽略。否则，我们可以将该行拆分为键和值。键是直到逗号位置的子字符串。

std::string key{ line.substr(0, position) };

定义是从逗号位置开始到行末的子字符串：

std::string value{ line.substr(position + 1) };

如果我们使用一个 std::string 作为文件名，我们可以编写一个返回 multimap 的函数，以便在我们改进的游戏中使用。 multimap 允许每个单词有多个定义。

清单 7.10 将文件加载到 multimap

#include <fstream> #include <iostream> #include <map> #include <string> std::multimap<std::string, std::string> load_dictionary(const std::string& filename) { std::multimap<std::string, std::string> dictionary; std::ifstream infile{ filename }; ❶ if (infile) ❶ { std::string line; while (std::getline(infile, line)) ❷ { size_t position = line.find(','); ❸ if (position != std::string::npos) { std::string key{ line.substr(0, position) }; ❹ key = str_tolower(key); ❹ std::string value{ line.substr(position + 1) }; dictionary.emplace(key, value); ❺ } else { std::cout << "*Invalid line\n" << line << "\nin " << filename << "*\n\n"; } } } else { std::cout << "Failed to open " << filename << '\n'; } return dictionary; }

❶ 创建并打开一个文件以进行读取

❷ 读取每一行

在逗号处分割

❹ 将键转换为小写

❺ 将键值对添加到多重映射中

我们可以使用这个函数来加载关键词和字典。某些操作系统的文件路径使用反斜杠，因此像 “c:\” 这样的内容可能会在代码中引发问题，因为反斜杠也用于转义特殊字符。我们可以使用原始字符串，这在 C++11 中引入，用 R() 包围字符串。如果我们将文件保存在工作目录中，就不需要使用原始字符串，但这是另一个值得注意的新特性：

const auto dictionary = load_dictionary(R"(dictionary.csv)"); const auto keywords = load_dictionary(R"(keywords.csv)");

原始字符串还有更多内容，但我们在这里将坚持使用 string 文件名。我们需要记住，代码需要在包含文件的目录中运行；否则，代码将找不到输入文件。

原始字符串和文件系统类型

我们可以在原始字符串中使用各种开始和结束字符，超出括号 ‘(‘ and ‘)’ （请参见 http://mng.bz/46ER）。我们甚至可以使用 C++17 中引入的文件系统路径（请参见
https://en.cppreference.com/w/cpp/filesystem/path）来表示文件路径。

7.3.2 使用 std::sample 随机选择一个单词

与其使用所有关键字，我们可以随机选择几个来进行游戏。我们还可以从字典中选择几个重叠的单词之一。C++17 引入了一个 sample 函数，它允许我们从一个范围中选择一些项目而不进行替换。每个项目的选择概率相同。 std::sample 函数位于 algorithm 头文件中。它接受一个起始迭代器和一个结束迭代器，一个输出迭代器用于写入样本，选择的样本数量，以及一个随机数生成器。因此，我们可以包含 random 头文件来创建一个生成器。

std::mt19937 gen{ std::random_device{}() };

并找到与单词词干匹配的条目。下限匹配词干：

auto stem = word.substr(offset); auto lb = dictionary.lower_bound(stem);

下限可能与我们想要的词根匹配，也可能不匹配。对于上限，我们希望超出词根的一个。

auto beyond_stem = stem; beyond_stem += ('z' + 1); auto ub = dictionary.upper_bound(beyond_stem);

超出词干的范围确保我们找到任何首字母匹配的单词。如果我们在寻找 “pet” ，我们希望包括 “petal” ，以及任何其他以 “pet” 开头的单词。

如果下界和上界 lb 和 ub 相等，我们无法找到合适的词；否则，我们可以从范围中抽取一个项目到 vector 中：

std::vector<std::pair<std::string, std::string>> dest; std::sample(lb, ub, std::back_inserter(dest), 1, gen);

在第二章中，我们发现帕斯卡尔三角形告诉我们抛硬币或在这种情况下从字典中选择条目的组合数量。选择单个项目并不困难，但选择多个项目则更复杂，因此 C++为我们做了繁重的工作。C++20 引入了 sample 算法的范围版本，我们可以用它来选择一些关键字。如果我们使用清单 7.10 加载关键字，我们可以使用 sample 选择 5 ：

std::vector<std::pair<std::string, std::string>> first_words; std::ranges::sample(keywords, std::back_inserter(first_words), 5, gen);

现在我们拥有创建一个基于文件中单词和定义的答案撞击游戏所需的所有部分。

7.3.3 答案击碎

首先，我们需要一个函数来选择一个重叠的单词在一个 multimap 中。因为我们可能会得到多个匹配的单词或一个具有两个不同定义的匹配单词，我们将使用我们刚刚遇到的随机 sample 函数来选择一个。如果我们制作一个函数模板，我们可以传入一个示例函数，这样测试就更容易了。我们可以使用一个 lambda 来执行随机抽样，或者始终选择第一个或最后一个项目，等等，以便进行测试。使用模板意味着我们应该将函数放在一个头文件中，因此我们使用我们的 Smash.h 头文件。

在列表 7.8 中，我们发现了一个重叠的单词并报告了重叠。我们也可以返回定义以节省额外的查找，因此我们可以使用 tuple 来返回单词、定义和偏移量。

std::tuple<std::string, std::string, int>

我们需要几个标题： map ， string ， tuple ，和 vector 。然后我们可以编写我们的函数。

列表 7.11 从 multimap 中选择一个词

template <typename T> std::tuple<std::string, std::string, int> select_overlapping_word_from_dictionary(std::string word, const std::multimap<std::string, std::string>& dictionary, T select_function) { size_t offset = 1; while (offset < word.size()) { auto stem = word.substr(offset); auto lb = dictionary.lower_bound(stem); ❶ auto beyond_stem = stem; ❶ beyond_stem += ('z' + 1); ❶ auto ub = dictionary.upper_bound(beyond_stem); ❶ if (lb != dictionary.end() && ❷ lb != ub) ❷ { std::vector<std::pair<std::string, std::string>> dest; ❸ select_function(lb, ub, std::back_inserter(dest)); ❸ auto found = dest[0].first; ❸ auto definition = dest[0].second; ❸ return { found, definition, offset }; } ++offset; ❹ } return {"", "", - 1}; ❺ }

找到合适的词汇

❷ 检查我们是否找到了合适的词汇

选择一个词典条目

❹ 没找到单词，请再试一次

❺ 未找到

我们可以测试这个功能。在列表 6.12 中，我们使用了一个假生成器和分布，但在这里我们只使用一个单一的 lambda 来选择一个项目。我们总是可以选择第一个或最后一个项目进行测试。第一个项目是下限。

auto select_first = [](auto lb, auto ub, auto dest) { *dest = *lb; };

最后一项是上限之前的一个：

auto select_last = [](auto lb, auto ub, auto dest) { *dest = *(--ub); };

我们可以在一个 check_properties 函数中使用 assert 函数再次测试我们的
select_overlapping_word_from_dictionary 函数。

清单 7.12 测试属性

#include <cassert> void check_properties() { auto select_first = [](auto lb, auto ub, auto dest) { *dest = *lb; }; auto [no_word, no_definition, no_offset] = select_overlapping_word_from_dictionary( "class", {}, select_first ); ❶ assert(no_word == ""); ❷ assert(no_offset == -1); ❷ }

使用空的多重映射和 lambda

未找到合适的词汇

最后，我们需要一个新的答案合并函数，接受两个多重映射。这与我们在列表 7.6 中构建的硬编码版本非常相似，但它现在使用 lambda 从字典中抽取一个项目：

std::mt19937 gen{ std::random_device{}() }; auto select_one = [&gen](auto lb, auto ub, auto dest) { std::sample(lb, ub, dest, 1, gen); };

五个关键词被抽样，并从字典中找到重叠项，给出一个 tuple ，以及 word 、 definition 和 offset 以节省线索的额外查找。

清单 7.13 一个更好的答案破坏游戏

#include <algorithm> #include <random> void answer_smash( const std::multimap<std::string, std::string>& keywords, const std::multimap<std::string, std::string>& dictionary) { std::mt19937 gen{ std::random_device{}() }; ❶ auto select_one = [&gen](auto lb, auto ub, auto dest) { ❶ std::sample(lb, ub, dest, 1, gen); ❶ }; ❶ const int count = 5; ❷ std::vector< ❷ std::pair<std::string, std::string> ❷ > first_words; ❷ std::ranges::sample( ❷ keywords, std::back_inserter(first_words), count, gen ); for (const auto& [word, definition] : first_words) { auto [second_word, second_definition, offset] = ❸ select_overlapping_word_from_dictionary(word, dictionary, select_one); if (second_word == "") { continue; ❹ } std::cout << definition << "\nAND\n" << second_definition << '\n'; ❺ std::string answer = word.substr(0, offset) + second_word; ❻ std::string response; ❻ std::getline(std::cin, response); ❻ if (str_tolower(response) == answer) ❻ { std::cout << "CORRECT!!!!!!!!!\n"; } else { std::cout << answer << '\n'; } std::cout << word << ' ' << second_word << "\n\n\n"; } }

将 std::sample 包装在一个 lambda 中

❷ 样本五个关键词

寻找合适的词汇

❹ 未找到任何内容，请再试一次

❺ 显示线索

❻ 检查小写响应

我们可以从 main 开始游戏，看看我们表现得如何。

清单 7.14 一个合适的答案击碎游戏

#include "Smash.h" int main() { using namespace smashing; const auto dictionary = load_dictionary(R"(dictionary.csv)"); const auto keywords = load_dictionary(R"(keywords.csv)"); answer_smash(keywords, dictionary); }

不要忘记在构建中包含一个 Smash.cpp 文件，并且代码需要在包含字典和关键字文件的目录中运行，或者在代码中更改路径。

你在玩游戏时应该会得到各种线索。有些非常令人愉快。例如，线索

is a prvalue expression whose value is the address of the implicit object parameter AND discipline that interprets past events

将 “this” 和 “history” 撞击在一起，得到 “thistory” 。

我们已经构建了我们想要创建的答案击碎游戏，并在此过程中使用了 std::map 和 std::multimap 进行了修订。我们注意到 C++引入了无序映射，因此我们将在下一章中更详细地讨论这些内容。

摘要

• 关联容器是标准模板库（STL）的一部分。
• 一个 std::pair 持有任何类型的两个值，我们使用 first 和 second 来访问这些值。
• std::tuple 是 std::pair 的一种概括，我们使用 std::get 来访问值。
• 我们可以使用结构化绑定将对、元组等直接绑定到变量中。
• std::map 的 operator[] 可用于查询和插入元素，因此如果您不想意外添加元素，请改用 at 函数进行查询。
• 一个 std::string_view 可以用来避免字符串的复制，但必须注意生命周期。
• std::map 的搜索、删除和插入操作具有对数复杂度。
• 一个 std::map 键必须由 std::less 操作符支持，因此我们可能需要为用户定义类型添加太空船操作符，以将其用作字典键。
• std::map 、 std::multimap 和 std::set 是有序关联容器，通常实现为红黑树。
• 一个 std::multimap 支持非唯一键。
• 使用有序关联容器的下界和上界成员函数以提高效率。
• 文件是流，因此它们支持 operator<< 和 operator>> 。我们还可以使用 std::getline 从输入文件流中读取整行。
• std::sample 函数从一个范围中无替换地选择 k 项的样本。