2色木（赤黒木）を実装してみた

タイトルのとおりです。
アルゴリズムイントロダクションを読んで理解したことを実装してみたら、想像以上にパフォーマンスが出たので紹介します。
アルゴリズム的な面白さは特に無いです。
言語はC++です。作成した2色木はC++のstd::mapライクなインタフェースを備えています。

ソースの場所→　https://github.com/risuoku/oreore/blob/master/algorithm_introduction/src/data_structure/rb_tree.h
検証用→　https://github.com/risuoku/oreore/tree/master/algorithm_introduction/test/data_structure/rb_tree

やったこと

• std::pairなデータを生成。データ数は5000000。
• oreore::map, std::map, std::tr1::unordered_map それぞれに対して生成したデータをinsert, findして、処理に必要な時間を調べた
• oreore名前空間に入ってるmapが今回作成したものです

なぜmapなのか

処理系依存だと思いますが、std::mapは大体2色木で実装されているそうです。
*1
なので、今回作成した2色木もmapと名付けました。

結果

下に示すグラフのとおりです。
縦軸が処理にかかった時間（sec）で、もちろん小さいほど良いです。
oreoreは機能が単純だからか、stdより処理が高速です。
メモリ使用量については、vmstatで簡単に見た程度ですが、どれも大差ありませんでした。unordered mapが若干少なかったかもしれません。
unorderd_mapは2色木ではありませんがインタフェースが同じなため一応比較しました。
実用的には、unordered_mapを使うといいのかもしれません。

数学的基礎とデータ構造 (アルゴリズムイントロダクション)

*1:http://research.preferred.jp/2011/07/stllike-containers/