本章涵盖

• 无序映射
• 哈希
• 协程

在本章中，我们将制作一个匹配硬币的游戏。游戏有两个玩家：我们和计算机。我们每人都有一枚硬币，并选择正面或反面。如果计算机与我们的选择相匹配，我们就输了。如果计算机的选择不同，我们就赢了。我们可以使用随机分布来进行计算机的猜测，因此我们在第一个游戏中不需要太多代码。

一旦我们初步的匹配硬币游戏运行起来，我们将看看计算机是否能够通过构建一个读心机器来预测我们的猜测。老实说，计算机实际上并不能真正读懂我们的心思。克劳德·E·香农在 1953 年写了一篇名为《读心(?)机器》的短文（见 http://mng.bz/vPDp）。标题中的问号是故意的。这个游戏被用于博弈论的思想实验和心理学研究。读心者需要跟踪之前发生的事情，因此我们将使用 std::unordered_map 来跟踪状态。在第 7 章中，我们使用了一个 std::map 。在这一章中，我们将使用一个 std::unordered_map 进行进一步的练习。正如我们在第 7 章中提到的， std::map 需要为其键定义一个 operator< 。 std::unordered_map 需要一个 hash 和一个等于运算符，因此我们也将学习 std::hash 。计算机将使用状态来预测我们的下一个选择。当我们完成后，我们将把代码封装在一个协程中以进行额外的练习。

8.1 随机生成的匹配硬币

要开始，我们将让计算机随机生成一个 0 或 1 ，表示正面或反面，使用一个 std::uniform_int_distribution 。我们还需要用户输入。在第三章中，我们为猜数字游戏读取数字，因此我们需要类似于列表 3.4 中的函数的代码。该函数试图从流中提取一个数字并返回一个 std::optional 。在这种情况下，我们只想接受 0 或 1 。任何其他输入意味着玩家已经放弃。如果我们将整个输入作为字符串获取，我们可以将输入与 "0" 或 "1" 进行比较，并返回一个适当的 optional<int> 。任何其他输入除了 0 或 1 都返回一个空的 optional ，以表示玩家想要停止。

清单 8.1 读取一个 optional 0 或 1

#include <iostream>
#include <optional>
#include <string>
std::optional<int> read_number(std::istream& in)
{
    std::string line;
    std::getline(in, line);
    if (line == "0") {
        return { 0 };        ?
    }
    else if (line == "1") {
        return { 1 };        ?
    }
    return {};               ?
}

? 0

? 1

? 空的可选项以指示停止

为了构建我们的便士游戏，我们需要计算机随机选择 0 或 1 ，因此我们需要一个生成器和一个分布：

std::mt19937 gen{ std::random_device{}() };
std::uniform_int_distribution dist(0, 1); 

要获取计算机的选择，我们调用 dist(gen) 。我们比较玩家和计算机的回合以决定谁赢了。如果我们记录玩家赢的次数和进行的回合数，我们可以在游戏停止后报告一些统计数据。将这些整合在一起就形成了一个便士游戏。

清单 8.2 一分钱游戏

#include <random>
void pennies_game()
{
    int player_wins = 0;                                            ?
    int turns = 0;                                                  ?
    std::mt19937 gen{ std::random_device{}() };                     ?
    std::uniform_int_distribution dist(0, 1);                       ?
 
    std::cout << "Select 0 or 1 at random and press enter.\n";      ?
    std::cout << "If the computer predicts your guess it wins.\n";  ?
    while (true)                                                    ?
    {                                                               ?
        const int prediction = dist(gen);                           ?
 
        auto input = read_number(std::cin);                         ?
        if (!input)                                                 ?
        {                                                           ?
            break;                                                  ?
        }
        const int player_choice = input.value();
 
        ++turns;                                                    ?
        std::cout << "You pressed " << player_choice                ?
                  << ", I guessed " << prediction << '\n';          ?
 
        if (player_choice != prediction)                            ?
        {                                                           ?
            ++player_wins;                                          ?
        }
    }
    std::cout << "you win " << player_wins << '\n'
        << "I win " << turns - player_wins << '\n';
}

? 跟踪统计

? 计算机的回合

? 玩家回合

? 如果未选择 0 或 1，则停止

? 更新统计信息

我们需要从一个 main 函数调用 pennies_game 函数，然后我们就可以玩游戏。计算机平均可能赢一半的时间。就目前而言，这个游戏并不是那么有趣。如果两个真人对手玩，他们会试图通过不可预测的方式来智胜对方。如果计算机跟踪我们的选择，我们将面临更多挑战。让我们通过允许计算机思考，或者至少根据之前的动作进行预测来扩展游戏。我们能否设法随机行为并超越计算机？

8.2 使用 unordered_map 匹配硬币

香农跟踪了一个人对抗他的机器时的状态。他并不是跟踪计算机和玩家的确切选择，而是跟踪胜利或失败是否导致了变化，以及该变化是否导致了随后的胜利或失败。例如，玩家可能会输，选择相同的选项，然后再次输。这给出了八种可能的状态，如表 8.1 所示。

表 8.1 硬币游戏中的八种可能状态

对于每个状态，香农跟踪玩家做出的最后两个选择，记录他们是否改变了选择或坚持相同的选择。如果两个选择匹配，它们就形成了预测。如果不匹配，心灵读者则随机选择。我们可以从游戏开始时跟踪每个选择，但使用最后两个选择效果很好。让我们思考一下在跟踪每个状态的选择时会发生什么。我们将建立一对与状态相关的选择，并在它们匹配时用这些选择进行预测。

想象一下我们总是选择正面，因此我们从不改变主意。香农的策略能否弄清我们在做什么？随着时间的推移，无论我们赢还是输，桌子中间的选择将始终是相同的，因此只有四行会被填充。因为我们总是选择正面，最后两个选择最终将始终是相同的，导致结果列如表 8.2 所示。

表 8.2 如果我们总是选择正面，状态及相应结果

任何后续的选择必须对应于四个已填充的行之一，因为选择永远不会改变。机器将找到两个匹配的结果“相同”，并预测玩家将选择相同，因此它似乎读懂了我们的心思。如果我们每次都改变选择，状态表的其他四行最终将填充一对“变化”，机器也会再次正确预测。

填充状态表确实需要一些时间。最初，八个状态都没有任何条目，因此计算机随机选择。将此与玩家的选择进行比较可以告诉我们结果是胜利还是失败。我们记住这个结果，因为它提供了与第一列值对应的状态的第一部分。对于第二轮，我们仍然没有任何条目可以用于预测，因此计算机再次随机选择，玩家进行了一轮。我们记住了倒数第二个结果，现在知道玩家是否改变了主意，然后赢了或输了。这一轮的额外信息对应于状态的最后两列：

