boost::container::stable_vector
今年7月のアーティクル『std::vector観察記録』で、「どのコンテナ使うか迷ったら、ひとまずvector使っとけ」と述べました。std::vectorは構造がシンプル（ゆえにコンパクト）で高速、各要素が連続領域に配置されるためにランダムアクセスでき、さらに先頭要素のアドレスがそのまま配列の先頭として扱えるのでCとの親和性に優れます。が、この特性が時として仇となることもあります。
std::vectorは要素の連続性を維持するために、挿入／削除のたびに要素のコピーが行われます。コピーにコストのかかるデータの集合としてstd::vectorを用いるとパフォーマンスを大きく落としかねません。加えてstd::vectorのイテレータはとても"はかない"ものです。とある要素を指すイテレータは挿入／削除が行われるとあっけなく無効化されてしまいます。このような特性が好ましくないケースではstd::listをその代替に使うこともできますが、そのかわりイテレータでランダムアクセスできなくなります。
stable_vectorは要素の挿入／削除にコピーを伴わず、イテレータも無効化されません（それが指す要素が削除されるのでなければ）。さらにランダムアクセスできてしまう魅力的なコンテナです。
コンストラクト／デストラクトやコピーの様子をモニタする要素クラス:itemを要素としたstd::vector<item>とstable_vector<item>に、item-0 ～ item-4 を挿入し、その様子を観察します。
#ifndef ITEM_H__
#define ITEM_H__
#include <iostream>
class item;
std::ostream& operator<<(std::ostream& stream, const item& x);
class item {
private:
int x_;
int y_;
public:
item(): x_(0), y_(0)
{ std::cout << "ctor()" << std::endl; }
item(int x, int y =0): x_(x), y_(y)
{ std::cout << "ctor(int x, int y) x=" << x << ", y=" << y << std::endl; }
item(const item& other): x_(other.x_), y_(other.y_)
{ std::cout << "ctor(const item& other) other=" << other << std::endl; }
item(item&& other): x_(other.x_), y_(other.y_)
{ std::cout << "ctor(item&& other) other=" << other << std::endl; }
~item()
{ std::cout << "dtor() *this=" << *this << std::endl; }
item& operator=(const item& other) {
std::cout << "copy(const item& other) other=" << other << std::endl;
x_ = other.x_;
y_ = other.y_;
return *this;
}
item& operator=(item&& other) {
std::cout << "copy(item&& other) other=" << other << std::endl;
x_ = other.x_;
y_ = other.y_;
return *this;
}
std::ostream& print_on(std::ostream& stream) const
{ return stream << '{' << x_ << ',' << y_ << '}'; }
};
inline std::ostream& operator<<(std::ostream& stream, const item& x) {
return x.print_on(stream);
}
#endif
void item_copy() {
cout << "\n=== item copy\n";
{
cout << "\n--- std::vector \n--- 5 insertions\n";
std::vector<item> v;
for ( int i = 0; i < 5; ++i ) {
v.emplace_back(i);
}
cout << "--- remove an item from front\n";
v.erase(v.begin());
cout << "--- that's it.\n";
}
{
cout << "\n--- boost::container::stable_vector\n--- 5 insertions\n";
boost::container::stable_vector<item> sv;
for ( int i = 0; i < 5; ++i ) {
sv.emplace_back(i);
}
cout << "--- remove an item from front\n";
sv.erase(sv.begin());
cout << "--- that's it.\n";
}
}
std;;vectorへの要素の挿入に伴い、要素のコピー（コピー・コンストラクト）が頻繁に行われている様子が見て取れます。一方stable_vectorでは要素のコピーが一切行われていません。
要素を5つ挿入し、中ほどの要素を削除したときの、各要素のアドレスを調べてみました。
void memory_usage() {
cout << "\n=== memory_usage\n";
{
std::vector<int> v;
for ( int i = 0; i < 5; ++i ) {
v.emplace_back(i);
}
cout << "\n--- std::vector : before\n";
for ( const int& val : v ) {
cout << setw(4) << val << " @ " << static_cast<const void*>(&val) << endl;
}
cout << "\n--- std::vector : after\n";
v.erase(begin(v)+2);
for ( const int& val : v ) {
cout << setw(4) << val << " @ " << static_cast<const void*>(&val) << endl;
}
cout << endl;
}
{
boost::container::stable_vector<int> sv;
for ( int i = 0; i < 5; ++i ) {
sv.emplace_back(i);
}
cout << "\n--- boost::container::stable_vector : before\n";
for ( const int& val : sv ) {
cout << setw(4) << val << " @ " << static_cast<const void*>(&val) << endl;
}
cout << "\n--- boost::container::stable_vector : after\n";
sv.erase(begin(sv)+2);
for ( const int& val : sv ) {
cout << setw(4) << val << " @ " << static_cast<const void*>(&val) << endl;
}
}
}
std::vectorは各要素がメモリ上で整列しているのに対し、stable_vectorでは飛び飛びになってますね。どんなカラクリなのか、メモリの取得／解放をモニタする特製allocatorを仕込んでみると……
void memory_detail() {
cout << "\n=== boost::container::stable_vector\n--- 3 insertions\n";
boost::container::stable_vector<int,epi::mallocator<int>> vv;
for ( int i = 0; i < 3; ++i ) {
vv.emplace_back(i);
}
for ( int item : vv) {
cout << item << ' ';
}
cout << endl;
}
……なんだか複雑。Boost.Containerのドキュメントによりますと、stabe_vectorの内部ではこんなメモリ管理を行っています。
ポインタ配列の各要素にnodeがぶら下がってて、各ノードは逆方向のポインタを持ってます。んでもって、stable_vectorのイテレータは各nodeを指します。なので、あるイテレータについて、
- nodeからnode*列に上がって
- そこからn個移動し（ポインタにnを加え）
- nodeに降りる
という操作でn個隣に飛び移ることができます。こんなカラクリでランダムアクセスを実現してますから、例えばstd::sort()でソートできます。
また、この構造により、とある要素を指すイテレータは（その要素を削除しない限り）要素の挿入／削除に伴って無効になることがありません。
