第十二章：协程和惰性生成器

目录

• 几个激励性示例 (A few motivating examples)
• 抽象化的协程 (The coroutine abstraction)
  • 子程序和协程 (Subroutines and coroutines)
  • 在 CPU 上执行子程序和协程 (Executing subroutines and coroutines on the CPU)
    • CPU 寄存器、指令和栈 (CPU registers, instructions, and the stack)
    • 调用和返回 (Call and return)
    • 暂停和恢复 (Suspend and resume)
    • 暂停和恢复无栈协程 (Suspending and resuming stackless coroutines)
  • 栈式协程与无栈协程
    • 性能成本 (Performance cost)
    • 内存占用 (Memory footprint)
    • 上下文切换 (Context switching)
  • 到目前为止您学到的内容
• 协程在 C++ 中
  • 标准 C++ 中包含哪些（不包含哪些）？
  • 什么使 C++ 函数成为协程？
  • 最小但完整的示例
    • 协程返回对象
    • 承诺类型
    • 可等待类型
    • 传递我们的协程
  • 协程状态的分配
  • 避免悬空引用
    • 向协程传递参数
    • 作为协程的成员函数 (Member functions that are coroutines)
    • 作为协程的 Lambdas
    • 防止悬空引用的指导原则
    • 错误处理 (Handling errors)
    • 定制点 (Customization points)
• 生成器 (Generators)
  • 实现一个生成器 (Implementing a generator)
  • 使用 Generator类
  • 解决生成器问题
    • 辅助函数：lin_value()
    • 1. 急切的线性范围
    • 2. 使用回调函数的惰性版本 (A lazy version using a callback)
    • 3. 迭代器实现 (An iterator implementation)
    • 4. 使用 Ranges 库的解决方案 (A solution using the Ranges library)
    • 5. 使用协程的解决方案 (A solution using a coroutine)
  • 结论 (Conclusion)
  • 使用生成器的真实世界示例
    • 问题描述 (The problem)
• 性能考虑
• 总结

计算已经成为一个充满等待的世界，我们的编程语言需要支持来表达这种等待。通常的想法是，每当程序执行到达一个我们知道可能需要等待某个事件的点时，就暂停（暂时中止）当前的流程，并将执行权交给其他流程。我们需要等待的这个“某事”可能是一个网络请求、用户的点击、一个数据库操作，甚至是一个耗时太长而我们无法阻塞的内存访问。相反，我们在代码中表明我们将要等待，继续执行其他流程，然后在准备就绪时再返回。协程使我们能够做到这一点。

在本章中，我们将主要关注添加到 C++20 中的协程。您将学习它们是什么、如何使用它们以及它们的性能特征。但我们也将花一些时间从更广泛的意义上研究协程，因为这个概念在许多其他语言中也很明显。

C++ 协程的标准库支持非常少。为协程添加标准库支持是 C++23 版本的一个高优先级特性。为了在日常代码中有效地使用协程，我们需要实现一些通用的抽象。本书将向您展示如何实现这些抽象，目的是学习 C++ 协程，而不是为您提供可用于生产的代码。

了解存在的各种类型协程、协程的用途以及促使 C++ 在语言中添加新特性来支持协程的原因也同样重要。

本章涵盖了大量内容。下一章也将讨论协程，但重点是异步应用。总而言之，本章将指导您完成以下内容：

• 关于协程的一般理论，包括有栈协程 (stackful coroutines) 和无栈协程 (stackless coroutines) 之间的区别，以及它们如何被编译器转换并在计算机上执行。
• C++ 中无栈协程的介绍。将讨论和演示 C++20 中使用 co_await、co_yield 和 co_return 对协程的新语言支持。
• 使用 C++20 协程作为生成器所需的抽象。
• 一些真实世界的示例，展示了使用协程在可读性和简洁性方面带来的好处，以及如何使用协程编写可以惰性求值的可组合组件。

如果您曾在其他语言中使用过协程，在阅读本章其余部分之前，您需要做好两方面的准备：

• 某些内容对您来说可能感觉很基础。尽管 C++ 协程工作原理的细节远非微不足道，但使用示例可能对您来说感觉很简单。
• 本章中我们将使用的一些术语（协程、生成器、任务等）可能与您目前对它们的理解不一致。

另一方面，如果您完全是协程的新手，本章的某些部分很可能看起来像魔法，需要一些时间来领会。因此，我将首先向您展示一些使用协程时 C++ 代码可能是什么样子的示例。

几个激励性示例 (A few motivating examples)

协程是那些与 Lambda 表达式相似的特性之一，它们提供了一种彻底改变我们编写和思考 C++ 代码的方式。这个概念非常通用，可以以多种不同的方式应用。为了让您体验一下使用协程时 C++ 是什么样子的，我们将在这里简要地看两个示例。

Yield 表达式可用于实现生成器——即惰性地生成值序列的对象。在这个例子中，我们将使用 co_yield 和 co_return 关键字来控制流程：

auto iota(int start) -> Generator<int> {
    for (int i = start; i < std::numeric_limits<int>::max(); ++i) {
        co_yield i;
    }
}

auto take_until(Generator<int>& gen, int value) -> Generator<int> {
    for (auto v : gen) {
        if (v == value) {
            co_return;
        }
        co_yield v;
    }
}

int main() {
    auto i = iota(2);
    auto t = take_until(i, 5);
    for (auto v : t) { // Pull values
        std::cout << v << ", ";
    }
    return 0;
}
// Prints: 2, 3, 4

在前面的示例中，iota() 和 take_until() 都是协程。iota() 生成一个整数序列，而 take_until() 交出值直到找到指定的值。Generator 模板是一种自定义类型，我将在本章后面向您展示如何设计和实现它。

构建生成器是协程的一个常见用例，另一个是实现异步任务。下一个示例将演示我们如何使用操作符 co_await 来等待某事而不阻塞当前执行的线程：

auto tcp_echo_server() -> Task<> {
    char data[1024];
    for (;;) {
        size_t n = co_await async_read(socket, buffer(data));
        co_await async_write(socket, buffer(data, n));
    }
}

co_await 不会阻塞，而是暂停执行，直到它被恢复并且异步的读取和写入函数完成。这里提供的示例是不完整的，因为我们不知道 Task、socket、buffer 以及异步 I/O 函数是什么。但是我们会在下一章关注异步任务时了解到它们。

如果此时您还不清楚这些示例是如何工作的，请不用担心——我们将在本章后面花大量时间深入研究细节。这些示例只是为了给您一个提示，让您了解如果您从未接触过协程，协程能让我们做什么。

在深入研究 C++20 协程之前，我们需要讨论一些术语和共同的基础知识，以便更好地理解在 2020 年向 C++ 添加一个相当复杂的语言特性的设计和动机。

抽象化的协程 (The coroutine abstraction)

我们现在退一步来讨论一般的协程，而不仅仅是关注添加到 C++20 中的协程。这将帮助您更好地理解协程的用途，以及存在哪些类型的协程及其区别。

如果您已经熟悉有栈协程 (stackful) 和无栈协程 (stackless)，以及它们的执行方式，您可以跳过本节，直接进入下一节“C++ 中的协程”。

协程的抽象概念已经存在了 60 多年，许多语言已将某种协程融入到它们的语法或标准库中。这意味着协程在不同的语言和环境中可能表示略有不同的事物。由于这是一本关于 C++ 的书，我将使用 C++ 标准中使用的术语。

协程与子程序 (subroutines) 非常相似。在 C++ 中，我们没有明确称为子程序的东西；相反，我们编写函数（例如，自由函数或成员函数）来创建子程序。我将普通函数 (ordinary functions) 和子程序 (subroutines) 互换使用。

子程序和协程 (Subroutines and coroutines)

为了理解协程和子程序（普通函数）之间的区别，我们将在这里重点关注子程序和协程最基本的属性，即如何启动、停止、暂停和恢复它们。当程序中其他部分调用子程序时，子程序就开始了。当子程序返回给调用者时，子程序就停止了：

auto subroutine() {
    // 语句序列 ...
    return; // 停止并将控制权返回给调用者
}

subroutine(); // 调用子程序以启动它
// 子程序已完成

子程序的调用链是严格嵌套的。在下图中，子程序 f() 必须等到子程序 g() 返回后才能返回到 main()：

协程也可以像子程序一样启动和停止，但它们还可以被暂停 (suspended) 和恢复 (resumed)。如果您以前没有使用过协程，这可能乍一看会觉得非常奇怪。协程被暂停和恢复的点称为暂停/恢复点 (suspend/resume point)。有些暂停点是隐式的，而有些则以某种方式在代码中明确标记。下面的伪代码显示了使用 await 和 yield 标记的三个显式暂停/恢复点：

// 伪代码
auto coroutine() {
    value = 10;
    await something; // 暂停/恢复点
    // ...
    yield value++;   // 暂停/恢复点
    yield value++;   // 暂停/恢复点
    // ...
    return;
}

auto res = coroutine(); // 调用 (Call)
res.resume();           // 恢复 (Resume)

在 C++ 中，显式暂停点使用关键字 co_await 和 co_yield 标记。下图显示了协程如何从一个子程序中调用，然后稍后从代码的不同部分恢复：

协程内部局部变量的状态在协程暂停期间是被保留的。这些状态属于协程的特定调用实例。也就是说，它们不像静态局部变量那样，静态局部变量是在函数的所有调用之间全局共享的。

总结一下，协程是也可以被暂停和恢复的子程序。另一种看待它的方式是说，子程序是不能被暂停或恢复的协程的特化。

从现在开始，我将严格区分调用 (call) 和恢复 (resume)，以及暂停 (suspend) 和返回 (return)。它们意味着完全不同的事情。调用协程会创建一个可以被暂停和恢复的新的协程实例。返回协程会销毁协程实例，并且它不能再被恢复。

要真正理解协程如何帮助我们编写高效的程序，您需要了解一些关于 C++ 中函数通常如何转换为机器代码并随后执行的底层细节。

在 CPU 上执行子程序和协程 (Executing subroutines and coroutines on the CPU)

我们在本书中讨论了内存层次结构、缓存、虚拟内存、线程调度以及其他硬件和操作系统概念。但我们还没有真正讨论指令是如何使用 CPU 寄存器和栈在 CPU 上执行的。在比较子程序与各种类型的协程时，理解这些概念很重要。

