這次研究基于的項(xiàng)目是 Github 上的 conduit蚁吝，項(xiàng)目作者應(yīng)該是在 C++20 尚未正式頒布時(shí)就寫好了疟位，里面包含的頭文件都是 <expriment/coroutine> 這樣的格式叭首。筆者用正式標(biāo)準(zhǔn)稍作改寫，發(fā)布在自己的 Gitee 上耸成，文末有鏈接漫萄。

先看示例主函數(shù)：

int main() {
  auto primes = range()
    >> map([](auto i) {return (3 + i * 2); })
    >> flatMap([primeVector = std::vector<int>()](auto c) mutable {
      return primeVector
        >> take(primeVector.size())
        >> find([c](auto p) { return c % p == 0; })
        >> count()
        >> orElse(just(c))
        >> find([](auto x) { return x; })
        >> forEach([&](auto p) { primeVector.push_back(p); });
      })
    >> startsWith(just(2))
    >> take(10);
  for (auto n : primes)
    std::cout << n << std::endl;
  return 0;
}

程序的功能就是找出前 10 個(gè)素?cái)?shù)，我們關(guān)注的重點(diǎn)不是這個(gè)算法如何（其實(shí)效率還是很高的）缀踪，而是看它的設(shè)計(jì)思想居砖，值得學(xué)習(xí)的主要有兩點(diǎn)：

1. 協(xié)程
2. 函數(shù)式編程

下面一一介紹。

協(xié)程

C++20 終于引入了協(xié)程驴娃，官方示例中有如下的例子：

generator<int> iota(int n = 0) {
  while(true) co_yield n++;
}
lazy<int> f() {
  co_return 7;
}

我原來以為 generator<T> 和 lazy<T> 都是標(biāo)準(zhǔn)庫提供的類奏候，后來才知道不是，只能新寫一個(gè)：

template<std::movable T>
class seq {
public:
  struct promise_type {
    seq<T> get_return_object() { return seq{ Handle::from_promise(*this) }; }
    static std::suspend_always initial_suspend() noexcept { return {}; }
    static std::suspend_always final_suspend() noexcept { return {}; }
    static void return_void() noexcept {}
    [[noreturn]] static void unhandled_exception() { throw; }

    std::suspend_always yield_value(T value) noexcept {
      current_value = std::move(value);
      return {};
    }
    std::optional<T> current_value;
  };
  using Handle = std::coroutine_handle<promise_type>;

  class iterator {
  public:
    void operator++() { m_coroutine.resume(); }
    const T& operator*() const { return *m_coroutine.promise().current_value; }
    bool operator==(std::default_sentinel_t) const { return !m_coroutine || m_coroutine.done(); }

    explicit iterator(const Handle coroutine) : m_coroutine{ coroutine } {}
  private:
    Handle m_coroutine;
  };

  explicit seq(const Handle coroutine) : m_coroutine{ coroutine } {}
  seq() = default;
  ~seq() { if (m_coroutine) m_coroutine.destroy(); }
  seq(const seq&) = delete;
  seq(seq&& other) noexcept : m_coroutine{ other.m_coroutine } { other.m_coroutine = {}; }

  seq& operator=(const seq&) = delete;
  seq& operator=(seq&& other) noexcept {
    if (this != &other) {
      if (m_coroutine)
        m_coroutine.destroy();
      m_coroutine = other.m_coroutine;
      other.m_coroutine = {};
    }
    return *this;
  }

  iterator begin() {
    if (m_coroutine)
      m_coroutine.resume();
    return iterator{ m_coroutine };
  }
  std::default_sentinel_t end() { return {}; }

private:
  Handle m_coroutine;
};

這個(gè)類在源項(xiàng)目中也有唇敞，但我改寫的這個(gè)版本更加簡明一些蔗草。主體代碼都是從官方文檔上參考來的，基本上不需要作什么修改疆柔，就能適用于大多數(shù)場合咒精。所以非常奇怪，為什么標(biāo)準(zhǔn)庫不直接提供一個(gè)能拿來就用的呢旷档？

這個(gè)類中模叙，promise_type 嵌套類可以自定義 operator new 和 operator delete，以提供自定義的內(nèi)存分配和回收操作鞋屈。源項(xiàng)目中有示例范咨，這里簡化去掉了。

有了 seq 類之后厂庇，我們就可以用它作為數(shù)據(jù)傳輸載體了：

template<typename T = unsigned long>
auto range(T b = 0) -> seq<T> {
  while (true) {
    co_yield b;
    ++b;
  }
};

這就是主程序中的 range() 函數(shù)渠啊，很簡單，就是從零開始依次生成整數(shù)序列权旷。那么它又是如何逐步轉(zhuǎn)化成素?cái)?shù)序列的呢替蛉？

函數(shù)式編程

首先定義一個(gè)概念和兩個(gè)輔助函數(shù)：

template<typename R>
concept sequence = requires(R & r) { r.begin(); r.end(); };

template<typename T>
T id(T const& x) { return x; }

template<typename T>
auto first(T&& xs) -> decltype(id(*xs.begin())) { return *xs.begin(); }

sequence 是個(gè)序列，滿足條件是只要它有 begin、end 兩個(gè)成員函數(shù)即可灭返。因此上面的 seq 類盗迟，以及標(biāo)準(zhǔn)庫中的常用容器，都是符合它的熙含。

下面看 map 函數(shù)的定義罚缕，主函數(shù)中就是使用它完成第一步轉(zhuǎn)換的：

namespace detail {
  auto map = [](sequence auto xs, auto f) -> seq<decltype(id(f(first(xs))))> {
    for (auto x : xs)
      co_yield f(x);
  };
}

