2. 实现一个序列生成器 | Benny Huo 的专栏

1.协程简介

什么是从cpp无栈协程？保留协程自己的状态和值，切换到另一个协程，不进行堆栈的切换

  1. co_await表示协程的挂起，操作对象是awaiter等待体
  2. 协程体内await_ready决定是否挂起，返回false就挂起，true无需挂起
  3. await_ready 返回 false 时，协程就挂起了。这时候协程的局部变量和挂起点都会被存入协程的状态当中，await_suspend 被调用到
  4. 协程恢复执行之后，等待体的 await_resume 函数被调用

自己实现一个很简单的等待体，功能是，调用co_await，看await_ready为false，始终挂起，挂起后新建一个线程，等待1s后再调用resume，resume返回一个值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct Awaiter {
  int value;

  bool await_ready() {
    // 协程挂起
    return false;
  }

  void await_suspend(std::coroutine_handle<> coroutine_handle) {
    // 切换线程
    std::async([=](){
      using namespace std::chrono_literals;
      // sleep 1s
      std::this_thread::sleep_for(1s); 
      // 恢复协程
      coroutine_handle.resume();
    });
  }

  int await_resume() {
    // value 将作为 co_await 表达式的值
    return value;
  }
};

co_await 后面的对象也可以不是等待体，这类情况需要定义其他的函数和运算符来转换成等待体。这个我们后面再讨论。

协程的返回值

区别一个函数是不是协程，是通过它的返回值类型来判断的。如果它的返回值类型满足协程的规则，那这个函数就会被编译成协程。

规则就是返回值类型能够实例化下面的模板类型 _Coroutine_traits：

1
2
3
4
5
6
7
8
9
10
template <class _Ret, class = void>
struct _Coroutine_traits {};

template <class _Ret>
struct _Coroutine_traits<_Ret, void_t<typename _Ret::promise_type>> {
    using promise_type = typename _Ret::promise_type;
};

template <class _Ret, class...>
struct coroutine_traits : _Coroutine_traits<_Ret> {};

简单来说，就是返回值类型 _Ret 能够找到一个类型 _Ret::promise_type 与之相匹配。这个 promise_type 既可以是直接定义在 _Ret 当中的类型，也可以通过 using 指向已经存在的其他外部类型。

此时，我们就可以给出 Result 的部分实现了：

1
2
3
4
5
struct Result {
  struct promise_type {
    ...
  };
};

协程返回值对象的构建

看一个协程函数的示例

1
2
3
4
5
Result Coroutine(int start_value) {
  std::cout << start_value << std::endl;
  co_await std::suspend_always{};
  std::cout << start_value + 1 << std::endl;
};

协程体当中并没有给出 Result 对象创建的代码。
实际上，Result 对象的创建是由 promise_type 负责的，我们需要定义一个 get_return_object 函数来处理对 Result 对象的创建

1
2
3
4
5
6
7
8
9
10
struct Result {
  struct promise_type {
    Result get_return_object() {
      // 创建 Result 对象
      return {};
    }
    ...
  };
};

不同于一般的函数，协程的返回值并不是在返回之前才创建，而是在协程的状态创建出来之后马上就创建的。也就是说，协程的状态被创建出来之后，会立即构造 promise_type 对象，进而调用 get_return_object 来创建返回值对象。

promise_type 类型的构造函数参数列表如果与协程的参数列表一致，那么构造 promise_type 时就会调用这个构造函数。否则，就通过默认无参构造函数来构造 promise_type。

协程体的执行

initial_suspend

为了方便灵活扩展，协程体执行的第一步是调用 co_await promise.initial_suspend()，initial_suspend 的返回值就是一个等待对象（awaiter），如果返回值满足挂起的条件，则协程体在最一开始就立即挂起。这个点实际上非常重要，我们可以通过控制 initial_suspend 返回的等待体来实现协程的执行调度。有关调度的内容我们后面会专门探讨。
接下来执行协程体。

协程体的执行

协程体当中会存在 co_await、co_yield、co_return 三种协程特有的调用，其中

  • co_await 我们前面已经介绍过，用来将协程挂起。
  • co_yield 则是 co_await 的一个马甲，用于传值给协程的调用者或恢复者或被恢复者，我们后面会专门用一篇文章给出例子介绍它的用法。
  • co_return 则用来返回一个值或者从协程体返回。

协程体的返回值

对于返回一个值的情况，需要在 promise_type 当中定义一个函数