CPU 寄存器、指令和栈 (CPU registers, instructions, and the stack)

本节将提供一个非常简化的 CPU 模型，目的是理解上下文切换、函数调用以及一些关于调用栈的更多细节。当我在这里说 CPU 时，我指的是类似于配备多个通用寄存器的 x86 系列 CPU。

程序包含 CPU 执行的一系列指令。指令序列存储在计算机的某个内存中。CPU 通过一个名为程序计数器 (Program Counter, PC) 的寄存器来跟踪当前正在执行指令的地址。通过这种方式，CPU 知道下一条要执行的指令是什么。

CPU 包含固定数量的寄存器 (registers)。寄存器类似于具有预定义名称的变量，可以存储一个值或一个内存地址。寄存器是计算机上可用的最快数据存储，并且位于离 CPU 最近的位置。当 CPU 操纵数据时，它使用寄存器。有些寄存器对 CPU 具有特殊含义，而其他寄存器则可以被当前正在执行的程序更自由地使用。

对 CPU 具有特殊含义的两个非常重要的寄存器是：

• 程序计数器 (PC): 存储当前正在执行指令的内存地址的寄存器。每当执行一条指令时，这个值都会自动递增。有时它也被称为指令指针 (instruction pointer)。
• 栈指针 (Stack Pointer, SP): 存储当前使用的调用栈 (call stack) 顶部的地址。分配和释放栈内存只是改变存储在这个单个寄存器中的值。

假设寄存器如上图所示被命名为 R0、R1、R2 和 R3。一个典型的算术指令可能如下所示：

add 73, R1 // 将 73 加到存储在 R1 中的值

数据也可以在寄存器和内存之间复制：

mov SP, R2 // 将栈指针地址复制到 R2
mov R2, [R1] // 将 R2 的值复制到存储在 R1 中的内存地址

一组指令隐式地引用调用栈。CPU 通过栈指针知道调用栈的顶部在哪里。在栈上分配内存只是更新栈指针的问题。该值会增加或减少，具体取决于栈是朝高地址还是低地址增长。

下面的指令使用了栈：

push R1 // 将 R1 的值推入栈顶

push 指令将寄存器中的值复制到栈指针指向的内存位置，并递增（或递减）栈指针。

我们也可以使用 pop 指令从栈中弹出值，该指令也会读取并更新栈指针：

pop R2 // 从栈中弹出值到 R2

每当执行一条指令时，CPU 都会自动递增程序计数器。但程序计数器也可以通过指令显式更新，例如 jump 指令：

jump R3 // 将程序计数器设置为 R3 中的地址

CPU 可以以两种模式运行：用户模式 (user mode) 或内核模式 (kernel mode)。CPU 寄存器在用户模式和内核模式下运行时有不同的用途。当 CPU 在用户模式下执行时，它以受限的权限运行，无法访问硬件。操作系统提供在内核模式下运行的系统调用 (system calls)。因此，像 std::puts() 这样将值打印到标准输出的 C++ 库函数必须进行一次系统调用才能完成其任务，这迫使 CPU 在用户模式和内核模式之间切换。

在用户模式和内核模式之间转换是昂贵的。要理解原因，让我们再次思考我们的示意性 CPU。CPU 通过使用其寄存器高效地运行，从而避免不必要地将值溢出到栈上。但 CPU 是所有用户进程和操作系统之间的共享资源，每当我们需要在任务之间切换时（例如，进入内核模式时），处理器状态，包括其所有寄存器，都需要被保存到内存中，以便稍后可以恢复。

调用和返回 (Call and return)

既然您对 CPU 如何使用寄存器和栈有了基本的了解，我们就可以讨论子程序调用了。调用和从子程序返回涉及许多我们可能认为理所当然的机制。我们的编译器在将 C++ 函数转换为高度优化的机器代码时做得非常出色。

以下列表显示了在调用、执行和从子程序返回时需要考虑的方面：

• 调用和返回（在代码中的不同点之间跳转）。
• 传递参数——参数可以通过寄存器或在栈上传递，或两者兼有。
• 在栈上为局部变量分配存储空间。
• 返回一个值——从子程序返回的值需要存储在一个调用者可以找到的地方。通常，这是一个专用的 CPU 寄存器。
• 使用寄存器而不干扰其他函数——子程序使用的寄存器需要在返回之前恢复到调用子程序之前的状态。

关于函数调用如何执行的确切细节由称为调用约定 (calling conventions) 的东西指定。它们提供了一个协议，供调用者/被调用者就谁负责哪部分达成一致。调用约定因 CPU 架构和编译器而异，是构成应用二进制接口 (Application Binary Interface, ABI) 的主要部分之一。

当一个函数被调用时，会为该函数创建一个调用帧 (call frame)（或活动帧 (activation frame)）。调用帧包含：

• 传递给函数的参数。
• 函数的局部变量。
• 我们打算使用并因此需要在返回前恢复的寄存器快照。
• 一个返回地址 (return address)，链接回调用者调用函数的内存位置。
• 一个可选的帧指针 (frame pointer)，指向调用者调用帧的顶部。帧指针对于调试器检查栈很有用。在本书中我们将不再进一步讨论帧指针。

由于子程序的严格嵌套性，我们可以将子程序的调用帧保存在栈上，以非常高效地支持嵌套调用。存储在栈上的调用帧通常被称为栈帧 (stack frame)。

下图显示了调用栈上的多个调用帧，并突出显示了单个调用帧的内容：

当一个子程序返回给它的调用者时，它使用返回地址知道跳转到哪里，恢复它已更改的寄存器，并从栈上弹出（释放）整个调用帧。通过这种方式，栈和寄存器都被恢复到调用子程序之前它们所处的状态。然而，有两个例外。首先，程序计数器 (PC) 已经移动到调用之后的指令。其次，向其调用者返回值子程序通常将该值存储在一个专用寄存器中，调用者知道在哪里可以找到它。

在理解了子程序是如何通过临时使用栈，然后在将控制权返回给调用者之前恢复 CPU 寄存器来执行之后，我们现在可以开始研究如何暂停和恢复协程。

暂停和恢复 (Suspend and resume)

考虑以下定义了多个暂停/恢复点的协程的伪代码：

// 伪代码
auto coroutine() {
    auto x = 0;
    yield x++; // 暂停 (Suspend)
    g();       // 调用其他函数 (Call some other function)
    yield x++; // 暂停 (Suspend)
    return;    // 返回 (Return)
}

auto co = coroutine(); // 调用子程序以启动它 (Call subroutine to start it)
// ...                   // 协程被暂停 (Coroutine is suspended)
auto a = resume(co);   // 恢复协程以获取下一个值 (Resume coroutine to get next value)
auto b = resume(co);   // 恢复协程以获取下一个值 (Resume coroutine to get next value)

当 coroutine() 暂停时，我们不能再像子程序返回给调用者时那样移除调用帧。为什么？因为我们需要保留变量 x 的当前值，并且还需要记住下一次协程恢复时应该在协程的哪个位置继续执行。此信息被放置在一个称为协程帧 (coroutine frame) 的东西中。协程帧包含恢复一个已暂停协程所需的所有信息。然而，这引发了几个新问题：

• 协程帧存储在哪里？
• 协程帧有多大？
• 当一个协程调用一个子程序时，它需要一个栈来管理嵌套的调用帧。如果我们尝试从嵌套调用帧中恢复会发生什么？那么当协程恢复时，我们需要恢复整个栈。
• 调用和从协程返回的运行时开销是多少？
• 暂停和恢复协程的运行时开销是多少？

对这些问题的简短回答是：这取决于我们正在讨论哪种类型的协程：有栈协程还是无栈协程。

有栈协程有一个单独的侧栈 (side stack)（类似于线程），其中包含协程帧和嵌套的调用帧。这使得从嵌套调用帧中暂停成为可能：

暂停和恢复无栈协程 (Suspending and resuming stackless coroutines)

无栈协程需要将协程帧存储在其他地方（通常在堆 (heap) 上），然后使用当前正在执行线程的栈来存储嵌套的调用帧。

但这并不是全部真相。调用者负责创建调用帧，保存返回地址（程序计数器的当前值）和栈上的参数。调用者不知道它正在调用的协程会暂停和恢复。因此，协程本身需要在被调用时创建协程帧，并将参数和寄存器从调用帧复制到协程帧：

当协程最初暂停时，协程的栈帧会从栈上弹出，但协程帧会继续存活。协程帧的内存地址（句柄/指针）被返回给调用者：

要恢复协程，调用者使用它先前收到的句柄，并调用一个 resume 函数并将协程句柄作为参数传递。resume 函数使用存储在协程帧中的暂停/恢复点来继续执行协程。对 resume 函数的调用也是一个普通函数调用，它将生成一个栈帧，如下图所示：

最后，当协程返回时，它通常会暂停并最终被释放。栈的状态如下图所示：

无栈协程没有为每个协程调用提供单独的侧栈，由此带来的一个重要后果是，当无栈协程暂停时，栈上不能留下任何嵌套的调用帧。请记住，当控制权转移回调用者时，调用者的调用帧必须位于栈的顶部。

作为最后一点说明，还应该提到，在某些情况下，协程帧所需的内存可以在调用者的调用帧内部分配。当我们查看 C++20 协程时，我们将更详细地讨论这一点。

栈式协程与无栈协程

如前一节所述，无栈协程（stackless coroutines）使用当前运行线程的栈来处理嵌套的函数调用。这带来的结果是，无栈协程永远不能从嵌套的调用帧中暂停。

有栈协程（stackful coroutines）有时被称为 纤程（fibers），在 Go 编程语言中，它们被称为 goroutines。有栈协程让人们联想到线程，因为每个线程都管理自己的栈。然而，有栈协程（或纤程）与操作系统线程之间有两个主要区别：

• 操作系统线程由内核调度，并且在两个线程之间切换是一个内核模式操作。
• 大多数操作系统是抢占式地切换操作系统线程（线程被调度器中断），而两个纤程之间的切换是协作式发生的。一个正在运行的纤程会一直运行，直到它将控制权移交给某个管理器，然后该管理器才能调度另一个纤程。

还有一类线程被称为用户级线程（user-level threads）或绿色线程（green threads）。这些是轻量级线程，不涉及内核模式切换（因为它们在用户模式下运行，因此内核不知情）。纤程是用户级线程的一个例子。但用户级线程也可能被用户库或虚拟机抢占式调度。Java 线程就是抢占式用户级线程的一个例子。【译注：这是早期的情况，现代JVM创建的线程和OS线程是一对一的。】

