出于什么样的原因，诞生了「协程」这一概念？

协程的理论模型是“有多个入口的带状态的函数”，通常我们把带状态的函数叫做“闭包”，所以协程也就是“有多个入口的闭包”。所以相比“闭包”，协程是一个更加“通用”的概念。

在现实世界中，我们使用协程的主要目的是把代码转化为对人更友好的形式，有两种典型的应用场景：

1. 作为 generator，来生成序列
2. 用顺序代码实现 IO 多路复用：在原本需要阻塞线程的地方，切换到同一线程的其它协程

举例来说：

1. 作为 generator，来生成序列

我们以二叉树中序遍历为例：

void walk(Node* p) {
  if (!p) return;
  walk(p->left);
  printf("%d\n", p->data);
  walk(p->right);
}
复制

这个 walk 代码，把业务代码（printf）和算法绑定到了一起。我们要把这两者拆分开来，有两种办法：

1.1. 使用回调函数

void walk_algo(Node* p, void(*visit)(Node*, void*), void* context) {
  if (!p) return;
  walk_algo(p->left);
  visit(p, context);
  walk_algo(p->right);
}
void do_visit(Node* p, void* maybe_useful_context) {
  printf("%d\n", p->data);
}
void walk(Node* root) {
  walk_algo(root, &do_visit, nullptr); // null context
}
复制

1.2. Iterator 抽象

就像 std::map/set 那样的二叉树 iterator 实现，比较复杂，就不写了。

标准库中的 map/set 一般使用红黑树，也可以使用 AVL 树，为了更简洁高效地实现 iterator，树结点中一般会有 parent 指针。
如果不使用 parent 指针，就需要 Iterator 自己管理一个栈，或者使用更复杂的线索二叉树。

---------------------

1.3. 使用协程

我们以 boost callcc 为例（C++20 的协程对递归的支持如何不太清楚）：

void walk_fn(Node* p, Node** seq_value, continuation& c) {
    if (p) {
        walk_fn(p->left, seq_value, c);
        *seq_value = p; // 这两句相当于
        c = c.resume(); // 一般 coroutine 的 yield p
        walk_fn(p->right, seq_value, c);
    }
}
void main() {
    Node* curr = nullptr;
    auto walk = callcc([root, &curr](continuation&& c) {
        walk_fn(root, &curr, c);
        return std::move(c);
    });
    while (walk) {
        printf("%d\n", curr->data);
        walk = walk.resume(); // 这句相当于 await
    }
}
复制

看上去似乎更烧脑，这是因为 callcc 在保持一定抽象的同时，还要追求极致的性能，如果愿意付出一点性能代价，可以进行一些合理的包装，变成容易理解的形式：

template class Generator {
    continuation src, sink;
    SeqValue result;
public:
    template explicit Generator(Func src_fn) {
        this->src = callcc([src_fn,this](continuation&& _sink) {
            this->sink = std::move(_sink);
            src_fn(*this);
            return std::move(this->sink);
        });
    }
    void yield(const SeqValue& v) { result = v; sink = sink.resume(); }
    Generator& operator++() { src = src.resume(); return *this; }
    SeqValue operator*() const { return result; }
    explicit operator bool() const { return static_cast(src); }
};
void walk_g(Generator& g, Node* p) {
    if (p) {
        walk_g(g, p->left);
        g.yield(p->data);
        walk_g(g, p->right);
    }
}
void use_walk_g(Node* root) {
    Generator src([root](Generator& g) { walk_g(g, root); });
    for (; src; ++src)
        printf("%d\n", *src);
}
复制

这个 Generator 模板类，短短十来行代码，在 callcc 的基础上，通过那么一点点性能代价，实现了必要的抽象。

这个场景，属于“对称式”协程，没有调度器，多个协程之间精密合作，效率可以达到最高。

boost.callcc 使用了 boost.context，属于“有栈协程”，其协程切换代价与单次函数调用在一个量级（官方文档中写到是 19 CPU cycle）。

2. 用顺序代码实现 IO 多路复用

这个一般需要专门的 IO 调度器，基于（操作系统发出的）事件，在调度器中选择发生了 IO 完成事件的那个 Fiber 并唤醒它。

在这里就不生编硬造例子了，给大家一个现实案例：大道至简，事半功倍：MultiGet IO 并发在 ToplingDB 中的协程实现，以及在 MyTopling 中的落地应用 - 知乎 (zhihu.com)