1
??? return_value();

例如：

1
2
3
4
5
6
7
8
struct Result {
  struct promise_type {
    void return_value(int value) {
      ...
    }
    ...
  };
};

此时，我们的 Coroutine 函数就需要使用 co_return 来返回一个整数了：

1
2
3
4
Result Coroutine() {
  ...
  co_return 1000;
};

1000 会作为参数传入，即 return_value 函数的参数 value 的值为 1000。

协程体返回 void

除了返回值的情况以外，C++ 协程当然也支持返回 void。只不过 promise_type 要定义的函数就不再是 return_value 了，而是 return_void 了：

1
2
3
4
5
6
7
8
struct Result {
  struct promise_type {
    void return_void() {
      ...
    }
    ...
  };
};

这时，协程内部就可以通过 co_return 来退出协程体了：

1
2
3
4
Result Coroutine() {
  ...
  co_return;
};

协程体抛出异常

协程体除了正常返回以外，也可以抛出异常。异常实际上也是一种结果的类型，因此处理方式也与返回结果相似。我们只需要在 promise_type 当中定义一个函数，在异常抛出时这个函数就会被调用到：

1
2
3
4
5
6
7
8
struct Result {
  struct promise_type {
    void unhandled_exception() {
      exception_ = std::current_exception(); // 获取当前异常
    }
    ...
  };
};

final_suspend

当协程执行完成或者抛出异常之后会先清理局部变量，接着调用 final_suspend 来方便开发者自行处理其他资源的销毁逻辑。final_suspend 也可以返回一个等待体使得当前协程挂起，但之后当前协程应当通过 coroutine_handle 的 destroy 函数来直接销毁，而不是 resume。

小结

本章介绍了协程的基本概念，两个重要的结构体 协程体和result结构体，协程体负责什么时候挂起，挂起后执行什么操作，恢复时执行什么操作
Result结构体内的promise_type可以定义返回值和异常的一系列操作

2. 实现一个序列生成器

实现目标

序列生成器通常的实现就是在一个协程内部通过某种方式向外部传一个值出去，并且将自己挂起，外部调用者则可以获取到这个值，并且在后续继续恢复执行序列生成器来获取下一个值。

显然，挂起和向外部传值的任务就需要通过 co_await 来完成了，外部获取值的任务就要通过协程的返回值来完成。
由此我们大致能想到最终程序的样子：

1
2
3
4
5
6
7
8
9
10
11
12
13
Generator sequence() {
  int i = 0;
  while (true) {
    co_await i++;
  }
}

int main() {
  auto generator = sequence();
  for (int i = 0; i < 10; ++i) {
    std::cout << generator.next() << std::endl;
  }
}

注意到 generator 有个 next 函数，调用它时我们需要想办法让协程恢复执行，并将下一个值传出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct Generator {
  struct promise_type {
    // 开始执行时不挂起，执行到第一个挂起点
    std::suspend_never initial_suspend() { return {}; };
    // 执行结束后不需要挂起
    std::suspend_never final_suspend() noexcept { return {}; }
    // 为了简单，我们认为序列生成器当中不会抛出异常，这里不做任何处理
    void unhandled_exception() { }
    // 构造协程的返回值类型
    Generator get_return_object() {
      return Generator{};
    }
    // 没有返回值
    void return_void() { }
  };
  int next() {
    ???.resume();
    return ???;
  }
};

调用者获取值

第一个是我们想要在 Generator 当中 resume 协程的话，需要拿到 coroutine_handle，这个要怎么做到呢？

这时候我希望大家一定要记住一点，promise_type 是连接协程内外的桥梁，想要拿到什么，找 promise_type 要。标准库提供了一个通过 promise_type 的对象的地址获取 coroutine_handle 的函数，它实际上是 coroutine_handle 的一个静态函数：

1
2
3
4
5
6
7
template <class _Promise>
struct coroutine_handle {
    static coroutine_handle from_promise(_Promise& _Prom) noexcept {
      ...
    }
    ...
}

获取返回值时就可以先获取coroutine handle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct Generator {
  struct promise_type {
    ...
    // 构造协程的返回值类型
    Generator get_return_object() {
      return Generator{ std::coroutine_handle<promise_type>::from_promise(*this) };
    }
    ...
  };
  std::coroutine_handle<promise_type> handle;
  int next() {
    handle.resume();
    return ???;
  }

};

