たぶん究極のC++ライブラリ、Lokiを使う - AssocVector

since: 2002-02-21 update: 2002-04-13 count: 17645

これはまあ簡単です。基本的には STL の map 。違いをまとめてみると、

map AssocVector
要素の追加・削除 O(log N) O(N)
要素の探索 O(log N) O(log N) / 2
要素の追加・削除で
iterator が無効化
しない する
value_type std::pair<_Key, _Val> std::pair<const _Key, _Val>
イテレータ Bidirectional RandomAccess

O(log N) / 2 ってのは map より二倍速いってことを表したつもりです。 二倍ってのは Modern C++ Design に書いてあったけど なんか理論的な根拠があるものなんですかね。 たぶん経験的なものだろうと思うのですが、調べてません。

この map もどきは基本的にベクタを常にソートした構造になっていて、 新しい要素が入ったり削除されたりすると、 ソートされた状態を保つために O(N) の計算量を使って要素を移動します。 しかし、探索は map より速く、メモリ効率も良いので、 挿入ー探索ー削除の順番でのみ行われるような作業 (map を使った作業は少なく見積もっても半分位はこれだろう) では、こっちを使え、ということらしいです。

ま、API は map と一緒だし、明日からでも手軽に使っていけますね。

Effective STL 第23項がこの話題について詳しいです。

サンプルコード

SmallObj で速度が気になったので性能比較をしました。

性能比較のソース
cppll で紹介されていた StopWatch クラス
ちなみに、 cppll
std::map Loki::AssocVector
50000回挿入 0.11 14.04
100000回検索(50000要素) 0.19 0.10
50000回削除 0.03 13.94
10000回挿入 0.01 0.14
100000回検索(10000要素) 0.08 0.04
10000回削除 0.01 0.17
50000要素まとめて挿入 0.13 0.02

確かに検索が二倍速いです。 看板に偽りなし、たいしたものです。 挿入が遅いですが、これはひとつずつ挿入しているため、 毎回ソートされた状態に保つ手間です。 まとめて挿入すれば、とても早く、かなり優秀なコンテナです。


home / index

全てリンクフリーです。 コード片は自由に使用していただいて構いません。 その他のものはGPL扱いであればあらゆる使用に関して文句は言いません。 なにかあれば下記メールアドレスへ。

shinichiro.hamaji _at_ gmail.com / shinichiro.h