conduit: 現(xiàn)代C++的協(xié)程與函數(shù)式編程

這次研究基于的項(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

歡迎關(guān)注微信公眾號碧注,一起交流
兆華雜記
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末峻贮,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子应闯,更是在濱河造成了極大的恐慌纤控,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,946評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件碉纺,死亡現(xiàn)場離奇詭異船万,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)骨田,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,336評論 3 399
  • 文/潘曉璐 我一進(jìn)店門耿导,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人态贤,你說我怎么就攤上這事舱呻。” “怎么了悠汽?”我有些...
    開封第一講書人閱讀 169,716評論 0 364
  • 文/不壞的土叔 我叫張陵箱吕,是天一觀的道長。 經(jīng)常有香客問我柿冲,道長茬高,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,222評論 1 300
  • 正文 為了忘掉前任假抄,我火速辦了婚禮怎栽,結(jié)果婚禮上丽猬,老公的妹妹穿的比我還像新娘。我一直安慰自己熏瞄,他們只是感情好脚祟,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,223評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著强饮,像睡著了一般愚铡。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上胡陪,一...
    開封第一講書人閱讀 52,807評論 1 314
  • 那天沥寥,我揣著相機(jī)與錄音,去河邊找鬼柠座。 笑死邑雅,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的妈经。 我是一名探鬼主播淮野,決...
    沈念sama閱讀 41,235評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼吹泡!你這毒婦竟也來了骤星?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,189評論 0 277
  • 序言:老撾萬榮一對情侶失蹤爆哑,失蹤者是張志新(化名)和其女友劉穎洞难,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體揭朝,經(jīng)...
    沈念sama閱讀 46,712評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡队贱,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,775評論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了潭袱。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片柱嫌。...
    茶點(diǎn)故事閱讀 40,926評論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖屯换,靈堂內(nèi)的尸體忽然破棺而出编丘,到底是詐尸還是另有隱情,我是刑警寧澤彤悔,帶...
    沈念sama閱讀 36,580評論 5 351
  • 正文 年R本政府宣布嘉抓,位于F島的核電站,受9級特大地震影響蜗巧,放射性物質(zhì)發(fā)生泄漏掌眠。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,259評論 3 336
  • 文/蒙蒙 一幕屹、第九天 我趴在偏房一處隱蔽的房頂上張望蓝丙。 院中可真熱鬧,春花似錦望拖、人聲如沸渺尘。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,750評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽鸥跟。三九已至,卻和暖如春盔沫,著一層夾襖步出監(jiān)牢的瞬間医咨,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,867評論 1 274
  • 我被黑心中介騙來泰國打工架诞, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留拟淮,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,368評論 3 379
  • 正文 我出身青樓谴忧,卻偏偏與公主長得像很泊,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個(gè)殘疾皇子沾谓,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,930評論 2 361

推薦閱讀更多精彩內(nèi)容