{penultimate outcome, choice, last outcome}.

现在我们已经有了完整的当前状态，我们准备在下一个回合添加第一个相应的选择。再次强调，计算机是随机出牌，但现在我们知道玩家是坚持同样的选择还是更改它。我们将此记录为与之前状态的第一个结果，然后更新为下次准备的状态。理论上，状态可能与之前相同，因此在下一个回合，我们在一行中有一对完整的选择；否则，我们在另一行中有一对的开始。随着时间的推移，我们将开始填充选择对，这意味着计算机可能会有与状态匹配的结果，并能够做出预测。心灵读者检查当前状态的状态表中是否有匹配对。如果有，预测就是该对中的值；否则，将做出随机选择。玩家也做出他们的选择，赢或输。然后可以更新状态，并将最新的选择存储在相应的值中。

我们注意到，始终切换或始终选择相同结果会被机器检测到。采用不那么明显的策略，跟踪最后两个动作的八个状态太多，难以记住，因此很难弄清楚机器在做什么。智者的最佳应对方式是自己跟踪状态，这样我们就知道它会预测什么，并采取相反的行动。智者并不是在读取玩家的思想，但很难跟踪它在做什么，因此可能给人一种心灵感应或任性的印象。就像许多机器智能的表象一样，实际上发生的只是模式匹配或某种统计分析。

与其使用最后两个状态，我们可以保留每个选择，并使用多数、移动平均或其他统计数据来进行预测。香农使用了一对来保持他构建的电路小巧、简单但有效。使用最后两个选择进行预测效果出奇地好，因此我们还是坚持香农的原始想法。

我们可以在一个关联容器中存储这八个状态，使用 std::tuple 作为三部分键，使用 std::pair 作为两个结果。元组需要一个胜利或失败，一个选择相同或更改，以及另一个胜利或失败。类枚举是表示这些的好方法。我们在第 5 章中遇到了作用域枚举，当时我们为我们的纸牌游戏制作了花色。枚举通常比魔法数字更清晰，因为我们可以使用名称来指示值，并且类枚举是强类型的，因此它不能被错误地隐式转换为整数。选择和结果最初将是未知的，因此我们可以使用 Shrug 和 Unset 作为这些值。我们只需在 enum 之后添加关键字 class 即可创建作用域枚举。

清单 8.3 三种可能的选择和结果

enum class Choice
{
    Same,
    Change,
    Shrug,
};
enum class Outcome
{
    Lose,
    Win,
    Unset,
};

我们状态的关键将是一个包含 Outcome 、 Choice 和另一个 Outcome 的元组，表示表 8.1 中的一行，值将是一个 Choices 的对，因此我们需要包含 utility 和 tuple 头。我们可以 typedef 关键和价值以节省每次使用它们时的输入 std::tuple<Outcome 、 Choice 、 Outcome> 和 std::pair<Choice, Choice> 。我们可以做得比 typedef 更好。C++11 引入了别名声明，允许我们说 using 来为现有类型引入别名。我们在 4.2.2 节中看到过这一点，当时我们定义了世纪并说 using centuries 。我们可以写

using state_t = std::tuple<Outcome, Choice, Outcome>;
using last_choices_t = std::pair<Choice, Choice>;

别名声明可以用于模板的家族，因此它比 typedef 更通用，但如果我们指定所有模板参数，它们是等价的。我们将在下一章进一步练习 using 声明。现在，请记住更倾向于 using 而不是 typedef 。

我们有一个键值对类型用于我们的状态，但需要一个容器。我们在上一章中学习了 std::map ，可以在这里再次使用它。然而，C++11 引入了无序容器，我们也可以将其用于查找表，所以让我们来了解这些容器是如何工作的。

8.2.1 无序容器和 std::hash

std::map 和 std::multimap ，以及 std::set 和 std::multiset ，是使用 std::less 作为默认比较的有序关联容器。正如我们在上一章中所学，元素以平衡二叉树的形式排列，因此搜索是 O(log(n)) 的。无序容器使用一种替代数据结构，称为哈希表，它将元素存储在槽或桶中。让我们花一点时间来了解哈希表。

哈希表使用一个 hash 函数来计算元素的索引，指示它属于哪个桶。该索引使我们能够直接跳到元素所属的桶，而无需沿着树的某部分遍历，因此搜索哈希表可能比搜索 std::map 或其他基于树的结构更快。

现在，两个不同的元素可能会给出相同的 hash 值，这被称为碰撞，因此我们可能会在特定的桶中有多个元素。搜索需要检查桶中的每个元素以找到特定元素，这会稍微减慢速度。对于一个好的哈希，我们不会遇到很多碰撞，通常会直接进入一个只有一个元素的桶，但有时我们可能需要检查桶中的几个元素。在最坏的情况下，我们可能会将所有元素都放在一个桶中，因此复杂度为 O(n) 。然而，对于一个体面的 hash 函数，我们期望每个桶中有一个项目，因此搜索在平均情况下是 O(1) 。用正式术语来说，我们说大 O 或复杂度是摊销常数时间。有时，标准告诉我们某个操作的最坏情况复杂度，但有时它告诉我们平均或摊销时间。

让我们通过将单个字符的键映射到整数值来可视化哈希表。如果我们使用键的小写版本的 ASCII 值作为 hash ，同一个字母的小写和大写版本将最终落入同一个桶中。如果我们添加两个元素，键为 'c' 和 'd' ，我们没有冲突，因此最多只有一个元素。

在一个桶中。然而，如果我们随后添加一个键为 'D' 的元素，我们就会发生冲突，因为键为 'd' 和 'D' 的元素会放入同一个桶，如图 8.1 所示。

要查找键为 'd' 的元素，我们需要检查第二个表中的两个元素。现在，冲突并不是灾难。我们仍然可以找到这些元素，但通过更好的 hash 函数可以获得更好的性能。

C++11 的无序容器是使用 std::hash 的哈希表，定义在 functional 头文件中，用于 hash 函数。C++ 为各种类型提供了 std::hash 的特化，包括数值类型，以及 std::string 等（请参见 https://en.cppreference.com/w/cpp/utility/hash）。如果我们想将一个没有 hash 的类型放入无序容器中，我们需要提供一个。该类型还必须支持相等比较，以应对 hash 碰撞。