auto map = [](auto f) {
  return [f](sequence auto&& xs) {
    return detail::map(std::forward<decltype(xs)>(xs), f);
  };
};

這就是典型的函數(shù)式編程思想，注意 map 在調(diào)用的時(shí)候傳入的參數(shù)是一個(gè) lambda 函數(shù)怎静，兩個(gè)函數(shù)返回的都是一個(gè) lambda 函數(shù)邮弹。也就是說，傳入不同的功能函數(shù)蚓聘，就能讓 map 去執(zhí)行不同的任務(wù)腌乡。

注意我將 xs 參數(shù)添加了 sequence 約束，但是對 f 沒有加夜牡，函數(shù)返回值類型也是使用 decltype 去推導(dǎo)与纽。這是因?yàn)楹瘮?shù)參數(shù)可以返回各種不同類型的值，因此 map 函數(shù)返回的類型塘装，在設(shè)計(jì)時(shí)是無法知道的急迂，只好交給編譯器去自動推導(dǎo)了。

再看 flatMap 函數(shù)蹦肴。與 map 函數(shù)的區(qū)別是僚碎，map 對每個(gè)元素只返回一個(gè)結(jié)果，而 flatMap 則對每個(gè)元素返回一個(gè)集合阴幌，再逐個(gè) yield：

namespace detail {
  auto flatMap = [](sequence auto xs, auto f) -> seq<decltype(first(f(first(xs))))> {
    for (auto x : xs) //每個(gè)元素
      for (auto&& y : f(x)) //調(diào)用函數(shù)之后生成一個(gè)序列
        co_yield std::move(y); //再逐個(gè)yield
  };
}

auto flatMap = [](auto&& f) {
  return [f](sequence auto&& xs) {
    return detail::flatMap(std::forward<decltype(xs)>(xs), f);
  };
};

主函數(shù)中就是使用 flatMap勺阐，對每個(gè)元素檢查其是否為素?cái)?shù)，如果是就 yield 并加入已有素?cái)?shù)序列矛双，如果不是那么空集合自然不會 yield渊抽，這樣就可以進(jìn)行過濾。

以下是 flatMap 函數(shù)所使用的 lambda 函數(shù)參數(shù)背零，添加了詳細(xì)注釋：

[primeVector = std::vector<int>()](auto c) mutable { //確保向量可修改
  return primeVector //已找到的質(zhì)數(shù)腰吟，vector（生存期同 flatMap）可以用>>
    >> take(primeVector.size()) //逐一拿出來嘗試
    >> find([c](auto p) { return c % p == 0; }) //找到一個(gè)就 yield & break
    >> count() //能整除就 yield 其序號（默認(rèn)返回零）
    >> orElse(just(c)) //左側(cè)無元素就 yield 右側(cè)无埃。結(jié)果要么 0徙瓶，要么 c
    >> find([](auto x) { return x; }) //再排除掉零，剩下要么 c嫉称，要么空
    >> forEach([&](auto p) { primeVector.push_back(p); }); //非空則加進(jìn)向量
}

首先侦镇，注意函數(shù)聲明了 mutable，這是因?yàn)?primeVector 的值是需要改變的织阅，如果不加 mutable壳繁，在 push_back 的地方就會出現(xiàn)編譯錯(cuò)誤。

注意到主函數(shù)和這個(gè) lambda 函數(shù)里都大量使用了 operator >>，它是重載了的闹炉，相當(dāng)于管道操作符：

template <sequence Xs, typename F>
auto operator >> (Xs&& xs, F&& f) {
  return f(std::forward<decltype(xs)>(xs));
}

Xs 加了 sequence 約束蒿赢，由于 vector 容器支持 begin、end 函數(shù)渣触，因此當(dāng)然也是可用的羡棵。

take、find嗅钻、count皂冰、forEach 這些函數(shù)基本上一看就知道做什么的，不再解釋了养篓。just 和 orElse 相對不常見秃流。

just 用于直接從元素生成序列：

template<typename...Xs>
auto just(Xs...xs) {
  if constexpr (sizeof...(xs) > 0) {
    using T = std::common_type_t<decltype(xs)...>;
    return [=]() -> seq<T> {
      T data[] = { (T)xs... };
      for (auto x : data)
        co_yield x;
    };
  } else {
    return []() -> seq<int> { co_return; };
  }
}

orElse 則是判斷給定序列是否為空，不為空則逐一 yield柳弄，否則調(diào)用 lambda 函數(shù)參數(shù)得到新序列：

namespace detail {
  template<sequence Xs, typename Xsf>
  auto orElse(Xs xs, Xsf xsf) -> seq<decltype(first(xs))> {
    bool hasElements = false;
    for (auto x : xs) {
      hasElements = true;
      co_yield x;
    }
    if (!hasElements) {
      for (auto x : xsf())
        co_yield x;
    }
  }
}

auto orElse = [](auto xsf) {
  return [xsf](sequence auto&& xs) {
    return detail::orElse(std::forward<decltype(xs)>(xs), xsf);
  };
};

最后看 startsWith舶胀，其實(shí)就是一個(gè)連接，將給定序列接在已有序列的頭部：

namespace detail {
  template<sequence Xs, sequence Ys>
  auto concat(Xs xs, Ys ys) -> seq<decltype(first(xs))> {
    for (auto x : xs)
      co_yield x;
    for (auto x : ys)
      co_yield x;
  }
}

auto startsWith = [](auto...xsf) {
  return [=](sequence auto&& ys) mutable {
    return detail::concat(xsf()..., std::forward<decltype(ys)>(ys));
  };
};

本文相關(guān) Github 項(xiàng)目：conduit

筆者改寫后的源碼：conduit.cpp

兆華雜記