无栈协程也允许我们编写和组合多个并发运行的任务，而无需为每个流程提供单独的侧栈。无栈协程与状态机（state machines）紧密相关。 可以将状态机转换为协程，反之亦然。为什么了解这一点很有用？首先，它能让您更好地理解无栈协程是什么。其次，如果您已经擅长识别可以使用状态机解决的问题，您就可以更容易地看出协程何时能作为合适的解决方案。状态机是非常通用的抽象，可以应用于各种各样的问题。然而，状态机通常应用于的一些领域包括解析（parsing）、手势识别和 I/O 多路复用等。这些都是无栈协程在表达能力和性能方面都能真正发光发热的领域。

性能成本 (Performance cost)

协程是一种抽象，它允许我们以清晰简洁的方式编写惰性求值代码和异步程序。但创建和销毁协程以及暂停和恢复协程都存在性能成本。在比较无栈协程和有栈协程的性能成本时，需要解决两个主要方面：内存占用和上下文切换。

内存占用 (Memory footprint)

有栈协程需要一个单独的调用栈，以便处理从嵌套调用帧中暂停的情况。因此，在调用协程时，我们需要为这个新的侧栈动态分配一块内存。这立即提出了一个问题：我们需要分配多大的栈？除非我们对协程及其嵌套调用帧可以消耗多少栈内存有一些策略，否则我们可能需要分配一个与线程的正常调用栈大小近似的栈。

一些实现尝试了分段栈（segmented stack），它允许栈在必要时增长。另一种替代方案是从一个小的连续栈开始，然后在需要时将栈复制到一个更大的新分配的内存区域（类似于 std::vector 的增长方式）。Go 语言中的协程实现（goroutines）已从使用分段栈转向使用动态增长的连续栈。

无栈协程不需要为单独的侧栈分配内存。相反，它们只需要一次分配来存储每个协程帧（coroutine frame），以便支持暂停和恢复。这种分配发生在协程被调用时（而不是在暂停/恢复时）。协程帧在协程返回时被释放。

总而言之，有栈协程需要为协程帧和侧栈进行较大的初始内存分配，或需要支持栈增长。无栈协程只需要为协程帧分配内存。调用协程的内存占用可以概括如下：

• 无栈： 协程帧
• 有栈： 协程帧 + 调用栈

性能成本的下一个方面与暂停和恢复协程有关。

上下文切换 (Context switching)

上下文切换可能发生在不同的级别。一般来说，上下文切换发生在我们需要 CPU 在两个或多个正在进行的任务之间切换时。即将暂停的任务需要保存 CPU 的整个状态，以便稍后可以恢复。

在不同进程和操作系统线程之间切换是相当昂贵的操作，涉及系统调用，需要 CPU 进入内核模式。内存缓存会被失效，并且对于进程切换，包含虚拟内存和物理内存之间映射的表需要被替换。

暂停和恢复协程也是一种上下文切换，因为我们正在在多个并发流程之间切换。协程之间的切换比进程和操作系统线程之间的切换快得多，部分原因是它不涉及任何需要 CPU 在内核模式下运行的系统调用。

然而，在有栈协程和无栈协程之间切换时仍然存在差异。有栈协程与无栈协程的上下文切换相对运行时性能可能取决于调用模式。但是，一般来说，有栈协程的上下文切换操作更昂贵，因为它在暂停和恢复期间需要保存和恢复比无栈协程更多的信息。恢复无栈协程与普通的函数调用相当。

无栈与有栈的争论在 C++ 社区已经持续了好几年，我将尽力远离这场争论，得出结论是它们都有合理的用例——有些用例会倾向于有栈协程，而另一些用例会倾向于无栈协程。

本节稍微绕了个弯，目的是让您更好地了解协程的执行和性能。让我们简短回顾一下您学到的内容。

到目前为止您学到的内容

协程是可以暂停和恢复的函数。普通函数不具备此能力，这使得可以移除返回的函数的调用帧。然而，一个被暂停的协程需要保持调用帧存活，以便在它被恢复时能够恢复协程的状态。

协程比子程序更强大，并且在生成的机器代码中涉及更多的簿记工作。然而，由于协程与普通函数之间的紧密关系，如今的编译器非常擅长优化无栈协程。

有栈协程可以被视为非抢占式用户级线程，而无栈协程提供了一种使用 await 和 yield 关键字来指定暂停点，以直接命令式方式编写状态机的方法。

在对一般协程抽象进行介绍之后，现在是时候了解 C++ 中无栈协程是如何实现的了。

协程在 C++ 中

添加到 C++20 中的协程是无栈协程。通过使用第三方库，C++ 也有使用有栈协程的选项。最著名的跨平台库是 Boost.Fiber。C++20 无栈协程引入了新的语言构造，而 Boost.Fiber 是一个可用于 C++11 及更高版本的库。在本书中，我们将不再进一步讨论有栈协程，而是专注于已在 C++20 中标准化的无栈协程。

C++20 中的无栈协程设计遵循以下目标：

• 可扩展性（Scalable）：它们的内存开销极小。这使得存活的协程数量可以远多于存活的线程或有栈协程的数量。
• 高效的上下文切换（Efficient context switching）：这意味着暂停和恢复一个协程应该几乎与普通的函数调用一样便宜。
• 高度灵活性（Highly flexible）：C++ 协程拥有超过 15 个定制点（customization points），这为应用程序开发人员和库编写者提供了极大的自由来配置和塑造协程。关于协程应如何工作的决策可以由我们开发人员决定，而不是硬编码在语言规范中。一个例子是协程在被调用后是应该立即暂停，还是继续执行到第一个显式暂停点。这类问题在其他语言中通常是硬编码的，但在 C++ 中，我们可以使用定制点来定制这种行为。
• 不要求 C++ 异常来处理错误：这意味着您可以在关闭异常的环境中使用协程。请记住，协程是一种可与普通函数相媲美的底层功能，这在嵌入式环境和具有实时要求的系统中非常有用。

考虑到这些目标，C++ 协程乍一看有点复杂也就不足为奇了。

标准 C++ 中包含哪些（不包含哪些）？

一些 C++ 特性是纯库特性（例如 Ranges 库），而其他特性是纯语言特性（例如借助 auto 关键字进行的类型推导）。然而，有些特性需要对核心语言和标准库都进行添加。C++ 协程就是这些特性之一；它们引入了新的语言关键字，但也向标准库添加了新的类型。

在语言方面，回顾一下，我们有以下与协程相关的关键字：

• co_await：一个操作符，用于暂停当前协程。
• co_yield：向调用者返回值并暂停协程（用于生成器）。
• co_return：完成协程的执行，并且可以选择性地返回值。

在库方面，有一个新的 <coroutine> 头文件，包括以下内容：

• std::coroutine_handle：一个模板类，引用协程状态，实现协程的暂停和恢复。
• std::suspend_never：一个琐碎的可等待类型（trivial awaitable type），它从不暂停。
• std::suspend_always：一个琐碎的可等待类型，它总是暂停。
• std::coroutine_traits：用于定义协程的承诺类型（promise type）。

C++20 附带的库类型是绝对最小集。例如，用于协程和调用者之间通信的基础设施不属于 C++ 标准。为了在我们的应用程序代码中有效使用协程所需的一些类型和函数已经在新的 C++ 提案中被提出，例如模板类 task 和 generator 以及函数 sync_wait() 和 when_all()。C++ 协程的库部分很可能会在 C++23 中得到补充。

在本书中，我将提供一些简化的类型来填补这个空白，而不是使用第三方库。通过实现这些类型，您将深入理解 C++ 协程是如何工作的。然而，设计可与协程一起使用的健壮库组件非常困难，很容易引入生命周期问题。因此，如果您计划在当前项目中使用协程，使用第三方库可能比从头开始实现它们是更好的选择。在撰写本书时，CppCoro 库是这些通用原语的事实标准。该库由 Lewis Baker 创建，可在 https://github.com/lewissbaker/cppcoro 上获取。

什么使 C++ 函数成为协程？

如果一个 C++ 函数包含关键字 co_await、co_yield 或 co_return 中的任何一个，那么它就是一个协程。此外，编译器对协程的返回类型提出了特殊要求。尽管如此，我们需要检查函数定义（函数体）而不仅仅是声明，才能知道我们面对的是协程还是普通函数。这意味着协程的调用者不需要知道它调用的是协程还是普通函数。

与普通函数相比，协程还有以下限制：

• 协程不能使用可变参数，例如 f(const char*...)。
• 协程不能返回 auto 或概念类型：auto f()。
• 协程不能声明为 constexpr。
• 构造函数和析构函数不能是协程。
• main() 函数不能是协程。

一旦编译器确定一个函数是协程，它就会将协程与一些类型关联起来，以使协程机制正常工作。下图突出显示了调用者使用协程时所涉及的不同组件：

调用者 (Caller) 和协程 (Coroutine) 是我们通常在应用程序代码中实现的实际函数。

返回对象 (Return Object) 是协程返回的类型，通常是一个为特定用例（例如生成器或异步任务）设计的通用类模板。调用者与返回对象交互以恢复协程并获取从协程中发出的值。返回对象通常将其所有调用委托给协程句柄。

协程句柄 (Coroutine Handle) 是协程状态的非拥有句柄。通过协程句柄，我们可以恢复和销毁协程状态。

协程状态 (Coroutine State) 就是我前面提到的协程帧。它是一个不透明对象（opaque object），这意味着我们不知道它的大小，并且除了通过句柄之外，我们无法以任何其他方式访问它。协程状态存储了恢复协程在上次暂停的位置所需的一切必要信息。协程状态还包含承诺对象（Promise）。

承诺对象 (Promise Object) 是协程本身通过关键字 co_await、co_yield 和 co_return 间接通信的对象。如果值或错误是从协程提交的，它们将首先到达承诺对象。承诺对象充当协程和调用者之间的通道，但两者都不能直接访问承诺。

诚然，这乍一看可能相当密集。一个完整但最小的示例将帮助您更好地理解不同的部分。

最小但完整的示例

让我们从一个最小的示例开始，以便理解协程是如何工作的。

首先，我们实现一个在返回之前被暂停和恢复的小协程：

