boost::unordered_*

abstract

必要なヘッダ

<boost/unordered_set.hpp> unordered_set, unordered_multiset,
<boost/unordered_map.hpp> unordered_map, unordered_multimap

出来ること

ハッシュを使った、O(1) で要素アクセスできる set と map

リファレンス

en

sample

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

#include <iostream>
#include <string>
#include <boost/unordered_set.hpp>
#include <boost/unordered_map.hpp>
using namespace std;

// 自分で作った型
struct MyData
{
	int    x, y;
	string data;

	bool operator==( const MyData& rhs ) const
	{
		return x==rhs.x && y==rhs.y && data==rhs.data;
	}
};

// 自分で作った型をunorderdコンテナに入れたいときは、operator== の他に
// 型と同じ名前空間で hash_value 関数を定義

size_t hash_value( const MyData& d )
{
	// 複数の値のハッシュ値を組み合わせてハッシュ値を計算するには、
	// boost::hash_combine を使います。
	size_t h = 0;
	boost::hash_combine(h, d.x);
	boost::hash_combine(h, d.y);
	boost::hash_combine(h, d.data);
	return h;
}

int main()
{
	boost::unordered_map<string, int> m;
	m["one"] = 1;
	m["two"] = 2;
	m["three"] = 3;
	cout << m["one"]+m["two"] << endl;

	boost::unordered_set<MyData> s;
	MyData d = {1,2,"onetwo"};
	s.insert(d);
	s.insert(d);
	cout << s.size() << endl;
}

実行結果

3
1

etc

順番に関して特に保証されないかわりに、std::set や std::map よりも高速な要素アクセスを実現する連想コンテナです。いわゆるハッシュで実装されています。 基本的に、std::set や std::map と同じように使うことができます。 C++標準ライブラリ拡張案 TR1 にも既にハッシュコンテナは含まれていて gcc4 や vc9 などでは実装済みですが、 それ以外の環境でも使えるポータブルなハッシュコンテナということになります。

自作のデータ型をこのコンテナに格納するには、operator == と、 そのデータ型の名前空間でハッシュ関数 hash_value 関数を定義します。