让我们使用来自 unordered_map 头部的 std::unordered_map 来构建我们的状态表。与 std::map 一样，这需要一个 key 和一个 value 类型，但还需要一个 Hash 和一个 KeyEqual 类型。这些默认为 std::hash 和 std::equal_to ，类似于

template<class Key, class Value, 
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>
> class unordered_map;

我们的关键是一个 std::tuple ，它支持 std::equal_to 。这在 C++14 中引入，默认是一个函数对象，在给定类型上调用 operator== 。比较元组开箱即用。给定两个元组

std::tuple t1 = {Outcome::Lose, Choice::Shrug, Outcome::Lose};
std::tuple t2 = {Outcome::Lose, Choice::Shrug, Outcome::Lose};

我们可以检查相等性：

bool match = t1 == t2;

这相当于

bool match = std::equal_to{}.operator(t1, t2);

首先，我们使用 {} 创建一个 std::equal_to 实例，然后 std::equal_to 的调用运算符默认调用 operator== 。因此， unordered_map 类模板中的默认 KeyEqual 适用于我们的键。然而， std::tuple 没有哈希实现，因此我们需要自己编写。我们可以专门化 struct 。

template<class Key>
struct hash;

对于我们的元组。单独来看， struct 并没有太大作用。然而，在 functional 头文件中有几个特化提供了一个 operator() const ，接受一个 Key ，并返回一个 size_t 。许多运算符被标记为 noexcept ，因为它们不会抛出异常。我们将为 state_t 实现一个特化。CppReference 告诉我们可以将自定义的 std::hash 特化注入到标准命名空间中（请参见 https://en.cppreference.com/w/cpp/utility/hash）。我们通常将代码添加到我们的命名空间中，而不是命名空间 std ，以避免与标准代码冲突。为特定类型定义 std::hash 是一个例外。这意味着 unordered_map 将为我们的键找到 std::hash 的特化。

要专门化一个模板，我们声明我们正在特殊处理的类型。 hash 只接受一种类型， template<class Key> ，因此我们只有一种类型需要特殊处理。我们从模板头中去掉 class Key ，留下 template<> ，并在名称后用尖括号指定类型，这样我们就得到了

template<>
struct std::hash<state_t>

我们的专业化需要一个操作符，接受一个键并返回一个 size_t 。它需要是 const ，我们可以将其标记为 noexcept ：

std::size_t operator()(state_t const& k) const noexcept

我们的元组有三个枚举，标准库为枚举提供了 std::hash 的特化。我们可以编写一个 hash 函数，将各个元素的哈希值结合起来，以提供 std::hash<state_t> 的特化。找到一种组合哈希的方法以避免冲突是很好的。对哈希值求和

{Outcome::Lose, Choice::Shrug, Outcome::Win}

将映射到相同的哈希值

{Outcome::Win, Choice::Shrug, Outcome::Lose}

导致冲突。如果我们能够使用 operator<< 为每个元素移动哈希值，我们可以做得更好。我们已经多次使用了流插入 operator<< 。内置的算术 operator<< 适用于数字而不是流，向左移动位（见 http://mng.bz/n1D5）。移动二进制数字 1, 1 << 1 会得到 10 的二进制表示，因为一位向左移动。如果我们再移动一次， 2 << 1 ，我们得到 100 的二进制表示。通过不移动第一个元素，将第二个元素移动一个位置，将最后一个元素移动两个位置，然后将三个移动后的哈希值相加，我们恰好避免了键的冲突。我们的方法在一般情况下并不好。我们尝试组合的元素越多，发生冲突的机会就越大，而我们向左移动的越多，最终得到零的可能性就越大。然而，对于我们少量的 Outcome 和 Choice ，这种方法确实有效。

我们需要为 std::hash 包含 functional 头。我们元组的特化如下。

清单 8.4 为我们的状态元组专门化 std::hash

#include <functional>
template<>                                                            ?
struct std::hash<state_t>                                             ?
{
    std::size_t operator()(state_t const& state) const noexcept       ?
    {
        std::size_t h1 = std::hash<Outcome>{}(std::get<0>(state));    ?
        std::size_t h2 = std::hash<Choice>{}(std::get<1>(state));     ?
        std::size_t h3 = std::hash<Outcome>{}(std::get<2>(state));    ?
        return h1 + (h2 << 1) + (h3 << 2);                            ?
    }
}; 

专门化 std::hash 用于 state_t

? 实现 operator()

获取每个元素的哈希值

? 移位和求和

这将适用于我们的特定用例。WG21 讨论了哈希组合函数（请参见 http://mng.bz/orDZ），并表示实现一个好的 hash 函数并不简单。如果我们需要一种更通用的方法将字段组合成合适的哈希，Boost 库有一个 hash_combine 方法（请参见 http://mng.bz/6nre）。Boost 是一个免费的同行评审 C++库，已经存在很长时间了。许多新的 C++特性最初是在 Boost 中诞生的，包括智能指针和 optional 、 any 、 variant 类型。该库仍然包含许多在 C++中尚不支持但可能在未来被采纳的特性。它很大，但如果你以前没有见过，值得一看。

凭借 hash 函数，我们准备在 unordered_map 中保持我们心灵感应机器的状态。在包含 unordered_map 头文件后，我们可以编写一个返回初始状态的函数。表 8.1 中的八个键在我们的 state_t 元组中表示。元组元素指示输或赢，后跟玩家选择的相同或交换，导致赢或输。相应的值是一对存储玩家在状态发生的最后两次选择的方式。最初，没有玩家选择可存储，因此我们将状态标记为未设置，使用一对 Shrug ：

const auto unset = std::pair<Choice, Choice>{Choice::Shrug,Choice::Shrug};

我们可以像在上一章中对 std::map 所做的那样，使用初始化列表来初始化 std::unordered_map 。

列表 8.5 初始状态表

#include <unordered_map>
std::unordered_map<state_t, last_choices_t> initial_state()
{
    const auto unset = std::pair<Choice, Choice>{Choice::Shrug,
                                                 Choice::Shrug };
    return {
        { {Outcome::Lose, Choice::Same,   Outcome::Lose}, unset },
        { {Outcome::Lose, Choice::Same,   Outcome::Win},  unset },
        { {Outcome::Lose, Choice::Change, Outcome::Lose}, unset },
        { {Outcome::Lose, Choice::Change, Outcome::Win},  unset },
        { {Outcome::Win,  Choice::Same,   Outcome::Lose}, unset },
        { {Outcome::Win,  Choice::Same,   Outcome::Win},  unset },
        { {Outcome::Win,  Choice::Change, Outcome::Lose}, unset },
        { {Outcome::Win,  Choice::Change, Outcome::Win},  unset },
    };
}