auto coroutine() -> Resumable { // Initial suspend (初始暂停)
    std::cout << "3 ";
    co_await std::suspend_always{}; // Suspend (explicit) (显式暂停)
    std::cout << "5 ";
} // Final suspend then return (最终暂停然后返回)

其次，我们创建协程的调用者。请注意此程序的输出和控制流。代码如下：

int main() {
    std::cout << "1 ";
    auto resumable = coroutine(); // Create coroutine state (创建协程状态)
    std::cout << "2 ";
    resumable.resume(); // Resume (恢复)
    std::cout << "4 ";
    resumable.resume(); // Resume (恢复)
    std::cout << "6 ";
} // Destroy coroutine state (销毁协程状态)
// Outputs: 1 2 3 4 5 6

第三，协程的返回对象 Resumable 需要被定义：

class Resumable { // The return object (返回对象)
private:
    struct Promise { /*...*/ }; // Nested class, see below (嵌套类，见下文)
    std::coroutine_handle<Promise> h_;
    explicit Resumable(std::coroutine_handle<Promise> h) : h_{h} {}

public:
    using promise_type = Promise;
    
    // 移动构造函数：确保源对象句柄被清除
    Resumable(Resumable&& r) : h_{std::exchange(r.h_, {})} {}
    
    // 析构函数：负责销毁协程状态
    ~Resumable() { if (h_) { h_.destroy(); } }
    
    // 恢复协程
    bool resume() {
        if (!h_.done()) { h_.resume(); }
        return !h_.done();
    }
};

最后，承诺类型被实现为 Resumable 内部的一个嵌套类，像这样：

struct Promise {
    // 1. 生成返回对象 (返回给调用者的 Resumable 实例)
    Resumable get_return_object() {
        using Handle = std::coroutine_handle<Promise>;
        // 从承诺对象获取协程句柄
        return Resumable{Handle::from_promise(*this)};
    }
    
    // 2. 初始暂停行为：总是暂停
    auto initial_suspend() { return std::suspend_always{}; }
    
    // 3. 最终暂停行为：总是暂停
    auto final_suspend() noexcept { return std::suspend_always{}; }
    
    // 4. 处理 co_return; (不带值)
    void return_void() {}
    
    // 5. 处理未捕获的异常
    void unhandled_exception() { std::terminate(); }
};

这个示例是最小的，但它涉及了许多值得注意和需要理解的事情：

• 函数 coroutine() 是一个协程，因为它包含了使用 co_await 的显式暂停/恢复点。
• 协程没有生成任何值，但仍需要返回一个带有特定约束的类型（Resumable），以便调用者可以恢复协程。
• 我们使用了名为 std::suspend_always 的可等待类型。
• resumable 对象的 resume() 函数从协程暂停的点恢复协程。
• Resumable 是协程状态的所有者。当 Resumable 对象被析构时，它使用 coroutine_handle 销毁协程。

调用者、协程、协程句柄、承诺和可恢复对象之间的关系如下图所示：

现在是时候更仔细地看看每个部分了。我们从 Resumable 类型开始。

协程返回对象

我们的协程返回一个 Resumable 类型的对象。这个 Resumable 类非常简单。它是协程返回的对象，调用者可以使用它来恢复和销毁协程。为了方便，我们再次给出完整的定义：

class Resumable { // The return object
private:
    struct Promise { /*...*/ }; // Nested class
    std::coroutine_handle<Promise> h_;
    explicit Resumable(std::coroutine_handle<Promise> h) : h_{h} {}
public:
    using promise_type = Promise;
    
    Resumable(Resumable&& r) : h_{std::exchange(r.h_, {})} {}
    ~Resumable() { if (h_) { h_.destroy(); } }
    
    bool resume() {
        if (!h_.done()) { h_.resume(); }
        return !h_.done();
    }
};

Resumable 是一个仅可移动（move-only）类型，它是协程句柄的所有者（因此控制着协程的生命周期）。移动构造函数通过使用 std::exchange() 确保源对象中的协程句柄被清除。当一个 Resumable 对象被析构时，如果它仍然拥有协程，它就会销毁协程。

resume() 成员函数在协程仍存活时，将恢复调用委托给协程句柄。

为什么我们需要在 Resumable 内部有成员类型别名 promise_type = Promise？

每个协程都有一个关联的承诺对象。当编译器看到一个协程时（通过检查函数体），它需要确定关联的承诺类型。为此，编译器使用 std::coroutine_traits<T> 模板，其中 T 是协程的返回类型。您可以为 std::coroutine_traits<T> 提供一个模板特化，或者利用默认实现 std::coroutine_traits 会在协程的返回类型 T 中查找名为 promise_type 的公共成员类型或别名这一事实。在我们的例子中，Resumable::promise_type 是 Promise 的别名。

【译注：

如果你不使用成员类型别名 using promise_type = Promise;，而是选择特化 std::coroutine_traits 来让编译器知道协程的承诺类型 (Promise Type)，你应该这样写：

假设你的协程返回类型是 Resumable，而承诺类型是 Resumable::Promise。特化必须在全局命名空间中，并与 <coroutine> 头文件一起使用。

首先，移除 Resumable 类中的 using promise_type = Promise;：

class Resumable { // The return object
private:
    // 将 Promise 定义为 Resumable 的内部结构
    struct Promise { /*...*/ }; 
    std::coroutine_handle<Promise> h_;
    explicit Resumable(std::coroutine_handle<Promise> h) : h_{h} {}
public:
    // **注意：这里移除了 using promise_type = Promise;**
    
    Resumable(Resumable&& r) : h_{std::exchange(r.h_, {})} {}
    ~Resumable() { if (h_) { h_.destroy(); } }
    
    // ... 其他成员函数 ...
};

接下来，你在全局命名空间中为 std::coroutine_traits 提供一个特化，将返回类型 Resumable 映射到正确的承诺类型 Resumable::Promise：

#include <coroutine>

// 假设 Resumable 和其内部的 Promise 结构体已定义

// 在 std 命名空间内特化 std::coroutine_traits
namespace std {
    
    // T 是协程的返回类型 (Resumable)
    // Args 是协程的参数列表（空或实际参数）
    template<typename... Args>
    struct coroutine_traits<Resumable, Args...> {
        
        // 显式指定该返回类型对应的承诺类型
        using promise_type = Resumable::Promise;
    };
    
} // namespace std

工作原理

1. 当编译器看到一个协程函数：

   auto coroutine() -> Resumable { /* ... */ }
   

2. 它知道返回类型是 Resumable 并且没有参数（或有参数）。
3. 编译器查找 std::coroutine_traits<Resumable>（或带有参数的特化）。
4. 由于找到了你提供的特化，编译器读取 using promise_type = Resumable::Promise;。
5. 编译器因此知道协程状态中需要嵌入 Resumable::Promise 类型的承诺对象，并使用这个承诺对象来生成协程的机器码。

总结： std::coroutine_traits 的特化是机制的底层，它允许库设计者将任何返回类型（T）映射到任何承诺类型（Promise Type），即使返回类型本身没有提供 promise_type 别名。

】

承诺类型

承诺类型（Promise type）控制着协程的行为。同样，为了方便，这里再次给出完整的定义：

struct Promise {
    auto get_return_object() { return Resumable{*this}; }
    auto initial_suspend() { return std::suspend_always{}; }
    auto final_suspend() noexcept { return std::suspend_always{}; }
    void return_void() {}
    void unhandled_exception() { std::terminate(); }
};

我们不应该直接调用这些函数；相反，当编译器将协程转换为机器代码时，它会插入对承诺对象的调用。如果我们不提供这些成员函数，编译器就不知道如何为我们生成代码。您可以将承诺视为一个协程控制器对象，它负责：

• 生成从协程调用返回的值。 这由 get_return_object() 函数处理。
• 通过实现 initial_suspend() 和 final_suspend() 函数来定义协程被创建和被销毁之前的行为。 在我们的 Promise 类型中，我们通过返回 std::suspend_always（见下一节）来表明协程应该在这些点暂停。
• 定制协程最终返回时的行为。 如果协程使用带有求值为 T 类型的值的 co_return 表达式，则承诺必须定义一个名为 return_value(T) 的成员函数。我们的协程不返回值，但 C++ 标准要求我们提供名为 return_void() 的定制点，我们在这里将其留空。
• 处理协程体内部未处理的异常。 在 unhandled_exception() 函数中，我们简单地调用 std::terminate()，但在后面的示例中，我们将更优雅地处理它。

代码中还有一些最后的部分需要更多关注，即 co_await 表达式和可等待类型。

可等待类型

我们在代码中使用了 co_await 添加了一个显式暂停点，并向它传递了可等待类型 std::suspend_always 的实例。std::suspend_always 的实现看起来像这样：

struct std::suspend_always {
    // 总是返回 false，表示“尚未准备好”，因此必须暂停
    constexpr bool await_ready() const noexcept { return false; }
    
    // 在暂停时被调用 (在这里为空，因为不需要额外的操作)
    constexpr void await_suspend(coroutine_handle<>) const noexcept {}
    
    // 在协程恢复时被调用 (在这里为空，因为不需要返回数据)
    constexpr void await_resume() const noexcept {}
};

std::suspend_always 被称为琐碎的可等待类型（trivial awaitable type），因为它总是报告它尚未准备好，从而总是使协程暂停。还有另一种琐碎的可等待类型，它总是报告它已准备好，称为 std::suspend_never：

struct std::suspend_never {
    // 总是返回 true，表示“已准备好”，因此不暂停
    constexpr bool await_ready() const noexcept { return true; }
    constexpr void await_suspend(coroutine_handle<>) const noexcept {}
    constexpr void await_resume() const noexcept {}
};

我们可以创建自己的可等待类型，我们将在下一章介绍，但现在我们可以使用这两个琐碎的标准类型。

这就完成了这个示例。但是当我们有了 Promise 和 Resumable 类型后，我们可以做更多的实验。让我们看看我们能用一个已启动的协程做些什么。

传递我们的协程

一旦 Resumable 对象被创建，我们可以将它传递给其他函数并从那里恢复它。我们甚至可以将协程传递给另一个线程。以下示例展示了这种灵活性的一部分：

auto coroutine() -> Resumable {
    std::cout << "c1 ";
    co_await std::suspend_always{};
    std::cout << "c2 ";
}