接下来就是如何获取协程内部传出来的值的问题了。同样，本着有事儿找 promise_type 的原则，我们可以直接给它定义一个 value 成员：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

struct Generator {
  struct promise_type {
    int value;

    ...
  };

  std::coroutine_handle<promise_type> handle;

  int next() {
    handle.resume();
    // 通过 handle 获取 promise，然后再取到 value
    return handle.promise().value;
  }
};

协程内部挂起并传值

现在的问题就是如何从协程内部传值给 promise_type 了。

我们再来观察一下最终实现的效果：

1
2
3
4
5
6
Generator sequence() {
  int i = 0;
  while (true) {
    co_await i++;
  }
}//这是个协程函数

特别需要注意的是 co_await i++; 这一句，我们发现 co_await 后面的是一个整型值，而不是我们在前面的文章当中提到的满足等待体（awaiter）条件的类型，这种情况下该怎么办呢？

实际上，对于 co_await <expr> 表达式当中 expr 的处理，C++ 有一套完善的流程：

  1. 如果 promise_type 当中定义了 await_transform 函数，那么先通过 promise.await_transform(expr) 来对 expr 做一次转换，得到的对象称为 awaitable；否则 awaitable 就是 expr 本身。
  2. 接下来使用 awaitable 对象来获取等待体（awaiter）。如果 awaitable 对象有 operator co_await 运算符重载，那么等待体就是 operator co_await(awaitable)，否则等待体就是 awaitable 对象本身。

听上去，我们要么给 promise_type 实现一个 await_tranform(int) 函数，要么就为整型实现一个 operator co_await 的运算符重载，二者选一个就可以了。

方案 1：实现 operator co_await

这个方案就是给 int 定义 operator co_await 的重载：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
auto operator co_await(int value) {
  struct IntAwaiter {
    int value;

    bool await_ready() const noexcept {
      return false;
    }
    void await_suspend(std::coroutine_handle<Generator::promise_type> handle) const {
      handle.promise().value = value;
    }
    void await_resume() {  }
  };
  return IntAwaiter{.value = value};
}

当然，这个方案对于我们这个特定的场景下是行不通的，因为在 C++ 当中我们是无法给基本类型定义运算符重载的。

不过，如果我们遇到的情况不是基本类型，那么运算符重载的思路就可以行得通。operator co_await 的重载我们将会在后面给出例子。

方案 2：await_transform

运算符重载行不通，那就只能通过 await_tranform 来做转换了。

代码比较简单：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct Generator {
  struct promise_type {
    int value;

    // 传值的同时要挂起，值存入 value 当中
    std::suspend_always await_transform(int value) {
      this->value = value;
      return {};
    }

    ...
  };

  std::coroutine_handle<promise_type> handle;

  int next() {
    handle.resume();

  // 外部调用者或者恢复者可以通过读取 value
    return handle.promise().value;
  }
};

定义了 await_transform 函数之后，co_await expr 就相当于 co_await promise.await_transform(expr) 了。

至此，我们的例子就可以运行了：

1
2
3
4
5
6
7
8
9
10
11
12
13
Generator sequence() {
  int i = 0;
  while (true) {
    co_await i++;
  }
}

int main() {
  auto gen = sequence();
  for (int i = 0; i < 5; ++i) {
    std::cout << gen.next() << std::endl;
  }
}

运行结果如下：

1
2
3
4
5
0
1
2
3
4

协程的销毁

怎么知道协程有没有被销毁？

当协程体执行结束后，协程就会被销毁，再访问协程就相当于访问野指针
如

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Generator sequence() {
  int i = 0;
  // 只传出 5 个值
  while (i < 5) {
    co_await i++;
  }
}

int main() {
  auto gen = sequence();
  for (int i = 0; i < 15; ++i) {
    // 试图读取 15 个值
    std::cout << gen.next() << std::endl;
  }
  return 0;
}

会得到结果

1
2
3
4
5
6
7
8
0
1
2
3
4
4

Process finished with exit code 139 (interrupted by signal 11: SIGSEGV)

为了解决这个问题，我们需要增加一个 has_next 函数，用来判断是否还有新的值传出来，has_next 函数调用的时候有两种情况：

  1. 已经有一个值传出来了，还没有被外部消费
  2. 还没有现成的值可以用，需要尝试恢复执行协程来看看还有没有下一个值传出来

这里我们需要有一种有效的办法来判断 value 是不是有效的，单凭 value 本身我们其实是无法确定它的值是不是被消费了，因此我们需要加一个值来存储这个状态：