我们尝试确保不会出现哈希冲突。对于我们的八个状态，冲突不会明显减慢游戏速度，但我们可以检查每个桶最多只有一个元素。 std::unordered_map 提供了 bucket_count ，告诉我们总共有多少个桶，以及 bucket_size 函数，告诉我们特定桶中有多少个项目。我们可以使用 assert 编写一个 check_properties 函数，以验证我们没有任何冲突。

清单 8.6 检查我们没有 hash 碰撞

#include <cassert>
void check_properties()
{
    std::unordered_map<
        state_t,
        last_choices_t
    > states = initial_state();
 
    for (size_t bucket = 0;
            bucket < states.bucket_count();
            bucket++)
    {
        assert(states.bucket_size(bucket) <= 1);    ?
    }
}

每个桶最多一个项目

测试通过，但我们手工制作的 hash 函数如果添加更多状态可能会崩溃。编写 hash 函数可能很困难。

我们现在可以开始在玩家做出选择时进行预测。将状态与读心游戏分开意味着我们可以更容易地测试我们的代码。

8.2.2 使用 unordered_map 进行预测

心灵读者要么根据状态表预测玩家的选择，要么做出随机选择。我们将把状态表保存在一个类中，提供一个 getter 函数和一个 update 函数，以便在每轮之后使用。我们可以使用一个私有状态表，该表通过列表 8.5 中的 initial_state 函数初始化。

清单 8.7 用于跟踪游戏状态的类

class State
{
    std::unordered_map<state_t,last_choices_t> state_lookup
                                             = initial_state();   ?
 
public:
    last_choices_t choices(const state_t& key) const;             ?
    void update(const state_t& key,
                const Choice& turn_changed);                      ?
};

? 私有状态

获取给定状态的选择

? 在进行回合时更新值

我们有八个有效状态，但在有有效的 state_t 可供查找之前需要一些预热。例如，我们将从没有回合开始，因此有状态

{Outcome::Unset, Choice::Shrug, Outcome::Unset}

该状态不在表 8.1 中，因此我们将使 choices 函数在这种情况下返回一对 Shrug 。我们尝试在查找中找到一个键。 find 方法如果未找到元素，则返回 unordered_map 的 end ，因此我们处于无效状态。如果找到，我们返回相应的值。

清单 8.8 查找选择或返回两个 Shrug s

last_choices_t choices(const state_t& key) const
{
    if (auto it = state_lookup.find(key);
            it!=state_lookup.end())                  ?
    {                                                ?
        return it->second;                           ?
    }
    else
    {
        return { Choice::Shrug, Choice::Shrug };     ?
    }
}

? 尝试寻找钥匙

在热身阶段，所以耸肩

为了更新状态，我们还需要注意初始 state_t 不在我们的状态表中。同样，我们尝试找到关键：

if (auto it = state_lookup.find(key); it != state_lookup.end())

如果我们有一个有效的状态，我们从迭代器中获得之前的两个选择：

const auto [prev2, prev1] = it->second;

我们可以用新对更新密钥：

last_choices_t value{ prev1, turn_changed };
it->second = value;

实际上，更新状态时会忽略前几轮的无效状态，仅更新有效状态。

清单 8.9 更新有效键的选择

void update(const state_t& key, const Choice& turn_changed)
{
    if (auto it = state_lookup.find(key);
            it != state_lookup.end())                  ?
    {
        const auto [prev2, prev1] = it->second;        ?
        last_choices_t value{ prev1, turn_changed };   ?
        it->second = value;                            ?
    }
}

? 检查密钥是否存在

? 形成新的选择对

? 更新查找

我们可以使用 choices 返回的 last_choices_t 来进行预测，即使对于初始无效状态。如果两个元素匹配，我们返回该值；否则，我们返回 Choice::Shrug ，表示我们无法进行预测。我们故意为无效状态返回了一对 Shrug 。因为它们匹配，所以对于无效状态返回一个 Shrug ，这样心灵读者就知道要做出随机选择。

清单 8.10 从状态中选择

Choice prediction_method(const last_choices_t& choices)
{
    if (choices.first == choices.second)    ?
    {                                       ?
        return choices.first;               ?
    }
    else
    {
        return Choice::Shrug;               ?
    }
}

匹配，因此返回任一值

? 不匹配，因此无法进行预测

我们现在准备构建一个心灵阅读器。它将使用我们的 State 类来进行预测。心灵阅读器进行预测，玩家做出选择。然后我们更新状态表，准备进行新的预测。

8.2.3 心灵读者游戏

我们可以使用在列表 8.7 中创建的 State 类来创建一个 mind reader 类。我们需要对某些状态进行随机翻转。我们已经多次使用生成器和分布使用随机数。我们可以制作一个模板类，接受这些类型，以便在测试中伪造它们。当我们在列表 6.12 中测试我们的随机块时，我们使用了一个始终返回 0 的生成器的 lambda。

[]() { return 0; }

并且可以在这里做同样的事情。对于实际游戏，我们使用一个合适的生成器和一个返回 0 或 1 的分布：

std::mt19937 gen{ std::random_device{}() };
std::uniform_int_distribution dist{ 0, 1 };

使用分布和生成器可以让心灵读者生成一个随机的 0 或 1 ：

int flip() { return dist(gen); }

我们可以使用该函数来初始化预测变量：

int prediction = flip();

心灵读者的 prediction 将在玩家进行回合后更新，使用当前状态，因此我们需要一个初始化为 state 的变量

{Outcome::Unset, Choice::Shrug, Outcome::Unset}    

我们将很快定义更新函数。如果它返回一个 bool ，表示是翻转而不是预测，我们可以在游戏进行时跟踪心灵读者做了多少次猜测。我们的心灵阅读类如下所示。

清单 8.11 一个读心术类

template <std::invocable<> T, typename U>
class MindReader {
    State state_table;
    T generator;
    U distribution;
    int prediction = flip();               ?
    state_t state{                         ?
        Outcome::Unset,                    ?
        Choice::Shrug,                     ?
        Outcome::Unset                     ?
    };                                     ??
    int previous_go = -1;                  ??
    int flip()                             ?
    {                                      ?
        return distribution(generator);    ?
    }
public:
    MindReader(T gen, U dis)
        : generator(gen), distribution(dis)
    {
    }
    int get_prediction() const
    {
        return prediction;
    }
    bool update(int player_choice);
}; 