auto coro_factory() { // Create and return a coroutine
    auto res = coroutine();
    return res;
}

int main() {
    auto r = coro_factory();
    r.resume(); // Resume from main (在主线程恢复)
    
    auto t = std::jthread{[r = std::move(r)]() mutable {
        using namespace std::chrono_literals;
        std::this_thread::sleep_for(2s);
        r.resume(); // Resume from thread (在另一个线程恢复)
    }};
}

【译注：

r = std::move(r) mutable的作用。

这段代码片段使用了 C++11 引入的 Lambda 表达式和 C++14 增强的泛型捕获（Generic Lambda Capture）功能，目的是将一个不可复制但可移动的对象安全地传递给新的线程。

[r = std::move(r)] 解释

这部分代码是 std::thread 构造函数中 Lambda 表达式的捕获列表。

Lambda 表达式通过捕获列表 ([...]) 访问其外部作用域中的变量。通常的捕获方式是按值复制 ([r]) 或按引用 ([&r])。

r = std::move(r)：移动捕获 (Move Capture)

这种语法被称为移动捕获或初始化捕获，其工作机制如下：

为什么要使用移动捕获？

在这个特定的协程示例中，移动捕获是必需的，原因如下：

• 资源所有权： r 是一个 Resumable 类型的对象，它拥有协程状态的句柄 (h_)，负责在析构时销毁协程。它是一个资源管理对象，通常被设计为不可复制（Non-copyable）。
• 线程要求： std::thread 的构造函数会将参数复制到新线程的存储空间。由于 Resumable 不可复制，标准的按值捕获 [r] 会失败。
• 安全转移： 通过 [r = std::move(r)]，我们安全地将协程句柄的所有权从主线程的 r 变量转移给了新线程的 Lambda 内部的 r 变量。 原始的 r 变量现在为空（因为移动构造函数将它重置了），而新线程中的 Lambda 拥有了句柄，并最终负责在其退出时销毁协程（通过析构函数）。

简而言之，[r = std::move(r)] 是将资源所有权从主线程转移到子线程的规范且安全的方法，特别是对于不可复制的类型。

值得注意的是，Lambda 表达式中紧跟的 mutable 关键字也是必需的，因为它允许你在按值捕获的变量（包括移动捕获）上执行非 const 操作。在这里，它允许你在 Lambda 内部调用 r.resume()，即使 std::thread 最终会以 const 方式存储 Lambda 对象。

】

前面的示例演示了，一旦我们调用了协程并获得了它的句柄，我们就可以像任何其他可移动类型一样移动它。这种将其传递给其他线程的能力在我们需要避免在特定线程上进行协程状态可能的堆分配的情况下非常有用。

协程状态的分配

协程状态（coroutine state）或协程帧（coroutine frame）是协程在暂停时存储其状态的地方。

协程状态的生命周期始于协程被调用，结束于协程执行 co_return 语句（或控制流到达协程体的末尾），除非它通过协程句柄 (coroutine handle) 被提前销毁。

协程状态通常分配在堆上。编译器会插入一次单独的堆分配操作。不过，在某些情况下，可以通过将协程状态内联到调用者（caller）的帧中（这可能是一个普通栈帧或另一个协程帧），从而消除（elide）这次单独的堆分配。不幸的是，这种堆分配的消除永远没有保证。

为了使编译器能够消除堆分配，协程状态的完整生命周期必须严格嵌套在调用者的生命周期内。此外，编译器需要确定协程状态的总大小，并且通常需要可见被调用协程的函数体，以便对其部分进行内联。像虚函数调用、调用位于其他翻译单元或共享库中的函数等情况通常会使这种消除变得不可能。如果编译器缺少所需的信息，它就会插入堆分配。

协程状态的堆分配是通过 operator new 执行的。可以在承诺类型（promise type）上提供一个自定义的类级别 operator new，它将替代全局的 operator new 被使用。因此，可以检查堆分配是否被消除。如果未被消除，我们可以找出协程状态所需的内存大小。以下是使用我们之前定义的 Promise 类型的示例：

struct Promise {
/* Same as before ... */
    static void* operator new(std::size_t sz) {
        std::cout << "custom new for size " << sz << '\n';
        return ::operator new(sz);
    }
    static void operator delete(void* ptr) {
        std::cout << "custom delete called\n";
        ::operator delete(ptr);
    }
}

另一个验证对于使用特定承诺类型的所有协程，堆分配是否完全被消除的技巧是声明 operator new 和 operator delete 但省略它们的定义。如果编译器随后插入对这些操作符的调用，程序将因符号无法解析而链接失败。

避免悬空引用

协程可以在我们的代码中传递，这意味着我们需要非常小心地管理传递给协程的参数的生命周期，以避免悬空引用（dangling references）。

协程帧包含通常位于栈上的对象的副本，例如局部变量和传递给协程的参数。如果协程通过引用接受参数，则复制的是引用本身，而不是对象。这意味着遵循函数参数的常规指导原则（即通过 const 引用传递昂贵的复制对象）时，我们很容易陷入悬空引用的困境。

向协程传递参数

以下协程使用了对 const std::string 的引用：

auto coroutine(const std::string& str) -> Resumable {
    std::cout << str;
    co_return;
}

假设我们有一个工厂函数用于创建并返回协程，如下所示：

auto coro_factory() {
    auto str = std::string{"ABC"};
    auto res = coroutine(str);
    return res;
}

最后，一个使用协程的 main() 函数：

int main() {
    auto coro = coro_factory();
    coro.resume();
}

这段代码表现出未定义行为（undefined behavior），因为当协程尝试访问 std::string 对象时，该对象（包含字符串 “ABC”）已经不再存活。希望这不会让您感到惊讶。这个问题类似于 lambda 通过引用捕获变量，然后将该 lambda 传递给其他代码而没有保持引用的对象存活。一个类似的示例可以通过传递捕获变量引用的 lambda 来实现：

auto lambda_factory() {
    auto str = std::string{"ABC"};
    auto lambda = [&str]() { // Capture str by reference (通过引用捕获 str)
        std::cout << str;
    };
    return lambda; // Ops! str in lambda becomes (噢！lambda 中的 str 成为)
} // a dangling reference (一个悬空引用)

int main() {
    auto f = lambda_factory();
    f(); // Undefined behavior (未定义行为)
}

正如您所见，同样的问题也可能发生在 lambda 上。在《第 2 章，C++ 基本技术》中，作者警告过您关于 lambda 捕获引用的问题，通常最好通过按值捕获来避免此问题。

避免协程悬空引用的解决方案是类似的：在使用协程时，避免通过引用传递参数。相反，使用按值传递，整个参数对象将被安全地放置在协程帧中：

auto coroutine(std::string str) -> Resumable { // OK, by value! (没问题，按值传递！)
    std::cout << str;
    co_return;
}

auto coro_factory() {
    auto str = std::string{"ABC"};
    auto res = coroutine(str);
    return res;
}

int main() {
    auto coro = coro_factory();
    coro.resume(); // OK! (没问题！)
}

参数是使用协程时生命周期问题的一个重要且常见的来源，但它们不是唯一的来源。现在我们将探讨与协程和悬空引用相关的其他一些陷阱。

作为协程的成员函数 (Member functions that are coroutines)

成员函数也可以是协程。例如，没有什么能阻止我们在成员函数中使用 co_await，如下例所示：

struct Widget {
    auto coroutine() -> Resumable { // A member function (一个成员函数)
        std::cout << i_++ << " "; // Access data member (访问数据成员)
        co_await std::suspend_always{};
        std::cout << i_++ << " ";
    }
    int i_{};
};

int main() {
    auto w = Widget{99};
    auto coro = w.coroutine();
    coro.resume();
    coro.resume();
}
// Prints: 99 100

重要的是要理解，是 coroutine() 的调用者（在本例中是 main()）有责任确保 Widget 对象 w 在协程的整个生命周期内保持存活。协程正在访问它所属对象的数据成员，但 Widget 对象本身并没有被协程保持存活。如果我们把协程传递给程序的其他部分，这很容易成为一个问题。

假设我们使用前面演示的协程工厂函数，但返回一个成员函数协程：

auto widget_coro_factory() { // Create and return a coroutine
    auto w = Widget{};
    auto coro = w.coroutine();
    return coro;
} // Object w destructs here (对象 w 在此析构)

int main() {
    auto r = widget_coro_factory();
    r.resume(); // Undefined behavior (未定义行为)
    r.resume();
}

这段代码表现出未定义行为，因为我们现在有一个从协程到在 widget_coro_factory() 函数中创建并析构的 Widget 对象的悬空引用。换句话说，我们最终得到了两个具有不同生命周期的对象，其中一个对象引用了另一个对象，但没有任何显式的所有权。

作为协程的 Lambdas

不仅成员函数可以成为协程。通过在 lambda 的函数体中插入 co_await、co_return 和/或 co_yield，也可以使用 lambda 表达式创建协程。

协程 lambda 处理起来可能稍微复杂一些。理解协程 lambda 最常见的生命周期问题的一种方法是思考函数对象（function objects）。回顾《第 2 章，C++ 基本技术》，lambda 表达式被编译器转换为一个函数对象。这个对象的类型是一个实现了调用操作符的类。现在，假设我们在 lambda 的函数体内部使用了 co_return；这意味着调用操作符 operator()() 变成了协程。

考虑以下使用 lambda 的代码：

auto lambda = [](int i) -> Resumable {
    std::cout << i;
    co_return; // Make it a coroutine (使其成为协程)
};

auto coro = lambda(42); // Call, creates the coroutine frame (调用，创建协程帧)
coro.resume(); // Outputs: 42

lambda 对应的类型看起来像这样：

struct LambdaType {
    auto operator()(int i) -> Resumable { // Member function (成员函数)
        std::cout << i; // Body (函数体)
        co_return;
    }
};

auto lambda = LambdaType{};
auto coro = lambda(42);
coro.resume();

这里需要注意的重要一点是，实际的协程是一个成员函数，即调用操作符 operator()()。上一节已经演示了协程成员函数的陷阱：我们需要在协程的生命周期内保持对象存活。在上面的示例中，这意味着我们需要保持名为 lambda 的函数对象存活，只要协程帧存活。

lambda 的某些用法使得意外地在协程帧被销毁之前就析构了函数对象变得非常容易。例如，通过使用立即调用 lambda，我们很容易陷入麻烦：