1
2
3
4
5
6
7
8
9
10
11
12
struct Generator {

  // 协程执行完成之后，外部读取值时抛出的异常
  class ExhaustedException: std::exception { };

  struct promise_type {
    int value;
    bool is_ready = false;
    ...
  }
  ...
}

我们定义一个成员 state 来记录协程执行的状态，状态的类型一共三种，只有 READY 的时候我们才能拿到值。

接下来改造 next 函数，同时增加 has_next 函数来描述协程是否仍然可以有值传出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
struct Generator {
  ...

  bool has_next() {
    // 协程已经执行完成
    if (!handle || handle.done()) {
      return false;
    }

    // 协程还没有执行完成，并且下一个值还没有准备好
    if (!handle.promise().is_ready) {
      handle.resume();
    }

    if (handle.done()) {
      // 恢复执行之后协程执行完，这时候必然没有通过 co_await 传出值来
      return false;
    } else {
      return true;
    }
  }

  int next() {
    if (has_next()) {
      // 此时一定有值，is_ready 为 true 
      // 消费当前的值，重置 is_ready 为 false
      handle.promise().is_ready = false;
      return handle.promise().value;
    }
    throw ExhaustedException();
  }
};

这样外部使用时就需要先通过 has_next 来判断是否有下一个值，然后再去读取了：

1
2
3
4
5
6
7
8
9
10
11
12
13
...

int main() {
  auto generator = sequence();
  for (int i = 0; i < 15; ++i) {
    if (generator.has_next()) {
      std::cout << generator.next() << std::endl;
    } else {
      break;
    }
  }
  return 0;
}

问题 2：协程状态的销毁比 Generator 对象的销毁更早

我们前面提到过，协程的状态在协程体执行完之后就会销毁，除非协程挂起在 final_suspend 调用时。

我们的例子当中 final_suspend 返回了 std::suspend_never，因此协程的销毁时机其实比 Generator 更早：

1
2
3
4
5
6
7
8
9
10
11
auto generator = sequence();
for (int i = 0; i < 15; ++i) {
  if (generator.has_next()) {
    std::cout << generator.next() << std::endl;
  } else {
    // 协程已经执行完，协程的状态已经销毁
    break;
  }
}

// generator 对象在此仍然有效

这看上去似乎问题不大，因为我们在前面通过 has_next 的判断保证了读取值的安全性。

但实际上情况并非如此。我们在 has_next 当中调用了 coroutine_handle::done 来判断协程体是否执行完成，判断之前很可能协程已经销毁，coroutine_handle 这时候都已经是无效的了：

1
2
3
4
5
6
7
8
bool has_next() {
  // 如果协程已经执行完成，理论上协程的状态已经销毁，handle 指向的是一个无效的协程
  // 如果 handle 本身已经无效，因此 done 函数的调用此时也是无效的
  if (!handle || handle.done()) {
    return false;
  }
  ...
}

因此为了让协程的状态的生成周期与 Generator 一致，我们必须将协程的销毁交给 Generator 来处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct Generator {

  class ExhaustedException: std::exception { };

  struct promise_type {
    ...

    // 总是挂起，让 Generator 来销毁
    std::suspend_always final_suspend() noexcept { return {}; }

    ...
  };

  ...

  ~Generator() {
    // 销毁协程
    handle.destroy();
  }
};

问题 3：复制对象导致协程被销毁

这个问题确切地说是问题 2的解决方案不完善引起的。

我们在 Generator 的析构函数当中销毁协程，这本身没有什么问题，但如果我们把 Generator 对象做一下复制，例如从一个函数当中返回，情况可能就会变得复杂。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Generator returns_generator() {
  auto g = sequence();
  if (g.has_next()) {
    std::cout << g.next() << std::endl;
  }
  return g;
}

int main() {
  auto generator = returns_generator();
  for (int i = 0; i < 15; ++i) {
    if (generator.has_next()) {
      std::cout << generator.next() << std::endl;
    } else {
      break;
    }
  }
  return 0;
}

这段代码乍一看似乎没什么问题，但由于我们把 g 当做返回值返回了，这时候 g 这个对象就发生了一次复制，然后临时对象被销毁。接下来的事儿大家就很容易想到了，运行结果如下：

1
2
3
4
0
-572662307

Process finished with exit code -1073741819 (0xC0000005)

