C++コルーチンを完全に理解した。
まず、コルーチンの戻り値型TはPromiseオブジェクト型T::promise_typeを持っていなければならない。そしてこいつのメンバ関数を指定の名前で色々実装することでコルーチンの挙動を決められる。
コルーチンが走るとまずT::promise_type::get_return_object()が呼ばれる。ここでT型オブジェクトを返さなければならない。コルーチンのコンテキストはstd::coroutine_handleによって管理される。Tのメンバ変数としてcoroutine_handle<T::promise_type>を持たせ、それをget_return_object()内で初期化するのがセオリーのようである。
コルーチンの本質は「中断可能な関数」である。ここで気を付けたいのは「中断してもいいし、中断しなくてもいい」ということだ。promise_typeおよびAwaitオブジェクトの実装によって「いつ中断して、いつ中断しないのか」を制御することが出来る。具体的には以下のポイントにおいて、中断するか否かを決めることができる。
- コルーチン呼び出し直後
- 各
co_await、co_yield時 - コルーチン終了時(注: ここは必ず中断しないと未定義の動作)
コルーチン呼び出し直後と終了時はそれぞれT::promise_type::initial_suspend()、T::promise_type::final_suspend()co_awaitに指定するのもAwaitオブジェクトである。つまり究極的にはAwaitオブジェクトの実装がコルーチンが中断するかどうかを決める。
Awaitオブジェクトはawait_ready(), await_suspend(), await_resume()を実装するオブジェクトだ。await_ready()の戻り値によって、コルーチンを中断して処理を戻すか、そのまま続行するかを選べる。なお、std::suspend_alwaysやstd::suspend_neverという標準で準備された自明なAwaitオブジェクトもあるのでこれで十分な場合も多い。
とにかくこれらの仕組みによって、コルーチンの呼び出し側とコルーチンの実装側双方に意識させることなく、promise_typeとAwaitオブジェクトの実装者がコルーチンの挙動を制御できる。
co_yieldやco_returnで値を返すような処理はこれらの上に立っており、はっきり言って別枠としてちょっこし整備されているにすぎない。co_yield hoge;はco_await handle.promise().yield_value(hoge);の単なるシンタックスシュガーである。ここでpromise_type::yield_value()の実装によってPromiseオブジェクトに値を記録しておくことができるので、呼び出し元で参照できるようにというだけの話だ。
なお、yield_value()はAwaitオブジェクトを返すということは、co_yield hoge;した結果としてコルーチンを中断しないことだってできるということである。実際問題なくできる。そんなのやったら呼び出し元から値参照できないんじゃねえかよ？と思うかもしれないが、そこもまたyield_value()の実装次第の話なので、例えばPromiseオブジェクトのメンバ変数としてqueueとかを持っておいて、コルーチンの中断はせずにそこに値を詰め込むといった実装をすれば必ずしも毎回中断しなくても値を参照できる。
天気が良いので外を散歩した。最近野草を調べるのに少しハマっている。いつも道端で見かけるものの名前も知らないのもどうかと思って手当たり次第にGoogleレンズを使い始めたのがきっかけだ。
タンポポ、シロツメクサ、ハルジオン、ヒメジョオンは覚えた。かなり色々なところで見かける。今日はイヌムギ、ネズミムギ、セイタカアワダチソウ、チガヤなどを覚えた。あとヨモギも葉っぱが特徴的だ。ギシギシは名前だけ知っていたが、今日ようやく名前と形が一致した。
ゼニアオイという花も見つけて覚えた。どうやらハーブとして有名なコモンマロウはこいつのことらしい。
ある草は先っぽが特徴的で、調べてみるとオオバコというやつに似ているのだが、どうも葉の形が明らかに違う。もっと調べるとヘラオオバコという種があるらしく、それらしかった。
ヌルデという植物は、細い枝に単純に葉が付いているかと思いきや、よく見ると枝の両脇も葉になっているのが面白い。触るとややかぶれるらしい。
コバンソウというのも見た目が面白かった。最初一見して虫か何かかと思ってしまったが、よく見ると稲穂の類のものだ。指でつぶすとパキパキと言って分解しながら崩れる。
ABC354に出た。
A: whileで回した
B: やるだけ、分かりにくい内輪ネタ…
C: てこずった。最初から二次元平面にプロットして考えればよかった。
D: 周期性を利用してがんばる。こういうやつのよくやる手として、[0,x][0,y]の成す長方形の値を計算する関数を作った上でそれを4回使って包除をやるというのがある。
E: Nが小さいので任意のカードの集合を全探索できる。遷移先も高々N^2なので、$O(2^N N^2\log N)$で真面目にgrundy数を求めればよい。mexの実装で微妙にミスして少し手間取った。ライブラリ化しても良いかもしれない。
F: 最後尾がAtであるようなLISと先頭がAtであるようなLISの長さを求めればいい、という方針は立ったが、その方法が分からなかった。思いつかなかったの普通にショックだが、DPの途中で何かをメモるのは普通に典型だ。
Categories: 未分類