読者です 読者をやめる 読者になる 読者になる

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を組み合わせることにより幅広い再起関数を再起を用いずに書き直すことができるであろう

ちなみにこの方法、どうもメモリをドカ食いするとの話も出ている
コンパイル時マージソートの話|どっかのゆとりのチラシの裏

だがイテレータを使う方法は自分でもイケてると思う
実際実装するのはもういいよ。他の人が実装してくれたし