为了解决这个问题，我们需要妥善地处理 Generator 的复制构造器：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct Generator {
  ...

  explicit Generator(std::coroutine_handle<promise_type> handle) noexcept
      : handle(handle) {}

  Generator(Generator &&generator) noexcept
      : handle(std::exchange(generator.handle, {})) {}

  Generator(Generator &) = delete;
  Generator &operator=(Generator &) = delete;

  ~Generator() {
    if (handle) handle.destroy();
  }
}

我们只提供了右值复制构造器，对于左值复制构造器，我们直接删除掉以禁止使用。原因也很简单，对于每一个协程实例，都有且仅能有一个 Generator 实例与之对应，因此我们只支持移动对象，而不支持复制对象。

使用 co_yield

序列生成器这个需求的实现其实有个更好的选择，那就是使用 co_yield。co_yield 就是专门为向外传值来设计的，如果大家对其他语言的协程有了解，也一定见到过各种 yield 的实现。

C++ 当中的 co_yield expr 等价于 co_await promise.yield_value(expr)，我们只需要将前面例子当中的 await_transform 函数替换成 yield_value 就可以使用 co_yield 来传值了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct Generator {

  class ExhaustedException: std::exception { };

  struct promise_type {
    ...

    // 将 await_transform 替换为 yield_value
    std::suspend_always yield_value(int value) {
      this->value = value;
      is_ready = true;
      return {};
    }
    ...
  };
  ...
};

Generator sequence() {
  int i = 0;
  while (i < 5) {
    // 使用 co_yield 来替换 co_await
    co_yield i++;
  }
}

可以看到改动点非常少，运行效果与前面的例子一致。

尽管可以实现相同的效果，但通常情况下我们使用 co_await 更多的关注点在挂起自己，等待别人上，而使用 co_yield 则是挂起自己传值出去。因此我们应该针对合适的场景做出合适的选择。

3. 序列生成器的泛化和函数式变换

泛化非常简单，加一个模板参数就可以

创建 Generator 的便捷函数

前面的代码创建Generator需要一个函数来确定生成器生成的范围，如果能够从一个数组或者序列中得到一个Generator会方便很多

使用数组创建 Generator 的版本实现比较简单，我们直接给出代码：

1
2
3
4
5
6
7
8
9
10
template<typename T>
struct Generator {
  ...

  Generator static from_array(T array[], int n) {
    for (int i = 0; i < n; ++i) {
      co_yield array[i];
    }
  }
}

注意到 C++ 的数组作为参数时相当于指针，需要传入长度 n。用法如下：

1
2
int array[] = {1, 2, 3, 4};
auto generator = Generator<int>::from_array(array, 4);

显然，这个写法不能令人满意。

我们把数组改成 std::list 如何呢？

1
2
3
4
5
6
7
8
9
10
template<typename T>
struct Generator {
  ...

  Generator static from_list(std::list<T> list) {
    for (auto t: list) {
      co_yield t;
    }
  }
}

相比数组，std::list 的版本少了一个长度参数，因为长度的信息被封装到 std::list 当中了。用法如下：

1
auto generator = Generator<int>::from_list(std::list{1, 2, 3, 4});

这个虽然有进步，但缺点也很明显，因为每次都要创建一个 std::list，说得直接一点儿就是每次都要多写 std::list 这 9 个字符。

这时候我们就很自然地想到了初始化列表的版本：

1
2
3
4
5
6
7
8
9
10
template<typename T>
struct Generator {
  ...

  Generator static from(std::initializer_list<T> args) {
    for (auto t: args) {
      co_yield t;
    }
  }
}

这次我们就可以有下面的用法了：

1
auto generator = Generator<int>::from({1, 2, 3, 4});

不错，看上去需要写的内容少很多了。

不过，如果这对花括号也不用写的话，那就完美了。想要做到这一点，我们需要用到 C++ 17 的折叠表达式（fold expression）的特性，实现如下：

1
2
3
4
5
6
7
8
9
template<typename T>
struct Generator {
  ...

  template<typename ...TArgs>
  Generator static from(TArgs ...args) {
    (co_yield args, ...);
  }
}

注意这里的模板参数包（template parameters pack）不能用递归的方式去调用 from，因为那样的话我们会得到非常多的 Generator 对象。

用法如下：

1
auto generator = Generator<int>::from(1, 2, 3, 4);

这下看上去完美多了。

实现 map 和 flat_map

实现 map

