FC2ブログ

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

赤黒木

赤黒木。STLのset,mapの実装(の殆ど?全部?)に使われているやつ。
何でSTLで使えるものを書いたかといえば、下記の理由から。

・コピーが格納されて欲しくない
一番の理由。
あるオブジェクトを木構造で管理したいけど、STLを使うとコピーが格納されてしまう。けどコピーは格納されて欲しくない。ポインタを格納して比較ファンクタを用意するとか、STLを使おうとするとどうしてもスマートじゃない方法になってしまう。

・色の持ち方(=メモリ使用量)
VC90の実装だとchar型のメンバ変数を色の保持に使ってた。ポインタのアライメントが保障されているとポインタの下位bitに格納することが出来るのでメモリ使用量を減らせる。1byteぐらいどーでもいいじゃん
アロケータのアライメントに関する規定があったはずだから標準でも出来ないことはないんだろうけど、なんでやってないんだろう?規定があるのはCだけだっけ?

・アロケータ
アライメントの保障とか。自前のアロケータを使おうとすると色々面倒とか。アロケータを混在させたいときとか。

参考文献:
Robert Sedgewick "Left-Leaning Red Black Trees" (PDF)

下記みたいな感じで使う。継承使ってるあたりに特に理由は無い。
ヘッダーのL46より下はサンプルみたいなもの。この辺は使う側で要求に合わせて実装したほうがいい。



スポンサーサイト

コメントの投稿

非公開コメント

検索フォーム
ユーザータグ

ICPC 2009 国内予選 ゲームプログラミング 

カテゴリ
最新記事
月別アーカイブ
最新コメント
最新トラックバック
リンク
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。