unordered_map

備忘録
C++11で新しく標準化されたunordered_map(ハッシュマップ)の使い方を調べたのでまとめておきます．

———-
基本的な使い方はmapと同じで，[]演算子を使った要素へのアクセスができます．
ハッシュマップのバケットに関するメソッドがいくつか定義されていて以下のようなものなどがあります．
bucket_count() : バケット数
bucket_size(int n) : 引数で指定したバケットに入っている要素数
rehash(int n) : バケット数をnに変更

unordered_map<string, int> hashmap;

// 基本的な使い方はmap等と一緒
hashmap["taro"] = 16;
hashmap["jiro"] = 14;
cout << "taro : " << hashmap["taro"] << std::endl;  // "taro : 16"
cout << "jiro : " << hashmap["jiro"] << std::endl;    // "jiro : 14"

// 各バケットのサイズを調べる
cout << "--- buckets ---" << endl;
for( size_t i = 0; i < hashmap.bucket_count(); i++ ){
  cout << i << " : " << hashmap.bucket_size( i ) << endl;
}

// バケットを10個にリハッシュ，バケットの最小値は8
hashmap.rehash( 10 );
// コンストラクタでバケット数を12に指定
unordered_map<string, int> hashmap2( begin(hashmap), end(hashmap), 12 );

バケット数には最小値が決められているようで，自分の環境(VS2010)では最小数は8となっていました．
最小値未満のバケット数を指定しても無視されて，バケット数は最小値になりました．

自作クラスをキーにするには以下のことをする必要があります．

自作クラスに operator== を定義する
自作クラスのハッシュ関数を作成する

ハッシュ関数を作成するには以下の方法があります．

自作クラスを受け取り，size_tを返すファンクタを作る
std::hashクラスを自作クラスに特殊化する

// 自作クラス
class Name{
const string name;
public:
Name( string n ) : name( n ) {}

  bool operator == ( const Name& rhs ) const {
    return rhs.name == name;
  }
};


// 方法1 : 自作ファンクタ
class MyHash{
public:
  size_t operator() (const Name& val ) const {
    return 1;  // テスト用の悪いハッシュ関数
  }
};

// 方法2 : std::hashの特殊化
template<>
struct std::hash<Name> : public unary_function<Name, size_t> {
  size_t operator()(Name val) const {
    return 2; // テスト用の悪いハッシュ関数
  }
};


// 特殊化されたstd::hashが使用される
unordered_map<Name, int> hashmap;
// 自作のファンクタが使用される
unordered_map<Name, int, MyHash> hashmap2();

hashクラスにはデフォルトのハッシュ関数が定義されているのですが，そこではキー値をsize_t型にキャストしています．なので，size_t型にキャスト可能な新たにハッシュ関数を定義しなくてもunordered_mapのキーにすることができます．
また，hashクラスは最初から string, wstring に対して特殊化されていたので(VS2010)，これらはデフォルトで使用することができます．

———-
とりあえず，自作クラスをキーにする方法などを調べましたが，ハッシュ関数の作成は色々と気を使う必要があってしんどいので個人的にはstringをキーにすることしかなさそうです．

tetro

「unordered_map」タグアーカイブ

unordered_map