これはまあ簡単です。基本的には 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 で速度が気になったので性能比較をしました。
性能比較のソース| 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 |
確かに検索が二倍速いです。 看板に偽りなし、たいしたものです。 挿入が遅いですが、これはひとつずつ挿入しているため、 毎回ソートされた状態に保つ手間です。 まとめて挿入すれば、とても早く、かなり優秀なコンテナです。
全てリンクフリーです。 コード片は自由に使用していただいて構いません。 その他のものはGPL扱いであればあらゆる使用に関して文句は言いません。 なにかあれば下記メールアドレスへ。