? 最初做出随机选择

? 存储状态和玩家的回合

当玩家进行他们的回合时，我们更新心灵读者，让它知道玩家的选择。首先，玩家的选择是否发生了变化，因此可以使用列表 8.9 中显示的函数来更新当前状态。我们计算回合是否发生了变化。

const Choice turn_changed = player_choice == previous_go ?
                            Choice::Same : Choice::Change;

然后相应地更新状态表：

state_table.update(state, turn_changed);

我们可以将当前的 player_choice 存储在 previous_go 中，以便下次使用。

当前状态已经改变，可以进行新的预测，为下一轮做好准备。我们更新状态，将之前的胜负移到元组的前面，并记录这一轮是否发生了变化以及是否获胜：

state = {std::get<2>(state), turn_changed, 
    (player_choice != prediction) ? Outcome::Win : Outcome::Lose};

我们在表中查找该状态， state_table.choices(state) ，并使用该对来决定采用列表 8.10 中的函数进行预测方法。我们得到一个 Choice 。对于 Shrug ，我们抛硬币。对于 Change ，我们想要将一个 0 与一个 1 交换，反之亦然，因此我们可以使用按位 operator^ ，与 1 一起，计算选择的 xor 与 1 ，得到相反的结果。如果预测是相同的，我们知道玩家在这一轮选择了什么，因此我们相应地更新我们的预测。我们可以在 MindReader 中实现这一点的新函数。

清单 8.12 更新预测

bool update_prediction(int player_choice)
{
    bool guessing = false;
    Choice option = prediction_method(state_table.choices(state));
    switch (option)
    {
    case Choice::Shrug:
        prediction = flip();
        guessing = true;
        break;
    case Choice::Change:
        prediction = player_choice ^ 1;
        break;
    case Choice::Same:
        prediction = player_choice;
        break;
    }
    return guessing;
}

update 函数在更新状态表和当前状态后使用 update_prediction 。

清单 8.13 心灵读者的 update 方法

bool update(int player_choice)
{
    const Choice turn_changed = player_choice == previous_go ?
                                Choice::Same : Choice::Change;
    state_table.update(state, turn_changed);        ?
 
    previous_go = player_choice;
    state = {std::get<2>(state),
             turn_changed,
             (player_choice != prediction) ?
                Outcome::Win : Outcome::Lose};      ?
 
    return update_prediction(player_choice);        ?
}

更新状态表

? 更新状态

? 进行下一个预测

游戏本身现在非常像我们在列表 8.2 中开始的硬币游戏。我们需要咨询读心者以获取预测，而不是在主游戏循环中随机选择 0 或 1 。我们还将跟踪猜测的次数，并在玩家停止时报告该次数。

清单 8.14 一款读心游戏

void mind_reader()
{
    int turns = 0;
    int player_wins = 0;
    int guessing = 0;
 
    std::mt19937 gen{ std::random_device{}() };
    std::uniform_int_distribution dist{ 0, 1 };
    MindReader mr(gen, dist);
 
    std::cout << "Select 0 or 1 at random and press enter.\n";
    std::cout << "If the computer predicts your guess it wins\n";
    std::cout << "and it can now read your mind.\n";
    while (true)
    {
        const int prediction = mr.get_prediction();              ?
 
        auto input = read_number(std::cin);
        if (!input)
        {
            break;
        }
        const int player_choice = input.value();
 
        ++turns;
        std::cout << "You pressed " << player_choice 
            << ", I guessed " << prediction << '\n';
 
        if (player_choice != prediction)
        {
            ++player_wins;
        }
        if (mr.update(player_choice))                            ?
        {
            ++guessing;
        }
    }
    std::cout << "you win " << player_wins << '\n'
        << "machine guessed " << guessing << " times" << '\n'    ?
        << "machine won " << (turns - player_wins) << '\n';
} 

咨询读心者

更新心灵阅读器

? 报告猜测

从 main 调用这个，看看你是否能智胜读心者。如果你自己跟踪状态，你可以看到它将预测什么并获胜，但没有纸和笔，你可能会忘记。事实证明，随机行为是非常困难的。

我们有一个读心器，我们可以将其打包在协程中，以了解另一个新的 C++ 特性。

8.3 协程

协程是在 1950 年代发明的，梅尔文·康威在 1958 年创造了这个术语。后来，在 1978 年，托尼·霍尔在《ACM 通讯》的一篇论文中描述了一种称为通信顺序过程（CSP）的协程类型（见 https://dl.acm.org/doi/10.1145/359576.359585），并在 1985 年出版了同名书籍。他开发了一种使用通过消息传递进行通信的顺序过程的并发编程语言。他的方法避免了并发代码中的一些常见问题，例如死锁。他的形式语言允许进行数学证明，证明这些问题不会发生。在一个非常高的层面上，这些过程是具有输入和输出的函数。通过将输入和输出连接在一起，多个函数可以同时运行，而无需保护共享内存。

C++20 引入了协程（见 http://mng.bz/5oEO）。支持相对较低级，因此 C++ 协程通常需要相当多的样板代码。我们可以编写一个协程来生成玩家的选择和预测。这既不会改变游戏，也不会充分利用异步代码的全部功能，但我们将发现构建协程所需的内容，并修订我们在第六章中学习的零规则。即使我们不使用协程的全部潜力，了解所需的构建块也是值得的。

协程是强大而灵活的。挂起和恢复工作，可能在不同的线程上，提供了一种并行性。刘易斯·贝克撰写了一系列博客文章，详细介绍了这一主题（请参见 http://mng.bz/mjda），互联网上有很多关于 C++ 协程的演讲和博客文章，因为它们是一项可以以多种方式使用的重要新特性。让我们学习基础知识。

8.3.1 如何创建协程

协程是一个包含一个或多个关键字： co_yield 、 co_await 或 co_return 的函数。Yield 返回一个值并暂停该函数。协程的状态被打包，允许挂起的执行在稍后继续。Await 表达式调用一个异步操作，并在该操作完成时恢复。Return 完成函数。与普通函数不同，协程的生命周期与调用者无关。例如，恢复可以在不同的线程上发生。我们在这里不会使用该特性，而是学习将普通函数转换为协程所需的内容。协程函数返回一个提供所需样板代码的对象，这允许编译器生成协程代码。

