boost::bimaps

abstract

必要なヘッダ

<boost/bimap/bimap.hpp> (基本),
<boost/bimap/set_of.hpp> (set view),
<boost/bimap/multiset_of.hpp> (multiset view),
<boost/bimap/unordered_set_of.hpp> (unordered_set view),
<boost/bimap/unordered_multiset_of.hpp> (unordered_multiset view),
<boost/bimap/list_of.hpp> (list view),
<boost/bimap/vector_of.hpp> (vector view),
<boost/bimap/unconstrained_set_of.hpp> (viewなし)

出来ること

双方向map

リファレンス

en

sample

サンプルの動作確認バージョン [GCC4.4/1.40.0] [VC9/1.40.0]

#include <iostream>
#include <string>
#include <boost/bimap/bimap.hpp>
#include <boost/bimap/multiset_of.hpp>
#include <boost/range.hpp> // boost::distance @ Boost.Range
using namespace std;
using namespace boost::bimaps;

int main()
{
	{
		typedef bimap<int,string>::value_type value_t;

		// int <==> string の１対１マップ
		bimap<int, string> b;
		b.insert( value_t(1, "one") );
		b.insert( value_t(2, "two") );
		b.insert( value_t(3, "three") );

		cout << b.left.at(1)          << endl; // 1 ==> ?
		cout << b.right.at("three")   << endl; // ? <== three
	}

	cout << "--------" << endl;

	{
		// Boost.Graph の例のグラフを多対多のマップで表現
		// with_info で、付加情報を加えることができます
		typedef bimap< multiset_of<int>, multiset_of<int>, with_info<int> > Graph;
		typedef Graph::value_type Edge;
		Graph g;
		g.insert( Edge(0, 1, 1) );
		g.insert( Edge(0, 2, 1) );
		g.insert( Edge(1, 2, 1) );
		g.insert( Edge(1, 4, 1) );
		g.insert( Edge(2, 0, 1) );
		g.insert( Edge(2, 3, 1) );
		g.insert( Edge(3, 4, 1) );

		cout << distance( g.left.equal_range(4) )  << "本" << endl; // [4]から出る辺の数
		cout << distance( g.right.equal_range(4) ) << "本" << endl; // [4]に入る辺の数
	}
}

実行結果

one
3
--------
0本
2本

etc

Boost.MultiIndex を、 ペアのどちら側を key としても使える双方向 map に特化したコンテナです。

機能的には bimap<A,B> は、 map<A,B> と map<B,A> を同時に維持しておいて、.left で A→B のmap、 .right で B→A の map を随時取り出せるコンテナ、ということになります。 Boost.MultiIndex の用途の中でも特に頻出のパターンなので、 インターフェイスを特にこのパターンに特化して整備したものってところですね。

デフォルトは双方向のmapですが、 multiset_of を使うことで multimap、unordered_set_of で unordered_map、 list_of でイテレート時に挿入順を保つ、などなど、色々カスタマイズが効きます。 個人的にはサンプルにあげたような、multiset×multiset×with_info で、逆辺参照も簡単にできるグラフ構造を表現できるのが便利でした。