auto coro = [i = 0]() mutable -> Resumable {
    std::cout << i++;
    co_await std::suspend_always{};
    std::cout << i++;
}(); // Invoke lambda immediately (立即调用 lambda)
coro.resume(); // Undefined behavior! Function object (未定义行为！函数对象)
coro.resume(); // already destructed (已经析构)

这段代码看起来很无辜；lambda 没有通过引用捕获任何东西。然而，lambda 表达式创建的函数对象是一个临时对象，一旦它被调用并且协程捕获了对它的引用，它就会被析构。当协程恢复时，程序很可能会崩溃或产生垃圾数据。

同样，更好地理解这一点的方法是，将 lambda 转换为定义了 operator() 的普通类：

struct LambdaType {
    int i{0};
    auto operator()() -> Resumable {
        std::cout << i++;
        co_await std::suspend_always{};
        std::cout << i++;
    }
};

auto coro = LambdaType{}(); // Invoke operator() on temporary object (在临时对象上调用 operator())
coro.resume(); // Ops! Undefined behavior (噢！未定义行为)

现在您可以看到这与我们有一个协程成员函数的情况非常相似。函数对象没有被协程帧保持存活。

防止悬空引用的指导原则

除非您有充分的理由接受引用参数，否则在编写协程时，请选择按值接受参数。协程帧将保留您传递给它的对象的完整副本，并且该对象保证与协程帧一样长久地存活。

如果您使用作为协程的 lambda 或成员函数，请特别注意协程所属对象的生命周期。请记住，对象（或函数对象）不会存储在协程帧中。保持其存活是协程调用者的责任。

错误处理 (Handling errors)

有不同的方法可以将错误从协程传回给调用或恢复它的代码部分。我们不一定被迫使用异常来表示错误。相反，我们可以根据需要定制错误处理。

协程可以通过两种方式将错误传回给使用它的客户端：

1. 抛出异常 (throwing an exception)。
2. 在客户端从协程获取值时（当协程 yield 或 return 时）返回一个错误码 (returning an error code)。

如果我们使用异常，并且一个异常从协程体中传播出来，就会调用承诺对象（promise object）的 unhandled_exception() 函数。这个调用发生在编译器插入的 catch 块内部，因此可以使用 std::current_exception() 来获取被抛出的异常。然后，std::current_exception() 的结果可以作为 std::exception_ptr 存储在协程中，并在稍后重新抛出。您将在下一章使用异步协程时看到相关的示例。

定制点 (Customization points)

您已经看到了许多定制点，一个合理的问题是：为什么有这么多的定制点？

• 通用性 (Generality): 这些定制点使得协程能够以各种方式使用。关于如何使用 C++ 协程的假设非常少。库编写者可以定制 co_await、co_yield 和 co_return 的行为。
• 效率 (Efficiency): 一些定制点的存在是为了根据不同的使用场景实现可能的优化。一个例子是 await_ready()，如果一个值已经被计算出来，它可以返回 true 以避免不必要的暂停。

还应该说明的是，我们之所以接触到这些定制点，是因为 C++ 标准没有提供任何类型（除了 std::coroutine_handle）来与协程通信。一旦这些类型（如 Task 或 Generator）就位，我们就可以重用它们，而不用过多担心其中的一些定制点。尽管如此，了解定制点对于充分理解如何高效使用 C++ 协程仍然是有价值的。

生成器 (Generators)

生成器（Generator）是一种将值yield 回给调用者的协程类型。例如，在本章开头，作者演示了 iota() 生成器如何 yield 递增的整数值。通过实现一个可以充当迭代器的通用生成器类型，我们可以简化实现与基于范围的 for 循环、标准库算法和 Ranges 兼容的迭代器的工作。一旦我们有了生成器模板类，我们就可以重用它。

到目前为止，在本书中，您大多在访问容器元素和使用标准库算法的上下文看到了迭代器。然而，迭代器不必与容器绑定。可以编写生成值的迭代器。

实现一个生成器 (Implementing a generator)

我们将要实现的生成器基于 CppCoro 库中的生成器。该生成器模板旨在用作产生值序列的协程的返回类型。这种类型的对象应该可以与基于范围的 for 循环和接受迭代器及范围的标准算法一起使用。为了实现这一点，我们将实现三个组件：

1. Generator: 作为返回对象。
2. Promise: 作为协程控制器。
3. Iterator: 作为客户端和 Promise 之间的接口。

这三种类型紧密耦合，它们与协程状态之间的关系如下图所示：

返回对象，在这里是 Generator 类，与 Promise 类型紧密耦合；Promise 类型负责创建 Generator 对象，而 Generator 类型负责向编译器暴露正确的 promise_type。

以下是 Generator 的实现：

template <typename T>
class Generator {
private:
    struct Promise { /* ... */ }; // See below (见下文)
    struct Sentinel {};
    struct Iterator { /* ... */ }; // See below (见下文)
    std::coroutine_handle<Promise> h_;
    explicit Generator(std::coroutine_handle<Promise> h) : h_{h} {}

public:
    using promise_type = Promise;
    Generator(Generator&& g) : h_(std::exchange(g.h_, {})) {}
    ~Generator() { if (h_) { h_.destroy(); } }
    
    auto begin() {
        h_.resume(); // 首次调用 resume 以执行到第一个 co_yield
        return Iterator{h_};
    }
    auto end() { return Sentinel{}; }
};

Promise 和 Iterator 的实现将很快跟进。Generator 与我们之前定义的 Resumable 类没有太大区别。Generator 是协程的返回对象和 std::coroutine_handle 的所有者。Generator 是一种可移动类型。当它被移动时，协程句柄被转移到新构造的 Generator 对象。当拥有协程句柄的 Generator 被析构时，它通过调用协程句柄的 destroy 函数来销毁协程状态。

begin() 和 end() 函数使得这个生成器可以在基于范围的 for 循环和接受范围的算法中使用。Sentinel 类型是空的—它是一个虚拟类型（dummy type）—Sentinel 实例用于能够将某些东西传递给 Iterator 类的比较操作符。

Iterator 的实现看起来像这样：

struct Iterator {
    using iterator_category = std::input_iterator_tag;
    using value_type = T;
    using difference_type = ptrdiff_t;
    using pointer = T*;
    using reference = T&;
    std::coroutine_handle<Promise> h_; // Data member (数据成员)

    Iterator& operator++() {
        h_.resume(); // 递增迭代器时，恢复协程以生成下一个值
        return *this;
    }

    void operator++(int) { (void)operator++(); }

    T operator*() const { return h_.promise().value_; } // 解引用返回 Promise 中存储的值
    
    T* operator->() const { return std::addressof(operator*()); }

    bool operator==(Sentinel) const { return h_.done(); } // 与哨兵比较，检查协程是否完成
};

迭代器需要将协程句柄存储在一个数据成员中，以便它可以将调用委托给协程句柄和承诺对象：

• 当迭代器被解引用时，它返回 Promise 中持有的当前值。
• 当迭代器被递增时，它恢复协程。
• 当迭代器与哨兵值进行比较时，迭代器忽略哨兵并将调用委托给协程句柄，协程句柄知道是否还有更多元素要生成（通过 h_.done()）。

现在只剩下 Promise 类型供我们实现了。Promise 的完整定义看起来像这样：

struct Promise {
    T value_; // 存储 co_yield 产生的值
    
    auto get_return_object() -> Generator<T> {
        using Handle = std::coroutine_handle<Promise>;
        return Generator{Handle::from_promise(*this)};
    }
    
    auto initial_suspend() { return std::suspend_always{}; } // 初始暂停，等待 begin() 调用
    auto final_suspend() noexcept { return std::suspend_always{}; } // 最终暂停，等待析构函数清理
    
    void return_void() {} // 处理 co_return;
    void unhandled_exception() { throw; } // 重新抛出异常
    
    // 处理右值 co_yield，高效移动值
    auto yield_value(T&& value) { 
        value_ = std::move(value);
        return std::suspend_always{}; // 暂停，将控制权返回给调用者
    }

    // 处理左值 co_yield，复制值
    auto yield_value(const T& value) { 
        value_ = value;
        return std::suspend_always{}; // 暂停
    }
};

我们生成器的承诺对象负责：

• 创建 Generator 对象。
• 定义到达初始和最终暂停点时的行为。
• 跟踪从协程 yield 出来的最后一个值（存储在 value_ 中）。
• 处理协程体抛出的异常（在这里是重新抛出）。

就是这样！我们现在所有的部分都已就位。返回 Generator<T> 类型的协程现在可以使用 co_yield 惰性地生成值。协程的调用者与 Generator 和 Iterator 对象交互以检索值。

对象之间的交互如下图所示：

现在，让我们看看如何使用新的 Generator 模板以及它如何简化各种迭代器的实现。

使用 Generator类

本例灵感来源于 Gor Nishanov 在 CppCon 2016 上的演讲《C++ 协程：揭秘内核》，它清晰地展示了我们如何从刚刚实现的生成器类型中受益。现在可以像这样实现小型可组合的生成器：

template <typename T>
auto seq() -> Generator<T> {
  for (T i = {};; ++i) {
    co_yield i;
  }  
}

template <typename T>
auto take_until(Generator<T>& gen, T value) -> Generator<T> {
  for (auto&& v : gen) {
    if (v == value) {
      co_return;
    }
    co_yield v;
  }
}

template <typename T>
auto add(Generator<T>& gen, T adder) -> Generator<T> {
  for (auto&& v : gen) {
    co_yield v + adder;
  }
}

一个简单的使用示例表明我们可以将我们的生成器传递给基于范围的 for 循环：

int main() {
  auto s = seq<int>();
  auto t = take_until<int>(s, 10);
  auto a = add<int>(t, 3);
  int sum = 0;
  for (auto&& v : a) {
    sum += v;
  }
  return sum; // returns 75
}

这些生成器是惰性求值（lazily evaluated）的。在程序到达 for 循环之前，不会产生任何值，for 循环会从生成器链中拉取（pull）值。

这个程序的另一个有趣的方面是，当使用 Clang 10 并开启优化进行编译时，整个程序的汇编代码看起来像这样：

main: # @main
mov eax, 75
ret

太棒了！程序简单地定义了一个返回 $75$ 的 main 函数。换句话说，编译器优化器已经能够在编译时完全评估生成器链，并得出单个值 $75$。