map 就是将 Generator 当中的 T 映射成一个新的类型 U，得到一个新的 Generator<U>。下面我们给出第一个版本的 map 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<typename T>
struct Generator {
  ...

  template<typename U>
  Generator<U> map(std::function<U(T)> f) {
    // 将 this 的所有权移动到新创建的 Generator 内部，确保生命周期的一致性
    auto up_stream = std::move(*this);
    // 判断 this 当中是否有下一个元素
    while (up_stream.has_next()) {
      // 使用 next 读取下一个元素
      // 通过 f 将其变换成 U 类型的值，再使用 co_yield 传出
      co_yield f(up_stream.next());
    }
  }  
}

参数 std::function<U(T)> 当中的模板参数 U(T) 是个模板构造器，放到这里就表示这个函数的参数类型为 T，返回值类型为 U。

接下来我们给出用法：

1
2
3
4
// fibonacci 是上一篇文章当中定义的函数，返回 Generator<int>
Generator<std::string> generator_str = fibonacci().map<std::string>([](int i) {
  return std::to_string(i);
});

通过 map 函数，我们将 Generator<int> 转换成了 Generator<std::string>，外部使用 generator_str 就会得到字符串。

当然，这个实现有个小小的缺陷，那就是 map 函数的模板参数 U 必须显式提供，如上例中的 <std::string>，这是因为我们在定义 map 时用到了模板构造器，这使得类型推断变得复杂。

为了解决这个问题，我们就要用到模板的一些高级特性了，下面给出第二个版本的 map 实现：

1
2
3
4
5
6
7
8
9
10
11
12
template<typename T>
struct Generator {
  ...

  template<typename F>
  Generator<std::invoke_result_t<F, T>> map(F f) {
    auto up_steam = std::move(*this);
    while (up_steam.has_next()) {
      co_yield f(up_steam.next());
    }
  }
}

注意，这里我们直接用模板参数 F 来表示转换函数 f 的类型。map 本身的定义要求 F 的参数类型是 T，然后通过 std::invoke_result_t<F, T> 类获取 F 的返回值类型。

这样我们在使用时就不需要显式的传入模板参数了：

1
2
3
Generator<std::string> generator_str = fibonacci().map([](int i) {
  return std::to_string(i);
});

实现 flat_map

在给出实现之前，我们需要先简单了解一下 flat_map 的概念。

前面提到的 map 是元素到元素的映射，而 flap_map 是元素到 Generator 的映射，然后将这些映射之后的 Generator 再展开（flat），组合成一个新的 Generator。这意味如果一个 Generator 会传出 5 个值，那么这 5 个值每一个值都会映射成一个新的 Generator，，得到的这 5 个 Generator 又会整合成一个新的 Generator。

由此可知，map 不会使得新 Generator 的值的个数发生变化，flat_map 会。

下面我们给出 flat_map 的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template<typename T>
struct Generator {
  ...

  template<typename F>
  // 返回值类型就是 F 的返回值类型
  std::invoke_result_t<F, T> flat_map(F f) {
    // 将 this 的所有权移动到新创建的 Generator 内部，确保生命周期的一致性
    auto up_steam = std::move(*this);
    while (up_steam.has_next()) {
      // 值映射成新的 Generator
      auto generator = f(up_steam.next());
      // 将新的 Generator 展开
      while (generator.has_next()) {
        co_yield generator.next();
      }
    }
  }
}

为了加深大家的理解，我们给出一个小例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Generator<int>::from(1, 2, 3, 4)
    // 返回值类型必须显式写出来，表明这个函数是个协程
    .flat_map([](auto i) -> Generator<int> {
      for (int j = 0; j < i; ++j) {
        // 在协程当中，我们可以使用 co_yield 传值出来
        co_yield j; 
      }
    })
    .for_each([](auto i) {
      if (i == 0) {
        std::cout << std::endl;
      }
      std::cout << "* ";
    });

这个例子的运行输出如下：

1
2
3
4
*
* *
* * *
* * * *

我们来稍微做下拆解。

  1. Generator<int>::from(1, 2, 3, 4) 得到的是序列 1 2 3 4
  2. flat_map 之后，得到 0 0 1 0 1 2 0 1 2 3

由于我们在 0 的位置做了换行，因此得到的输出就是 * 组成的三角形了。

flat_map的参数是个协程函数，返回协程，相当于传入一个根据自己协程返回新协程的函数，然后再flat_map内执行这个函数，从而实现每个元素生成一个新协程

4. 通用异步任务 Task