Boost.Container stable_vector - fjnlの生存記録のような何か

はじめに

本記事は partake.in 7日目です。

stable_vector

Boost 1.48からBoost.ContainerというSTL互換のコンテナライブラリが採用されました。基本的にはboost::container::vectorやboost::container::stringといったSTL互換のクラスが提供されていますが、boost::container::stable_vectorのようにSTLにはない独自のコンテナも提供されています。

(以下、stable_vectorと書いた場合はboost::container::stable_vectorを、vectorと書いた時はstd::vectorを示すものとします)

stable_vectorは名の示す通り(要素が)安定したvectorです。例えばvectorを用いて以下の操作を行うことを考えます。

vector<int> v;

v.push_back(1);
auto const it = v.begin();

for (int i = 2; i < 10; ++i)
  v.push_back(i);

// ↓この *it は大丈夫?
std::cout << *it;

最後の行にある *it をしてiteratorを参照しても大丈夫かどうかという問題です。forループで回されているpush_backによってiteratorが無効化(invalidated)されるかが鍵となります。N3290によると、vectorの末尾に要素を追加する際に v.size() + 1 > v.capacity() ならばiteratorが無効化されるとあります。したがって、上の問題の答えは、v.begin()でiteratorを保存した時のv.capacity()が10以上ならば大丈夫、となります。

insertとeraseの場合、話はもう1段階複雑になります。insertの場合、v.size() + (挿入される要素数) > v.capacity()ならばreallocationが発生し、全てのiteratorが無効化されます。reallocationが発生しないならば、挿入点よりも後の要素を指すiteratorのみ無効化されます。eraseの場合は、reallocationは一切起こらないので、削除点以降の要素を指すiteratorが無効化されます。

以上の例のように、vectorは操作によってiteratorが無効化されてしまうため、頻繁に要素を操作する場合、使いにくいと感じる場面があります。そのような時に使うのがstable_vectorです。

vectorは、格納されている要素の連続性を保証しているため、要素が移動した時にiteratorが無効化されやすいという問題がありますが、stable_vectorは、要素が並んでいる領域を連続確保するのではなく、図1のように要素を指すポインタを連続して確保する仕組みを取っています。リストのようですが、要素を指すポインタは連続して確保されているためランダムアクセスが可能で、また、挿入や削除が発生しても格納されている要素は移動しないためiteratorが無効化されることはありません。また、コンテナ中央に要素を挿入削除した場合、vectorではそれ以降の全要素をmoveする必要があるのに対して、stable_vectorではポインタをcopyするだけで済み、低コストとなる場合があります。

図1: stable_vectorの要素の配置の概念図。

一方で、stable_vectorは要素の安定性を重視しているため、各種性能ではvectorやlistに劣る面もあります。要素のアクセスのために一回余計に間接参照をしなくてはいけないため、vectorよりも遅くなりますし、要素本体が連続している保証がないため、キャッシュ効率も悪くなるでしょう。また、vectorよりも多くのメモリを必要とします。boostのドキュメントによると、(c + 1)p + (n + 1)(e + p) 分のメモリが必要であるとされています。ここで、c=capacity(), p=sizeof(T*), n=size(), e=sizeof(T)です。vectorではc×e分の空間しか必要としないのと比べると多いことがわかります。ただし、一部の場合でstable_vectorの方が省メモリである場合もあります(どのような場合にそうなるかはdocumentを読んでください)。c>>nであることが多いことと、要素を格納するための領域が、vectorはc×e分確保しますが、stable_vectorはn×e分しか確保しないためです。(まめにshrink_to_fitするならば、全く勝目がありませんが…)

まとめ

vectorの直接的な代替というよりは、listの代替の位置付けに近いと思います。要素の安定性や中央への挿入削除速度が必要で、かつ、ランダムアクセスが必要な場合にstable_vectorは威力を発揮します。

8日目は id:tt_clown さんの担当です。よろしくお願いします。