這次研究基于的項(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):
- 協(xié)程
- 函數(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)注微信公眾號碧注,一起交流