constexprで無限リスト作った
こんな感じ
struct Func { constexpr int operator()(int i)const { return i+1; } }; make_recurrence_list(0,Func{});//0,1,2,3,4...
無限だから長さを求めようとすると無限ループ起こしてコンパイラが死ぬ
単方向リストだから巻き戻しもできない
かいててラムダ式がconstexprだったらなぁとか考えた
gist
https://gist.github.com/Fuyutsubaki/a17eec9fb0735baaff92
wandbox
http://melpon.org/wandbox/permlink/Q1e32fdki75pTbmt
これの当初の使い方の予定はマージ関数の実装に使う予定であった
({},{1,3},{2,6})//result,left1,left2
このようなタプルを作り
({},{1,3},{2,6}) →({1},{3},{2,6}) →({1,2},{3},{6}) →({1,2,3},{},{6}) →({1,2,3,6},{},{})
のような関数を作り
find_if(make_recurrence_list(init,Func{}),is_empty_left)
のようにすれば自身は一度も倍分再帰を書くことなくマージ関数をO(logN)再起実装できる
マージ関数のみならず、無限リストとfindを組み合わせることにより幅広い再起関数を再起を用いずに書き直すことができるであろう
ちなみにこの方法、どうもメモリをドカ食いするとの話も出ている
コンパイル時マージソートの話｜どっかのゆとりのチラシの裏
