クラステンプレート: unordered_set
TR1にはハッシュ表を使った4種のコンテナが定義されています。
unordered_set: 要素の重複を許さない集合unordered_multiset: 要素の重複を許す集合unordered_map: 要素の重複を許さない辞書unordered_multimap: 要素の重複を許す辞書
これらを代表してunordered_setについて、その概要を説明します。
namespace std { namespace tr1 { // [6.3.4.3] Class template unordered_set template <class Value, class Hash = hash<Value>, class Pred = std::equal_to<Value>, class Alloc = std::allocator<Value> > class unordered_set; } }
unordered_setのテンプレート引数は4つ。
Value: コンテナ要素の型Hash:Valueからハッシュ値を求める関数オブジェクトPred: ふたつのValueが等しいときtrueとなる関数オブジェクトAlloc: アロケータ
Hashのデフォルト引数はhash<Value>で、Valueを引数としsize_tを返すoperator()を実装します。組み込み型と文字列については標準ヘッダ functionalに定義されています。これら以外の型を要素とするunorderedコンテナを利用するときは適切なハッシュ関数オブジェクトを与えなくてはなりません。
namespace std { namespace tr1 { template <class T> struct hash : public std::unary_function<T, std::size_t> { std::size_t operator()(T val) const; }; template <> struct hash<bool>; template <> struct hash<char>; template <> struct hash<signed char>; template <> struct hash<unsigned char>; template <> struct hash<wchar_t>; template <> struct hash<short>; template <> struct hash<unsigned short>; template <> struct hash<int>; template <> struct hash<unsigned int>; template <> struct hash<long>; template <> struct hash<unsigned long>; template <> struct hash<float>; template <> struct hash<double>; template <> struct hash<long double>; template<class T> struct hash<T*>; template <> struct hash<std::string>; template <> struct hash<std::wstring>; } }
コンテナに対する要素の挿入/削除/検索および列挙に関するインターフェイスは従来のsetと変わりません:
insert: 要素の挿入erase: 要素の削除clear: 全要素を削除しコンテナを空にするfind: 要素の検索count: 検索によって一致した要素数equal_range: 検索によって一致する要素位置の範囲
unorderedコンテナ独自のメンバ関数を以下に示します:
bucket_count
size_type bucket_count() const
コンテナ内のバケツの数を返します。
max_bucket_count
size_type max_bucket_count() const
コンテナ内に内包できるバケツの最大数を返します。
bucket
size_type bucket(k)
要素kが格納されるであろうバケツの番号を返します。
bucket_size
size_type bucket_size(n)
n番目のバケツに格納された要素数を返します。
begin
local_iterator begin(n)
const_local_iterator begin(n) const
n番目のバケツに格納された要素の先頭位置を返します。
end
local_iterator end(n)
const_local_iterator end(n) const
n番目のバケツに格納された要素の末尾位置を返します。
load_factor
float load_factor() const
バケツに格納されている要素数の平均値、すなわち要素数/バケツ数を返します。
max_load_factor
float max_load_factor() const
バケツに格納される要素数の平均値の上限を返します。要素の挿入によってこの上限値を超えたとき、新たなバケツが追加され各要素がバケツに再配分されます。
void max_load_factor(float z)
バケツに格納される要素数の平均値の上限をzに設定します。
rehash
void rehash(size_type n)
バケツ数が少なくともnになるようバケツ数が調整され、各要素が再配分されます。
setとの速度比較
最後に、ハッシュ表による unordered_set と二分木による set との速度を比較してみましょう。1～100000の乱数を二百万個挿入したときのそれぞれの所要時間を計測します。乱数の生成には同じくTR1に収録されたメルセンヌ・ツイスタを用いました。
// min/maxマクロの干渉防止 #define NOMINMAX #include <windows.h> #include <iostream> #include <set> #include <unordered_set> #include <unordered_map> #include <random> using namespace std; int main() { set<int> s; tr1::unordered_set<int> us; const int N = 100000; tr1::mt19937 rng; // メルセンヌ・ツイスタ tr1::uniform_int<> dice(1,N); // 整数一様分布 tr1::variate_generator <tr1::mt19937&, tr1::uniform_int<> > sample(rng, dice); long t; const int TIMES = 2000000; rng.seed(12345); t = GetTickCount(); for ( int i = 0; i < TIMES; ++i ) { s.insert(sample()); } t = GetTickCount() - t; cout << t << "(set)\n"; rng.seed(12345); //us.rehash(N); /* バケツ数の調整 */ t = GetTickCount(); for ( int i = 0; i < TIMES; ++i ) { us.insert(sample()); } t = GetTickCount() - t; cout << t << "(unordered_set)\n"; }
1562(set) 1188(unordered_set)
25%ほどunordered_setの方が速いようです。さほどに大きな速度差が出ませんでしたが、これはコンテナ内に要素が追加されるに従ってバケツ数の拡張と要素の再配分がしばしば行われるのに要する時間を含んでいます。コード中ほどの //us.rehash(N);のコメントを取り除き、最初から十分な数のバケツを確保した場合、実行結果は:
1563(set) 875(unordered_set)
となり、set の約2倍の速度が得られました。
まとめ
5回にわたって新しいC++: C++0xで提供される標準C++ライブラリの拡張:TR1の概要を解説しました。TR1が提供する機能はこれですべてではありません。上記サンプルでほんの少しお見せしている乱数やコンパイル時に型を判定するtype_traitsなども含まれます。
現在の標準C++ライブラリはコンテナ/アルゴリズム/イテレータおよび関数オブジェクトを中心としたものでした。TR1はこれらに加えて利用頻度が高いにもかかわらず今まで標準の存在しなかった機能群を強化し、標準ライブラリをほぼ二倍の量に拡張します。
JavaやC#,VB.NET等に比べて圧倒的に（？）複雑/難解であるがゆえに敬遠されがちなC++ですが、C++の活躍する分野は依然として在り続けます。
