boost::intrusive

abstract

必要なヘッダ

<boost/intrusive/*.hpp>

出来ること

侵入式コンテナ

リファレンス

en

sample

#include <iostream>
#include <boost/intrusive/list.hpp>
#include <boost/intrusive/list_hook.hpp>
using namespace std;

// intrusive::list に格納するための「フック」付きオブジェクト
class MyObject
	: public boost::intrusive::list_base_hook<>
{
public:
	MyObject(int v) : value(v) {}
	int value;
};

int main()
{
	MyObject* pa = new MyObject(100);
	MyObject   b(300);
	MyObject   c = b;
	b.value = 200;

	{
		boost::intrusive::list<MyObject> lst;
		lst.push_back(*pa);
		lst.push_back(b);
		lst.push_back(c);

		cout << pa << " == " << &lst.front() << endl; // *pa そのものがリストに直接入る
		cout << &c << " == " << &lst.back() << endl;  // 同様
		cout << lst.begin()->value << endl;
		cout << lst.rbegin()->value << endl;
	}

	delete pa; // オブジェクトの寿命管理には要注意
}

実行結果

003A54A8 == 003A54A8
0012FF54 == 0012FF54
100
300

etc

STLのコンテナ… list, set, map は、 リストやツリー構造を構成するために、格納するオブジェクトとは別に、 リストやツリーのノードオブジェクトを生成しています。 そうすることで、 格納されるオブジェクトの側ではコンテナを意識する必要がなくなり汎用性が高まっているのですが、 格納値とノードを別にすることで、「メモリ割り当ての回数が増える」「メモリの局所性が落ちる」 「例外安全性が若干落ちる」などの欠点も抱えています。

Boost.Intrusive は、list, set 等に格納するオブジェクトの側にノード処理を含めるタイプのコンテナです。 slist (単方向リスト)、list (双方向リスト)、 set (標準的な、赤黒木によるset)、 avl_set (標準的な、AVL木によるset)、 sg_set (メモリ効率の良いバランス木によるset)、 splay_set (頻繁にアクセスする要素ほど高速に検索できるset) が提供されています。setコンテナはそれぞれ、対応するtree構造としても直接利用可能です。