在大多数情况下，我们需要为返回的对象编写代码，尽管 C++23 引入了 std::generator (http://mng.bz/7vmv)，它提供了一个具体类型以从简单生成器协程返回。CppReference 提供了示例代码，从名为 letters 的协程输出字母表。 letters 函数是一个协程，因为它使用了 co_yield. 。该函数返回一个 std::generator ，它提供了所需的内容以连接协程的初始化并处理 co_yield 。该函数没有 co_return ，我们注意到这会完成一个协程，因此 letters 可能会生成一个无限序列。我们可以随意调用它。例如，我们可以使用范围的 views 通过 take 函数获取前 26 个字母。不幸的是， std::generator 还没有得到广泛支持，但 Visual Studio 2022 确实在 experimental/generator 头文件中提供了一个 experimental 版本。

清单 8.15 使用 std::generator

#include <experimental/generator>                                 ?
#include <ranges>
 
std::experimental::generator<char> letters(char first)            ?
{
    for (;; co_yield first++);                                    ?
}
 
void generator_experiment()
{
    for (const char ch : letters('a') | std::views::take(26))     ?
        std::cout << ch << ' ';
    std::cout << '\n';
} 

? 使用实验性头部

协程返回生成器

? co_yield 使此函数成为协程。

? 根据我们的需要调用协程

随着时间的推移，我们可能会看到标准支持的协程的更具体的返回对象。目前，我们通常需要自己编写样板代码，除非我们的选择的编译器支持 std::generator 并且适用于我们的用例。

我们将编写一个协程， co_yields 玩家输入以及心灵读者的预测。调用代码将获取并显示结果。我们游戏的协程版本并不是必需的，但理解如何使用这个新的 C++ 特性将是有益的。我们将逐步构建协程所需的代码。到目前为止，我们已经发现协程

• 是一个包含 co_yield 、 co_await 或 co_return 的函数
• 返回一个提供所需样板的对象

清单 8.15 有一个 co_yield ，生成器提供所需的样板代码。为了将我们的游戏变成一个协程，我们将

• 编写一个包含 co_yield 和 co_return 的函数（第 8.3.2 节）
• 返回一个用户定义的类叫做 Task ，尽管可以使用任何其他名称（第 8.3.3 节）
• 实现一个 promise_type ，因为编译器期望它，所以必须这样称呼（第 8.3.3 节）

Task 和 promise_type 从协程函数开始、停止并生成数据，因此我们将添加细节：

• Task 和 promise_type 的创建与销毁（第 8.3.4 节）
• 启动和停止协程以及如何 co_yield 数据或 co_return （第 8.3.5 节）
• 对 Task 本身的调用，允许调用代码在协程挂起后恢复，直到游戏完成（第 8.3.6 节）

我们以使用 Task 的调用代码结束，这为我们提供了游戏的新版本。

8.3.2 协程函数

在列表 8.14 中，我们编写了一个 mind_reader 函数，处理用户输入，获取预测并显示结果。我们将提取用户输入和预测以形成一个协程。我们需要包含 coroutine 头文件，我们的新函数将返回一个提供协程所需样板的对象。我们称之为 Task 并在下一节中实现它。我们将从协程本身开始。

像之前一样，我们创建一个 MindReader 对象，并在用户想要玩的时候循环。如果玩家放弃，我们的协程将使用 co_return 停止。否则，我们 co_yield 玩家选择和读心者的预测。将 co_return 或 co_yield 添加到一个函数并返回一个合适的对象就形成了一个协程。

列表 8.16 我们的第一个协程

#include <coroutine>
struct Task;                                                ?
Task coroutine_game()                                       ?
{
    std::mt19937 gen{ std::random_device{}() };
    std::uniform_int_distribution dist{ 0, 1 };
    MindReader mr(gen, dist);
    while (true)
    {
        auto input = read_number(std::cin);
        if (!input)
        {
            co_return;                                      ?
        }
        int player_choice = input.value();
        co_yield{ player_choice , mr.get_prediction() };    ?
        mr.update(player_choice);
    }
} 

? 前向声明我们将很快实施的任务

协程函数返回一个合适的对象

? 如果玩家放弃则停止

? 让玩家的回合和读心者的预测

编译器使用返回的 Task 中的函数来连接所需的 yield 和 return，以及创建协程帧。这将函数打包起来，使其在遇到 co_XXX 函数时可以挂起。当我们 yield 一个选择和一个预测时，协程会挂起，直到恢复。然后，协程在下一行继续执行，状态与暂停时相同，更新思维读取器。如果我们调试协程，恢复时我们似乎会瞬移到 while 循环的中间。

协程状态通常是动态分配的，因此它通常被描述为无栈的。实际上，协程是一个打包为动态对象的函数，以便可以暂停（挂起）并恢复直到完成。协程甚至可以在不同的线程上恢复。控制在调用者和协程之间传递，如图 8.2 所示。

我们提前声明了一个 Task 以从我们的协程中返回，所以接下来让我们实现它。

8.3.3 协程的返回对象

协程的返回对象通常被描述为一个承诺或任务，但我们可以自由使用任何我们喜欢的名称。我们需要为我们的协程添加几个函数。具体要求因每个协程而异，但我们总是会看到两样东西。首先是一个承诺对象，用于将结果发送或报告异常给协程外部的代码；其次是一个协程句柄，用于在协程内部恢复执行或在完成时销毁协程帧。

让我们逐步构建我们的 Task 。编译器需要在我们的 Task 中有一个叫做 promise_type 的东西。我们可以单独定义一个类并向任务添加一个 using 声明，或者我们可以将类作为嵌套类内联定义在 Task 中。我们将使用嵌套类，因此我们的协程返回的 Task 开始如下。

清单 8.17 连接协程的结构

#include <coroutine>
struct Task                ?
{
    struct promise_type    ?
    {
    };
};

? 由列表 8.16 返回的任务

? 所需结构

编译器使用 Task ，这是我们在清单 8.16 中从 coroutine_game 返回的，以及它的 promise_type 来生成代码。我们需要在 promise_type 和 Task 中提供更多细节，以使我们的 coroutine_game 能够编译。我们可以为返回类型使用任何名称，尽管 Task 是一个常用名称；然而，我们必须有一个名为 promise_type 的关联类。 Task 和 promise_type 允许协程启动、停止和返回数据。让我们填充细节。

8.3.4 RAII 和零原则

在列表 8.16 中，我们编写了一个返回我们刚开始创建的 Task 的协程。编译器为协程生成的代码通过调用 get_return_object 函数从 promise_type 获取 Task ，类似于以下伪代码：

promise_type promise;
auto task = promise.get_return_object();

我们并不直接创建一个 Task 。只有 promise_type 在 get_return_ object 函数中这样做。就目前而言，我们可以向 promise_type 添加一个函数：

Task get_return_object() {  return Task{}; }

然而，我们仍然可以在任何地方创建 Task ，这些对编译器以外的任何事物都没有太大用处。如果我们给 Task 一个私有构造函数， promise_type 可以创建一个任务，因为我们将其设为内部类，但其他任何东西都不能。

此外，我们注意到承诺对象将结果或报告异常发送到协程外的代码，并且我们使用协程句柄在完成时恢复执行或销毁协程框架。协程提供了一个 from_promise 方法来获取 std::coroutine_handle ，因此如果我们将指针存储在 Task 中的 promise_ type 。

promise_type * promise;

我们可以在需要时包含一个句柄

auto handle = std::coroutine_handle<promise_type>::from_promise(*promise);

现在，原始指针常常麻烦。我们不需要删除指针，因为编译器为我们处理协程的生命周期，但我们应该在完成后调用 destroy 方法。如果我们在 Task 中添加一个析构函数，我们可以使用 RAII 进行必要的清理。在析构函数中，我们可以从 promise 创建一个句柄并调用。

handle.destroy()

然而，第 6 章告诉我们，添加我们自己的析构函数会隐式阻止移动，但仍然可以进行复制操作。复制一个 Task 是潜在的资源泄漏。我们可以显式删除复制并默认移动，或者为承诺指针使用智能指针。使用智能指针意味着我们不再需要析构函数来为我们整理。

在第 6 章中，我们遇到了 std::unique_ptr 。我们在那里的默认设置是 "delete" ，因为我们有想要被删除的原始指针。现在我们希望发生不同的事情。智能指针接受一个类型和一个删除器，默认调用 delete ：

template<class T, class Deleter = std::default_delete<T>> class unique_ptr

我们的删除器需要在通过我们的 promise_type 指针获得的句柄 from_promise 上调用 destroy 。我们可以使用类模板为任何承诺类型编写一个更通用的函数。

清单 8.18 自定义 "deleter"

template<typename Promise>                               ?
struct coro_deleter                                      ?
{                                                        ?
    void operator()(Promise* promise) const noexcept     ?
    {
        auto handle =
            std::coroutine_handle<Promise>::from_promise(
                *promise
            );                                           ?
        if (handle)                                      ?
            handle.destroy();                            ?
    }
};

? 适用于任何承诺类型的模板函数

从承诺中获取句柄

如果有句柄，调用将被销毁

我们可以声明一个模板家族，利用我们之前遇到的 using 语句中的删除器。我们使用任何类型的 std::unique_ptr ， T ，以及 coro_ deleter<T> ：

template<typename T>
using promise_ptr = std::unique_ptr<T, coro_deleter<T>>;

我们现在可以在 Task 中使用 promise_ptr 并依赖于零规则。没有要删除的副本或要默认的移动，因为我们不再需要定义析构函数，因为 std::unique_ptr 将为我们整理。

我们现在可以在 Task 中填充更多的函数。首先，我们添加一个接受 promise_type 指针的私有构造函数，并将其存储在 promise_ptr 中。然后，我们可以向 promise_type 添加一个 get_return_object 函数，返回一个 Task 。

清单 8.19 连接协程的结构

#include <coroutine>
#include <memory>
struct Task
{
    struct promise_type
    {
        Task get_return_object()              ?
        {
            return Task(this);
        }
    };
private:
    promise_ptr<promise_type> promise;        ?
    Task(promise_type* p) : promise(p) {}     ?
};

仅由 promise_type 创建的任务

智能指针用于 RAII

? 私有构造函数

我们已经编写了足够的内容，以便在完成时创建一个 Task 并销毁一个协程句柄。我们仍然需要添加更多的函数来处理创建和销毁之间发生的事情。让我们填充细节，以使列表 8.16 中使用的 co_yield 和 co_return 正常工作。

8.3.5 填充 promise_type

让我们从 promise_type 开始。编译器根据此类中的函数注入代码。我们始终需要定义三个函数，说明在以下情况下会发生什么：

1. 当我们第一次启动协程时
2. 如果抛出异常
3. 当协程停止时

在协程主体中任何未捕获的异常都会调用一个 unhandled_ exception 方法。最简单的实现什么也不做：

void unhandled_exception() {}

或者，我们可以记录问题，甚至调用终止。

我们还需要名为 initial_suspend 和 final_suspend 的方法来指示是否暂停。作为协程支持的一部分，C++20 引入了两个辅助类 suspend_always 和 suspend_never ，分别用于暂停或不暂停。我们希望我们的协程能够为调用代码准备用户输入和预测，因此我们使用 suspend_never 来指示它应该最初运行：

std::suspend_never initial_suspend() noexcept { return {}; }

注意我们在第 8.2.1 节中遇到的 noexcept ，当时我们编写了一个 hash 函数。永不挂起有时被称为热启动，而最初暂停协程则是冷启动。当我们完成时，我们总是挂起以标记我们已完成：

std::suspend_always final_suspend() noexcept { return {}; }

这在协程句柄上设置一个标志，以便 Task 可以查看协程是否已完成。

我们已经处理了协程的开始和结束，但尚未提供处理 co_await 、 co_yield 或 co_return 的代码。我们在列表 8.16 中的协程提供了玩家的选择和一个预测：

co_yield { player_choice , mr.get_prediction()};

因此，编译器会在我们的 promise_type 中寻找一个返回一对 int 的 yield_value 方法。如果我们不使用 co_yield ，就不需要这个方法。我们可以将 ints 的 std::pair 存储在 promise 中，以便 Task 可以访问它们并将它们返回给协程外部的代码。

在产生值后，我们暂停协程，并通过从 yield_value 方法返回 suspend_ always 来表示这一点：

std::suspend_always yield_value(std::pair<int, int> got)
{
    choice_and_prediction = got;
    return {};
}

控制随后返回到调用代码。

我们在玩家放弃时调用 co_return ，所以我们需要在 promise_type 中添加另一个函数。 co_return 可以是 void 或后面跟一个返回的表达式。我们的为 void ，所以我们需要一个 return_void 方法：

void return_void() {}

如果我们想返回一个值，我们需要一个 return_value 函数。我们的完整承诺类型如下。

清单 8.20 完整的承诺类型

struct promise_type
{
    std::pair<int, int> choice_and_prediction;                  ?
 
    Task get_return_object()                                    ?
    {
        return Task(this);
    }
    std::suspend_never initial_suspend() noexcept               ?
    { 
        return {};
    }   
    std::suspend_always final_suspend() noexcept                ?
    {
        return {};
    }   
    void unhandled_exception() {}                               ?
    std::suspend_always yield_value(std::pair<int, int> got)    ?
    {
        choice_and_prediction = got;
        return {};
    }
 
    void return_void() { }                                      ?
};

? 数据

? 创建任务

启动

? 停止

? 异常处理

? 由任务的 co_yield 调用

? 被任务的 co_return 调用

我们快完成了。 promise_type 现在拥有协程所需的所有方法。协程返回的 Task 为我们提供了一个指示承诺中数据的位置，并将恢复协程直到完成。让我们填补这些缺失的部分。

8.3.6 填写任务类型

为了从 Task 返回选择和预测，我们提供一个获取函数，从 promise_ptr 中获取 std::pair 的数据：

std::pair<int, int> choice_and_prediction() const
{
    return promise->choice_and_prediction;
}

我们可以通过调用句柄的 done 方法来检查协程是否完成。当 promise_type 的 final_suspend 方法被调用并返回 suspend_always 时，此标志被设置为 true。我们使用 from_promise 方法获取句柄，然后查看我们是否完成：

bool done() const
{
    auto handle =
        std::coroutine_handle<promise_type>::from_promise(*promise);
    return handle.done();
}

当我们在列表 8.16 中使用 co_yield 时，协程暂停。调用代码随后可以根据玩家的选择和心灵读者的预测进行操作，但它需要一种方法来恢复协程以获取下一对。我们通过调用句柄的 operator()() 来恢复协程。我们可以在我们的 Task 中添加一个名为 next 的函数，以恢复协程：

void next()
{ 
    auto handle =
         std::coroutine_handle<promise_type>::from_promise(*promise);
    handle();
}

调用代码可以在使用之前的选择和预测时调用 next 。将这些新方法添加到 Task ，我们得到了以下内容。

列表 8.21 协程的 Task 和 promise_type

struct Task                                         ?
{
    struct promise_type                             ?
    {
    // ...
    };
 
    std::pair<int, int> choice_and_prediction()     ?
    {
        return promise->choice_and_prediction;
    }
    bool done() const                               ?
    {
        auto handle =
            std::coroutine_handle<promise_type>::from_promise(*promise);
        return handle.done();
    }
    void next()                                     ?
    {
        auto handle =
            std::coroutine_handle<promise_type>::from_promise(*promise);
        return handle ();
    }
private:
    promise_ptr<promise_type> promise;              ?
    Task(promise_type* p) : promise(p) {}           ?
}; 

? 列表 8.16 中协程返回的任务

? promise_type 来自列表 8.20

? 让调用代码从 Promise 获取数据

? 让调用代码知道我们是否完成

恢复协程

智能指针用于 RAII

? 私有构造函数由 promise_type 可见

我们的 Task 现在已经完成，我们可以使用协程。

8.3.7 一个协程心灵读者

要使用我们的协程，我们可以使用类似于列表 8.14 中原始游戏的代码，但 MindReader 和用户输入现在被打包在 coroutine_game 内部。我们通过以下方式调用协程：

Task game = coroutine_game();

我们使用 Task 来控制协程。我们循环直到 done ，在每个回合获取玩家的选择和预测。这在 co_yield 暂停了协程。我们的调用代码随后重新获得控制并显示结果。通过在 Task 上调用 next ，控制然后返回到协程，并从中断的地方继续。我们的调用代码如下。

清单 8.22 一个心灵读者的协程版本

void coroutine_minder_reader()
{
    int turns = 0;
    int player_wins = 0;
 
    std::cout << "Select 0 or 1 at random and press enter.\n";
    std::cout << "If the computer predicts your guess it wins\n"
                         "and it can now read your mind.\n";
 
    Task game = coroutine_game();                     ?
 
    while (!game.done())                              ?
    {
        auto [player_choice, prediction] =
                    game.choice_and_prediction();     ?
        ++turns;
        std::cout << "You pressed " << player_choice
                  << ", I guessed " << prediction << '\n';
 
        if (player_choice != prediction)
        {
            ++player_wins;
        }
        game.next();                                  ?
    }
    std::cout << "you win " << player_wins << '\n'
        << "machine won " << (turns - player_wins) << '\n';
}

获取协程

? 检查用户是否停止

从协程获取数据

? 让协程恢复

使用协程对我们的心灵读者没有影响，但我们使用了 C++20 中一个经常讨论的特性。我们可以扩展这个，编写另一个协程来 co_await 从 std::cin 输入，返回一个随机翻转的函数，甚至另一个心灵读者。

协程可以在多种场合中使用，包括等待输入或其他资源的异步操作。Andreas Fertig 的书《使用 C++20 编程：概念、协程、范围等》（Fertig Publications，2021）有一章专门讲述如何使用协程解析字节流。他在 2022 年在 Overload 上发表了一篇概述（见 https://accu.org/journals/overload/30/168/fertig/）。Rayner Grimm 在他的博客上列出了几个可能的用例，包括事件驱动编程和协作多任务处理（见 http://mng.bz/qjPr）。如果一个协程被挂起，程序的其他部分可以运行，因此协程提供了一种受限的并发模型。

我们已经学习了许多 C++ 特性，快要结束了。我们已经多次使用了带参数包的模板，但还没有深入了解它们是如何工作的。让我们通过最后一章进一步探索模板，来结束我们的学习。

摘要

• 我们可以使用关键字 using 为声明创建别名，包括模板的家族。
• C++的无序容器使用哈希表。
• 哈希表将元素存储在桶中，并使用一个 hash 函数来定位桶。
• 一个 std::unordered_map 默认使用 std::hash 和 std::equal_to 作为键。
• 我们可以将一个 hash 函数注入到 namespace std 中，以支持在 std::unordered_map 中定义的用户类型。
• 一个 C++ 协程是一个包含以下三个关键字之一或多个的函数： co_yield ， co_await ，或 co_return 。
• 协程可以被挂起和恢复。
• 协程的返回类型通常是用户定义的类型，包含启动和停止协程所需的函数，以及根据需要支持 co_yield 和 co_await 的函数。
• C++23 引入了一个 std::generator 作为协程的返回类型，提供了一个潜在的无限序列，但对于其他用途，我们目前必须编写自己的 promise 或 task，提供所需的样板代码。
• 我们为 std::unique_ptr 使用了自定义删除器，以便我们能够使用零规则。