我们的 Generator 类也可以与范围算法一起使用。在下面的示例中，我们使用 includes() 算法来查看序列 ${5, 6, 7}$ 是否是生成器产生的数字的子范围：

int main() {
  auto s = seq<int>(); // Same as before
  auto t = take_until<int>(s, 10);
  auto a = add<int>(t, 3);
  const auto v = std::vector{5, 6, 7};
  auto is_subrange = std::ranges::includes(a, v); // True
}

通过实现 Generator 模板，我们可以将其重用于各种生成器函数。我们实现了一个通用且高度有用的库组件，应用程序代码在构建惰性生成器时可以在许多地方从中受益。

解决生成器问题

现在作者将提出一个小型问题，我们将尝试使用不同的技术来解决它，目的是了解我们可能可以用生成器替换哪些编程习惯用法。我们将编写一个小型工具，用于生成起始值和停止值之间线性等距的序列。

如果您使用过 MATLAB/Octave 或 Python NumPy，您可能会认出这种使用名为 linspace() 函数生成均匀（线性）间隔数字的方法。这是一个方便的实用工具，可用于具有任意范围的各种上下文。

我们将我们的生成器命名为 lin_space()。以下是生成 $2.0$ 和 $3.0$ 之间五个等距值的用法示例：

for (auto v: lin_space(2.0f, 3.0f, 5)) {
    std::cout << v << ", ";
}
// Prints: 2.0, 2.25, 2.5, 2.75, 3.0,

辅助函数：lin_value()

在生成浮点值时，我们必须稍微谨慎，因为我们不能简单地计算每个步长（在上面的示例中为 $0.25$）并累加它，因为步长可能无法使用浮点数据类型精确表示。可能的舍入误差会在每次迭代中累加，最终我们可能会得到完全荒谬的值。我们相反需要做的是使用线性插值（linear interpolation）在特定的增量下计算起始值和停止值之间的一个数字。

C++20 在 <cmath> 中添加了一个名为 std::lerp() 的便捷实用工具，它计算两个值之间的线性插值，并带有指定的“量”（amount）。在我们的例子中，“量”将是 $0.0$ 到 $1.0$ 之间的值；量为 $0$ 返回起始值，量为 $1.0$ 返回停止值。以下是使用 std::lerp() 的几个示例：

auto start = -1.0;
auto stop = 1.0;
std::lerp(start, stop, 0.0); // -1.0
std::lerp(start, stop, 0.5); // 0.0
std::lerp(start, stop, 1.0); // 1.0

我们将要编写的 lin_space() 函数都将使用以下小型辅助函数模板：

template <typename T>
auto lin_value(T start, T stop, size_t index, size_t n) {
    assert(n > 1 && index < n);
    const auto amount = static_cast<T>(index) / (n - 1);
    const auto v = std::lerp(start, stop, amount); // C++20
    return v;
}

该函数返回范围 $[start, stop]$ 中线性序列的值。index 参数是我们要生成的 $n$ 个总数中当前数字的编号。

有了 lin_value() 帮助程序，我们现在可以轻松实现 lin_space() 生成器。在看到使用协程的解决方案之前，我们将研究其他常见技术。接下来的部分将探讨实现 lin_space() 时的以下不同方法：

• Eagerly generate and return all values (急切地生成并返回所有值)
• Using a callback (lazy) (使用回调函数（惰性）)
• Using a custom iterator (lazy) (使用自定义迭代器（惰性）)
• Using the Ranges library (lazy) (使用 Ranges 库（惰性）)
• Using coroutines with our Generator class (lazy) (使用我们的 Generator 类和协程（惰性）)

对于每个示例，都会简要反思每种方法的优点和缺点。

1. 急切的线性范围

我们将从实现一个简单的急切（eager）版本开始，它计算范围内的所有值并返回一个包含所有值的 vector：

template <typename T>
auto lin_space(T start, T stop, size_t n) {
    auto v = std::vector<T>{};
    for (auto i = 0u; i < n; ++i)
        v.push_back(lin_value(start, stop, i, n));
    return v;
}

由于此版本返回一个标准容器，因此可以将返回值用于基于范围的 for 循环和其他标准算法：

for (auto v : lin_space(2.0, 3.0, 5)) {
    std::cout << v << ", ";
}
// Prints: 2, 2.25, 2.5, 2.75, 3,

这个版本简单明了，相当容易阅读。缺点是我们需要分配一个 vector 并用所有值填充它，尽管调用者不一定对所有值都感兴趣。这个版本也缺乏可组合性（composability），因为没有办法在不首先生成所有值的情况下在中间过滤元素。

现在让我们尝试实现 lin_space() 生成器的一个惰性（lazy）版本。

2. 使用回调函数的惰性版本 (A lazy version using a callback)

在《第 10 章，代理对象和惰性求值》中，作者得出结论，惰性求值可以通过使用回调函数来实现。我们将实现的惰性版本是基于将一个回调函数传递给 lin_space() 并在发出值时调用该回调函数：

template <typename T, typename F>
requires std::invocable<F&, const T&> // C++20
void lin_space(T start, T stop, std::size_t n, F&& f) {
    for (auto i = 0u; i < n; ++i) {
        const auto y = lin_value(start, stop, i, n);
        f(y);
    }
}

如果我们想打印生成器产生的值，我们可以像这样调用这个函数：

auto print = [](auto v) { std::cout << v << ", "; };
lin_space(-1.f, 1.f, 5, print);
// Prints: -1, -0.5, 0, 0.5, 1,

迭代现在发生在 lin_space() 函数内部。没有办法取消生成器，但进行一些更改后，我们可以让回调函数返回一个 bool 来指示它是否需要生成更多元素。

这种方法有效但不够优雅。当尝试组合生成器时，这种设计的问腿变得更加明显。如果我们想添加一个过滤器来选择一些特殊值，我们将最终得到嵌套的回调函数。

现在我们将继续看如何为我们的问题实现一个基于迭代器的解决方案。

3. 迭代器实现 (An iterator implementation)

另一种替代方案是实现一个通过暴露 begin() 和 end() 迭代器来符合范围（range）概念的类型。这里定义的类模板 LinSpace 使得可以迭代线性值范围：

template <typename T>
struct LinSpace {
    LinSpace(T start, T stop, std::size_t n)
        : begin_{start, stop, 0, n}, end_{n} {}
    struct Iterator {
        using difference_type = void;
        using value_type = T;
        using reference = T;
        using pointer = T*;
        using iterator_category = std::forward_iterator_tag;
        void operator++() { ++i_; }
        T operator*() { return lin_value(start_, stop_, i_, n_);}
        bool operator==(std::size_t i) const { return i_ == i; }
        T start_{};
        T stop_{};
        std::size_t i_{};
        std::size_t n_{};
    };
    auto begin() { return begin_; }
    auto end() { return end_; }
private:
    Iterator begin_{};
    std::size_t end_{};
};

template <typename T>
auto lin_space(T start, T stop, std::size_t n) {
    return LinSpace{start, stop, n};
}

这个实现非常高效。然而，它受困于大量的样板代码（boilerplate code），而且我们试图封装的小算法现在分散到不同的部分：LinSpace 构造函数实现了设置起始值和停止值的初始工作，而计算值所需的工作最终位于 Iterator 类的成员函数中。与我们看过的其他版本相比，这使得算法的实现更难理解。

4. 使用 Ranges 库的解决方案 (A solution using the Ranges library)

另一种替代方案是使用 Ranges 库 (C++20) 中的构建块来组合我们的算法，如下所示：

template <typename T>
auto lin_space(T start, T stop, std::size_t n) {
    return std::views::iota(std::size_t{0}, n) |
           std::views::transform([=](auto i) {
               return lin_value(start, stop, i, n);
           });
}

这里我们将整个算法封装在一个小函数内部。我们使用 std::views::iota 为我们生成索引。将索引转换为线性值是一个简单的转换，可以在 iota 视图之后链接。

这个版本高效且可组合。从 lin_space() 返回的对象是一个 std::ranges::view 类型的随机访问范围（random-access range），可以使用基于范围的 for 循环迭代或传递给其他算法。

5. 使用协程的解决方案 (A solution using a coroutine)

在看过不少于四个针对同一个问题的版本之后，我们现在到达了最后一个解决方案。这里将展示一个使用前面实现的通用 Generator 类模板的版本：

template <typename T>
auto lin_space(T start, T stop, std::size_t n) -> Generator<T> {
    for (auto i = 0u; i < n; ++i) {
        co_yield lin_value(start, stop, i, n);
    }
}

它紧凑、直接且易于理解。通过使用 co_yield，我们可以编写出类似于简单的急切版本的代码，但无需将所有值收集到容器中。可以像您将在本章末尾看到的那样，链接多个基于协程的生成器。

此版本也与基于范围的 for 循环和标准算法兼容。然而，此版本暴露的是一个输入范围（input range），因此无法跳过任意数量的元素，而这是使用 Ranges 库的版本可以实现的。

结论 (Conclusion)

显然，不止一种方法可以解决这个问题。但作者为什么要展示所有这些方法呢？

1. 模式识别： 首先，如果您是协程的新手，您将有望开始看到使用协程可能具有优势的模式。
2. 简洁性： 其次，Generator 模板和 co_yield 的使用允许我们以非常清晰和简洁的方式实现惰性生成器。当我们将解决方案与其他版本进行比较时，这一点变得显而易见。
3. 习惯替换： 最后，某些方法对于这个示例问题可能看起来非常做作，但它们经常用于其他上下文。C++ 默认是一种急切（eager）的语言，许多人（包括作者）已经习惯于创建类似于急切版本的代码。使用回调函数的版本可能看起来很奇怪，但在异步代码中是一种常用模式，协程可以包装或替换这些基于回调的 API。

我们实现的生成器类型部分基于 CppCoro 库中的同步生成器模板。CppCoro 还提供了一个 async_generator 模板，使得可以在生成器协程内部使用 co_await 操作符。作者在本章中提供了 Generator 模板，目的是演示如何实现生成器以及如何与协程交互。但如果您计划开始在代码中使用生成器，请考虑使用第三方库。

使用生成器的真实世界示例

当示例更高级时，使用协程来简化迭代器才真正发挥作用。使用 co_yield 结合 Generator 类，使我们能够高效地实现和组合小型算法，而无需样板代码将它们粘合在一起。接下来的这个例子将尝试证明这一点。

