木構造のSTLライクなデザインの難しさ
昔からのテーマなのですが、木構造 ( std::map のように木を中に持っていて外からは配列的に扱えるものではなく、子や兄弟など階層をなすもの ) の STL ライクなデザインがなかなか難しい。
http://www.damtp.cam.ac.uk/user/kp229/tree/
今のところ上の tree.hh が暫定１位。とてもよいと思うのだが、GPLなのでお仕事で使えないのよ...。
STLライクなデザインを考えるとき begin() 〜 end() でいろいろたどりたいのだが、木なので、たどり方がいろいろある...。いろいろな iterator を用意するという手法があり、結構主流だ。子をたどるイテレーターと兄弟をたどるイテレーターを分けたり、子優先でたどるイテレーターをつけてみたり、親優先でたどるイテレーターをつけてみたり...。ちなみに tree.hh もそんな感じだ。
しかし、実際に木を使っていて思うのだが、子をたどるだけだったものが、イレギュラーに親が見たくなったり、兄弟が見たくなったりすることがある。そんなときにこのタイプの実装だと困ってしまうのだ。そういうときにいいなと思うのが、
http://www.grinninglizard.com/tinyxml/
TinyXml の木の実装。残念ながらこの木は読み込み専用なのだが、イテレーターとノードが一体化していて、実はこちらの方が使いやすい。ただ、ポインターがむき出しなので、現代的なデザインではない...。こぎれいな汎用な単純な仕組みがないだろうか...。
あとは root の置き場の問題も存在する。動的に0から作成される木の場合、root の置き場が問題となる。
tree< int > t; r.push_back( 100 );
等とすると、一見問題ない気がする。100 の格納されたルートノードができる。だが...
tree< int > t; r.push_back( 100 ); r.push_back( 1 ); r.push_back( 2 ); r.push_back( 3 ); r.push_back( 4 ); r.push_back( 5 );
うわ〜、root がいっぱい...(^^;)。たくさんルートがある木を許すというのも手だが何とも気分がよくない（これは主観の問題なので、人によりけりだとは思いますが）。ちなみに tree.hh には tree の中に既に root が含まれている。
ちなみに木より上位の概念であるグラフは boost によって、かなり小難しく実装されている。なんせ、デフォルトだと静的グラフだからだ。パッと見 visitor パターン使いまくりといった感じ。iterator の使い方も奇妙。tieって何...。
