当記事は「C++ Advent Calendar 2013」の20日目の記事です．
2013/12/21 追記 : 進捗できました
どうも，@wx257osn2で名乗ったほうが通じやすいIです．[^1]
Twitter及びC++を初めて早3年，C++ Advent Calendar念願の初参加でしたが，
大変深い悲しみを帯びた旨とその経緯について綴ります…
see N3797 §20.4[tuple]
C++11でconstexpr-Lambdaを作ろうとしてたらC++11でconstexprなtupleが欲しくなって， さらにlibstdc++/libc++共に線形実装であったこと，ちょうど同時期にのじ(@fimbul11)さんが [テンプレートパラメーターパックへのインデックスアクセスの対数実装を確立した][fimbul11_slidshare]ことから 「なんか線形実装ダサい[要出典]し，対数オーダーで実装できそうだからやってみよう」と 言った感じで作り始めた代物です． 構築，getによるアクセス，及びtupleに関連する各種アルゴリズムの再帰深度を対数オーダーで実装し， また(後付で)インターフェースは出来る限りC++標準のそれに近づけることを目標としました． ちなみに，再帰深度が対数オーダーである利点は，簡単に言えば「コンパイルが通る要素数の上限が増える」ことです．
コードはこちらにあります．ただしとても汚いです．
対数オーダーでデータを扱うということで，とりあえず平衡木っぽい木構造をとれば良さそうな気がした[^2] ので
適当に調べてみたのですが，constexprですし副作用は起こさないという前提で話を進めようとすると，
世間に数ある木構造の中でも，風のうわさに聞く「赤黒木」とかの2分探索木は基本的に「回転」という操作でもって計算量を減らしてるみたいで，
副作用起こさずに回転させるとなるとその都度木を再生成せざるを得ず，旨味が少なそうです．
そんなわけで，面倒臭かったので黙ってただの二分木で作ることにしました．[^3] 名前はvalue_btreeとしました．
なお，今回の二分木は葉のみならず各ノードが値を持ちます．
ひとまず，make_tupleみたいな形で構築できるようにしようとしました． 二分木の実装ですが，constexprなのでデータ構造は型で決めねばなりません． というわけで，テンプレートパラメーターパックから二分木の構造を型で構築し， 二分木型がコンストラクタで関数パラメーターパックを受け取って子に引数を流す，という実装にすることにしました． が，最初にここで躓きます．平衡2分木(平衡2分探索木ではなく，平衡木である2分木です)にするために， テンプレートパラメーターパックを大体半分に分けなければならなくなりました．
template<typename... Types>class value_btree
↓
template<typename T, typename... Lefts, typename... Rights>class value_btree
//sizeof...(Lefts)とsizeof...(Rights)はほぼ同じ要するに，
TypesのtailをLefts...とRights...に分割value_btree<Lefts...>とvalue_btree<Rights...>を再帰的に生成
という手順です．今考えてみると，のじさんのtype_atの手法で半分に分割できそうな気もしますが， とりあえず当時は全く浮かばなかったので，後輩のHaskeller[^4] にヘルプを投げてみたところ， 「最初から分けなくてもいいんじゃないの」という指摘をくれました． なんでも，リストから二分木への変換なら先頭から読んでいって， 作った木と余った要素を再帰で処理していけば間に合うとのこと．
- Typesのtailを全て
Lefts...とし，生成する木のノード数(これは計算で簡単に求まる)と共にvalue_btree生成器に渡す - 生成した時に余ったテンプレートパラメーターパックを
Rights...として，同様にvalue_btree生成器に渡す - それでも余ったものはこの木の余りとし，親のノードに返す
と言った感じです．これで，対数オーダーで型を二分木様に配置することが出来ました．
が，しかしここでさらに躓きます．二分木のコンストラクタで受け取る引数の型が無くなってしまったのです．
例えば，value_btree<A, value_btree<B, value_btree<C, D>, value_btree<E, F, G>>, value_btree</*hoge*/>>という二分木があったとします．
中の二分木はB, C, D, E, F, Gをコンストラクタの引数の型として持ち，かつC, Dが左のノードの，
そしてE, F, Gが右のノードのコンストラクタに渡す型であることが分かる必要があります．
最初に私が取ろうとした手法ならば，根のLefts...がそれに当たりますし，
正しく2分割できる(はずな)のでLefts...のtailを分ければ必然的に子のノードに渡す型も確定します．
しかし，今回採用した手法だとvalue_btreeに親から渡される型はG以降の消費しない余り(/*hoge*/の部分で使われる型)も含まれます．
そのため，それをそのまま使う訳にはいきません．
そういうわけで，引数の型をそのノードの子孫から再生成する，という方法を取りました．
つまり，自身のBと，左側の子からC, D，そして右側の子からE, F, Gを受け取り，それらを結合した型を親に要求するようにしたのです．
結果，value_btreeのテンプレートパラメータが大分キモいことになってしまいました．ただまぁ，実装部分なのでいいかなぁってことで妥協しました．
なにはともあれ，対数オーダーで値を取り出せるデータ構造を対数オーダーで構築できるようになりました． Clangでlong long8192要素のvalue_btreeでもちゃんと生成できます[^5]． 成し遂げだぜ．
ここで，欲が出ます．「標準ライブラリと同じインターフェースにすれば代替品になりうるんじゃないか？」 というわけで，N3797[^6] の§20.4と20.5を印刷し，適当に読んでみました． アロケーター周りはかったるいのでとりあえず飛ばして，残りの部分には手を付けられそうかな？と思ったので作り始めました．
この過程に関しては，教職によってマシマシされた課題/試験とか，大学のサークルで色々増えたジョブとか，「如何にして時間を割くか」が主な課題でした[^7]． あと，今なら某中3女子の「[ひたすら労力][bolero_slideshare]」という言葉がよく分かります． ライブラリは労力です．つらい．
そんな感じで各種非メンバ/メンバ関数を作ってたのですが，tuple_catとかいうのが滅茶苦茶面倒臭い…というか， そもそも最初規格書読んだ時に仕様が唯一理解できなかった代物がこれでした． で，とりあえずtupleのvalue_btreeを構築して下から結合していく，という戦略をとったのですが…ここでもやっぱり躓きます． 実を言うと，最初はgetをtupleやvalue_btreeのメンバ関数として定義してました． しかし，皆さんご存知の通りC++11のconstexprの仕様はメンバ関数との相性がすこぶる悪いです． 結論から言うと，tuple_catはソースとなるtupleを新たなtupleにforwardingしてやらないといけないのですが， constexprなgetメンバ関数はconstメンバ関数になるのでforwardできない，という話です． また，同様の都合でvalue_btreeへのtuple_cat実装関数適用部分もvalue_btreeがforward出来ない状態でした． そんなわけで，tuple_catの実装で都合が悪くなってしまったので，ここでgetを非メンバ関数に変更します[^8]．
その後変な勘違いをしたせいでえらい時間を取られたり，大量のエラーに見まわれつつも何とか動くレベルに持ってきて， ようやくGCCでコンパイルも通りました．と，もう既にAdvent Calendar公開日が半分終わってしまっていますね．急ぎましょう．
犬小屋の結果
もうだめです，疲れました．というか，タイムリミットです．そういうわけで，そろそろ諦めて公開します．だれか助けてください(切実)
- テストケースを増やす
- どう考えてもテストケースが少ないです．増やします．
- 整形とか
汚ねぇ． 表現もバラバラですし，1行が長すぎるし，ちょっと色々とヤバいです．メタメタしてるのとは別の意味で魔窟になってしまっています．読めたものではないので，なんとかします．- 2013/12/21 追記 : done. …まぁ，どっちみち汚いのですが，かろうじて人類に読めるレベルにはなりました．
- 修正
Clangさんで動かしたいです．- 2013/12/21 追記 : done.
- ライブラリ化
- ある程度まともに仕上がったらveilerに入れます．
駄文が続きましたが，結論としては進捗ダメでした．
なにかあればTwitterにお願いします．というか，助けてくださいお願いします．
明日は21日目，hr_saoさんのC++/CXについての記事です．
[^1]: 「あい」って読んでくださいね，たまに「いち」とか「える」とか言われますが「あい」です．
[^2]: 競技勢のすごい人たちとは違って私はデータ構造とかアルゴリズムとかに対して無知です．
[^3]: この時点ではまだconsとかで関数型プログラミングにおいて二分木が基本的なデータ構造として使われているという事実は知らなかったです．
[^4]: 知ってる人は知ってるあの子です．今回のような関数型プログラミングの事案では私なんかでは遠く及ばないほど理解がありますし，C++も少々嗜んでますし，とにかく引き出しが豊富なのでとりあえず困ったら頼ってます．すぺしゃるさんくす．
[^5]: なんでC++11向けのを作っているのにC++14のWDを持ってきたのか，というと，constexprなtupleの標準のインターフェースが知りたかったとか，applyのインターフェースが知りたかったとか，そんなところです．
[^6]: この時点での話です．メモリを18GBだか19GBだか食ってたような記憶があります．
[^7]: そして11月中全く時間を割かなかった結果12月入ってから死に物狂いで実装することになりました．
[^8]: 昨日のお話です．なお，この時点ではGCC/Clang共にコンパイルが通っていますが，何を血迷ったかこの時点でのコードを残していません．git使おう．
[fimbul11_slidshare]: http://www.slideshare.net/yoshihikoozaki5/tmp-web-28084468 "Template Meta Programming 入門から応用まで"
[bolero_slideshare]: http://www.slideshare.net/GenyaMurakami/constexpr-29223898 "すごいconstexprたのしくレイトレ！"