问题描述 (The problem)

我们将通过一个例子来演示如何使用我们的 Generator 类来实现一种压缩算法，该算法可用于搜索索引的压缩，这些索引通常存储在磁盘上。这个例子在 Manning 等人的《信息检索导论》一书中有详尽描述。

搜索引擎使用某种形式的名为倒排索引（inverted index）的数据结构。它就像一本书末尾的索引。使用该索引，我们可以找到包含我们正在搜索的术语的所有页面。

现在想象我们有一个充满菜谱的数据库，并为该数据库构建一个倒排索引。该索引的一部分可能看起来像这样：

每个术语都关联着一个已排序的文档标识符列表。（例如，术语 apple 包含在 ID 为 $4, 9, 67, 89$ 的菜谱中。）如果我们要查找同时包含 beans 和 chili 的菜谱，我们可以运行一个类似归并（merge-like）的算法来查找 beans 和 chili 列表的交集（intersection）：

现在想象我们有一个大型数据库，我们选择使用 $32$ 位整数来表示文档标识符。对于出现在许多文档中的术语，文档标识符列表可能会变得非常长，因此我们需要压缩这些列表。一种可能的方法是使用差值编码（delta encoding）结合可变字节编码（variable byte encoding）方案。

由于列表是已排序的，我们可以存储两个相邻元素之间的间隙（gap），而不是存储文档标识符。这种技术被称为差值编码（delta encoding）或间隙编码（gap encoding）。下图显示了一个使用文档 ID 和间隙的示例：

间隙编码非常适用于此类数据；频繁使用的术语会因此产生许多小间隙。那些非常长的列表只会包含非常小的间隙。在列表经过间隙编码后，我们可以使用可变字节编码方案来实际压缩列表，通过对较小的间隙使用较少的字节。

但首先，让我们开始实现间隙编码功能。我们将从编写两个小型协程开始，它们将执行间隙编码/解码。

编码器将一个已排序的整数序列转换为一个间隙序列：

template <typename Range>
auto gap_encode(Range& ids) -> Generator<int> {
    auto last_id = 0;
    for (auto id : ids) {
        const auto gap = id - last_id;
        last_id = id;
        co_yield gap;
    }
}

通过使用 co_yield，无需急切地传递完整的数字列表并分配一个大的间隙输出列表。相反，协程惰性地一次处理一个数字。注意 gap_encode() 函数如何包含将文档 ID 转换为间隙所需知道的一切。将此实现为传统的迭代器是可能的，但这会将逻辑分散在迭代器上的构造函数和操作符中。

我们可以构建一个小程序来测试我们的间隙编码器：

int main() {
    auto ids = std::vector{10, 11, 12, 14};
    auto gaps = gap_encode(ids); // 注意：此处 ids 必须传递
    for (auto&& gap : gaps) {
        std::cout << gap << ", ";
    }
} // Prints: 10, 1, 1, 2,

解码器执行相反的操作；它将一个间隙范围作为输入，并将其转换为有序数字列表：

template <typename Range>
auto gap_decode(Range& gaps) -> Generator<int> {
    auto last_id = 0;
    for (auto gap : gaps) {
        const auto id = gap + last_id;
        co_yield id;
        last_id = id;
    }
}

通过使用间隙编码，我们平均而言将存储小得多的数字。但是，由于我们仍然使用 int 值来存储小间隙，如果我们将这些间隙保存到磁盘，我们并没有真正获得任何收益。不幸的是，我们不能只使用一个较小的固定大小的数据类型，因为仍然有可能遇到一个真正大的间隙，需要完整的 $32$ 位 int。我们想要的是一种使用更少位来存储小间隙的方法，如下图所示：

为了使这个列表的物理尺寸更小，我们可以使用可变字节编码，使得小间隙用比大间隙更少的字节进行编码，如上图所示。

可变字节编码是一种非常常见的压缩技术。UTF-8 和 MIDI 消息是使用此技术的一些著名编码。为了在编码时使用可变数量的字节，我们使用每个字节的 $7$ 位用于实际的有效载荷（payload）。每个字节的第一位代表一个继续位（continuation bit）。如果还有更多的字节要读取，则它设置为 $0$；如果它是编码数字的最后一个字节，则设置为 $1$。编码方案如下图例示：

现在我们准备好实现可变字节编码和解码方案了。这比差值编码稍微复杂一些。编码器应该将一个数字转换为一个或多个字节的序列：

auto vb_encode_num(int n) -> Generator<std::uint8_t> {
    for (auto cont = std::uint8_t{0}; cont == 0;) {
        auto b = static_cast<std::uint8_t>(n % 128);
        n = n / 128;
        cont = (n == 0) ? 128 : 0;
        co_yield (b + cont);
    }
}

代码中名为 cont 的继续位要么是 $0$，要么是 $128$，这对应于位序列 $10000000$。本例中的细节理解起来不是那么重要，但为了使编码更容易，字节是以反向顺序生成的，使得最低有效字节先出现。这不是问题，因为我们可以在解码期间轻松处理它。

有了数字编码器，编码一个数字序列并将其转换为字节序列就很简单了：

template <typename Range>
auto vb_encode(Range& r) -> Generator<std::uint8_t> {
    for (auto n : r) {
        auto bytes = vb_encode_num(n);
        for (auto b : bytes) {
            co_yield b;
        }
    }
}

解码器可能是最复杂的部分。但同样，它被完全封装在一个具有清晰接口的函数中：

template <typename Range>
auto vb_decode(Range& bytes) -> Generator<int> {
    auto n = 0;
    auto weight = 1;
    for (auto b : bytes) {
        if (b < 128) { // Check continuation bit (检查继续位)
            n += b * weight;
            weight *= 128;
        }
        else {
            // Process last byte and yield (处理最后一个字节并 yield)
            n += (b - 128) * weight;
            co_yield n;
            n = 0; // Reset (重置)
            weight = 1; // Reset (重置)
        }
    }
}

如您所见，这段代码中所需的样板代码非常少。每个协程都封装了所有状态，并清晰地描述了如何一次处理一个片段。

我们需要将间隙编码器与可变字节编码器结合起来，以压缩我们排序的文档标识符列表：

template <typename Range>
auto compress(Range& ids) -> Generator<int> {
    auto gaps = gap_encode(ids);
    auto bytes = vb_encode(gaps);
    for (auto b : bytes) {
        co_yield b;
    }
}

// Decompress is a simple chaining of vb_decode() followed by gap_decode():
// 解压缩是 vb_decode() 后跟 gap_decode() 的简单链接：
template <typename Range>
auto decompress(Range& bytes) -> Generator<int> {
    auto gaps = vb_decode(bytes);
    auto ids = gap_decode(gaps);
    for (auto id : ids) {
        co_yield id;
    }
}

由于 Generator 类暴露了迭代器，我们可以将这个例子进一步扩展，轻松地使用 iostreams 将值流式传输到磁盘和从磁盘读取。（尽管，更实际的方法是使用内存映射 I/O 以获得更好的性能。）

这里有两个小型函数，用于将压缩数据写入磁盘和从磁盘读取：

template <typename Range>
void write(const std::string& path, Range& bytes) {
    auto out = std::ofstream{path, std::ios::out | std::ofstream::binary};
    std::ranges::copy(bytes.begin(), bytes.end(),
                      std::ostreambuf_iterator<char>(out));
}

auto read(std::string path) -> Generator<std::uint8_t> {
    auto in = std::ifstream {path, std::ios::in | std::ofstream::binary};
    auto it = std::istreambuf_iterator<char>{in};
    const auto end = std::istreambuf_iterator<char>{};
    for (; it != end; ++it) {
        co_yield *it;
    }
}

一个小型的测试程序将结束这个例子：

int main() {
    {
        auto documents = std::vector{367, 438, 439, 440};
        auto bytes = compress(documents);
        write("values.bin", bytes);
    }
    {
        auto bytes = read("values.bin");
        auto documents = decompress(bytes);
        for (auto doc : documents) {
            std::cout << doc << ", ";
        }
    }
}
// Prints: 367, 438, 439, 440,

这个例子旨在表明我们可以将惰性程序划分为小型封装的协程。C++ 协程的低开销使其适用于构建高效的生成器。我们最初实现的 Generator 是一个完全可重用的类，有助于我们在像这样的例子中最小化样板代码的数量。

性能考虑

每次创建协程（首次调用时），都会分配一个协程帧（coroutine frame）来保存协程状态。协程帧可以分配在堆上，或者在某些情况下分配在栈上。然而，不能保证完全避免堆分配。如果您处于禁止堆分配的情况（例如，在实时 (real-time) 上下文中），可以创建协程并立即在不同的线程中暂停，然后将其传递给程序中实际需要使用协程的部分。暂停（Suspend）和恢复（Resume）保证不分配任何内存，并且成本与普通的函数调用相当。

在撰写本书时，编译器对协程的支持仍处于实验阶段。小型实验已经显示出与性能相关的有希望的结果，表明协程对优化器很友好。然而，作者不会在本书中提供任何协程的基准测试。相反，作者展示了无栈协程（stackless coroutines）是如何求值的，以及协程是如何以最小开销实现的。

生成器示例表明协程对编译器可能非常友好。我们在该示例中编写的生成器链在运行时被完全求值（即消除）。在实践中，这是 C++ 协程的一个非常好的特性。它们允许我们编写对编译器和人类都易于理解的代码。C++ 协程通常会产生易于优化的干净代码。在同一线程上执行的协程可以共享状态而无需使用任何锁定原语，因此可以避免多线程同步带来的性能开销。这将在下一章中得到演示。

总结

在本章中，您看到了如何使用 C++ 协程通过关键字 co_yield 和 co_return 来构建生成器。为了更好地理解 C++ 无栈协程与有栈协程的区别，我们对两者进行了比较，并研究了 C++ 协程提供的定制点（customization points）。这使您对 C++ 协程的灵活性以及如何利用它们实现效率有了深入的理解。无栈协程与状态机（state machines）密切相关。通过将传统实现的状态机重写为使用协程的代码，我们探讨了这种关系，您看到了编译器如何很好地将我们的协程转换为机器语言并进行优化。

在下一章中，我们将继续讨论协程，重点关注异步编程（asynchronous programming），并将加深您对 co_await 关键字的理解。

• ← Previous Post
• Next Post →