multi_index_containerのキーに任意のクラスを使用する(1)

setやunorderd_setでやってきたことのmulti_index_containor編です。

multi_index_containorそのものの解説は、ぐぐったりして調べてください。
慣れるとめちゃくちゃ便利なコンテナです。

setに当たるものがorderd_unique、unorderd_setにあたるものがhashed_uniqueになります。
ちなみに、multi_setがorderd_non_unique、unorderd_multisetがhashed_non_uniqueです。

multi_index_containorの場合は、色々便利な関数が揃っているので、
比較関数やハッシュ関数を登録せずに使う方法もあります。

クラスに必要な関数をもたせる

まずは、クラスそのものに必要な関数を定義してしまう方法です。
前回まではPoint型を例に、yの値のみをキーにしていましたが、今回はxとyの両方をキーにしています。

orderd_uniqueならoperator<を定義します。
hashed_uniqueならoperator==とhash_valueを定義します。
それぞれ、std::mapとboost::unorderd_mapと同じ方法です。

# include <boost/multi_index_container.hpp>
# include <boost/multi_index/identity.hpp>
# include <boost/multi_index/ordered_index.hpp>
# include <boost/multi_index/hashed_index.hpp>

using namespace boost::multi_index;

struct Point{
	int x, y;

	Point() :x(0), y(0){}
	Point(int x, int y) :x(x), y(y){}

	bool operator<(const Point &r) const { return this->x == r.x ? this->y < r.y : this->x < r.x; }
	bool operator==(const Point &r) const { return this->x == r.x && this->y == r.y; }
	friend size_t hash_value(const Point &p){ return (p.x << 16) ^ (p.x >> 16) ^ p.y; }
};

typedef boost::multi_index_container <
	Point,
	indexed_by<
	ordered_unique< identity<Point> >,
	hashed_unique< identity<Point> >
	>
> PointIndex;

int main(){
	PointIndex p;

	p.insert(Point(10, 20));
	p.insert(Point(20, 30));
	p.insert(Point(0, 10));

	return 0;
}

composite_keyで複数のキーを指定する

Point型はxとyの値を持ったクラスなので、この両方をcomposite_keyとして一つにまとめたキーとして扱うことでもできます。
この時、複数のint型という扱いなので、特に自分で関数を用意する必要はありません。

# include <boost/multi_index_container.hpp>
# include <boost/multi_index/ordered_index.hpp>
# include <boost/multi_index/hashed_index.hpp>
# include <boost/multi_index/member.hpp>
# include <boost/multi_index/composite_key.hpp>

using namespace boost::multi_index;

struct Point{
	int x, y;

	Point() :x(0), y(0){}
	Point(int x, int y) :x(x), y(y){}
};

typedef composite_key < 
	Point, 
	BOOST_MULTI_INDEX_MEMBER(Point, int, x),
	BOOST_MULTI_INDEX_MEMBER(Point, int, y)
> composite_key_point;

typedef boost::multi_index_container <
	Point,
	indexed_by<
	hashed_unique<composite_key_point>,
	ordered_unique<composite_key_point>
	>
> PointIndex;

int main(){
	PointIndex p;

	p.insert(Point(10, 20));
	p.insert(Point(20, 30));
	p.insert(Point(0, 10));

	return 0;
}

関数を使って一つにまとめる

Point型にあるxとyはint型なので、intを32bitと考えるとPointは64bitのデータを持ちます。
long long(64bit)の値を返す関数を定義して、それで管理するという方法をやってみます。

hashed_uniqueの方は侵入型(メンバ関数を呼び出す形)、orderd_uniqueの方は非侵入型(グローバル関数を呼び出す形)で定義しています。

# include <boost/multi_index_container.hpp>
# include <boost/multi_index/ordered_index.hpp>
# include <boost/multi_index/hashed_index.hpp>
# include <boost/multi_index/mem_fun.hpp>
# include <boost/multi_index/global_fun.hpp>
using namespace boost::multi_index;

struct Point{
	int x, y;

	Point() :x(0), y(0){}
	Point(int x, int y) :x(x), y(y){}

	long long int64value() const{
		return (static_cast<long long>(x) << 32) | y;
	}
};

long long point_int64value(const Point &p){ return p.int64value(); }

typedef boost::multi_index_container <
	Point,
	indexed_by<
		hashed_unique<BOOST_MULTI_INDEX_CONST_MEM_FUN(Point, long long, int64value)>,
		ordered_unique< global_fun<const Point &, long long, &point_int64value> >
	>
> PointIndex;

int main(){
	PointIndex p;

	p.insert(Point(10, 20));
	p.insert(Point(20, 30));
	p.insert(Point(0, 10));

	return 0;
}

BOOST_MULTI_INDEX_MEMBERを使う場合、自分自身が直接所有しているメンバ変数しか指定できません。
PointData型の中にPoint型があり、Point型のxとyを指定したいという場合は、
BOOST_MULTI_INDEX_MEMBERではうまくできないので、ラッパ関数を作って対応します。

(BOOST_MULTI_INDEX_MEMBERを入れ子にする方法があるなら教えて欲しいです。)

# include <boost/multi_index_container.hpp>
# include <boost/multi_index/ordered_index.hpp>
# include <boost/multi_index/hashed_index.hpp>
# include <boost/multi_index/mem_fun.hpp>
# include <boost/multi_index/global_fun.hpp>
# include <boost/multi_index/composite_key.hpp>

using namespace boost::multi_index;

struct Point{
	int x, y;

	Point() :x(0), y(0){}
	Point(int x, int y) :x(x), y(y){}
};

struct PointData{
	Point pos;
	int value;

	PointData(const Point &pos, int value):pos(pos), value(value){}
	PointData():pos(), value(0){}
};

int PointDataPointX(const PointData &pd){return pd.pos.x;}
int PointDataPointY(const PointData &pd){return pd.pos.y;}

typedef composite_key < 
	PointData, 
	global_fun<const PointData &, int, &PointDataPointX>,
	global_fun<const PointData &, int, &PointDataPointY>
> composite_key_point;

typedef boost::multi_index_container <
	PointData,
	indexed_by<
		hashed_unique<composite_key_point>,
		ordered_unique<composite_key_point>
	>
> PointDataIndex;

int main(){
	PointDataIndex p;

	p.insert(PointData(Point(10, 20), 30));
	p.insert(PointData(Point(20, 30), 50));
	p.insert(PointData(Point(0, 10), 10));

	return 0;
}

長くなったので、比較関数を指定する方法に関しては次回に書きます。