スポンサーリンク

| キーワード:

C++のunordered_mapで自作クラスを使う (主にハッシュ値生成について)

概要

C++11以降、ハッシュマップ(hash map)の機能が追加されました。

しかしhash mapの名前の既存ライブラリがたくさんあったので、衝突しないようにunordered_mapという名前にしました。

 

で、このunorderd_mapは基本型ならそのまま使えるんですが、自作型の場合にはクラスのインスタンスからハッシュ値を作る機能も作ってやる必要があります。

サンプルコード

#include <string>
#include <unordered_map>
#include <iostream>

////////////////////////////////////////////////////////////////
//ハッシュ値を統合する ( 汎用的に使用できる関数 )
// seed  in:既存のハッシュ値  out:元のseedとvから作成したハッシュ値を統合した値
// v     新たにハッシュ値を作成する値
template<typename T>
void hash_combine(size_t & seed, T const& v) {
  //基本型に関するハッシュ生成は標準ライブラリが提供している
  std::hash<T> primitive_type_hash;

  //生成したハッシュを合成する。このコードはboostものを使用する
  seed ^= primitive_type_hash(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

////////////////////////////////////////////////////////////////
// 自作データ
class MyData {
public:
  std::string m_v_str;
  int m_v_int;
  double m_v_double;
};
////////////////////////////////////////////////////////////////
// 自作データの比較演算子
bool operator==(const MyData& v1, const MyData& v2) {

  return
    v1.m_v_str == v2.m_v_str &&
    v1.m_v_int == v2.m_v_int &&
    v1.m_v_double == v2.m_v_double;//本当はdoubleを==比較してはいけません
}

////////////////////////////////////////////////////////////////
//自作データのハッシュを作成
namespace std {

  // 標準ライブラリは struct hash<>というデータをハッシュ化する関数オブジェクトのテンプレートを提供している
  // これは最初から基本型に対しては特殊化されているのでそのまま使える(上記hash_combine内で使用)
  // 自作クラスの場合は自分で特殊化し、operator()を定義してやる。

  template<>
  struct hash<MyData> {
  public:
    size_t operator()(const MyData& data)const {

      //クラスのメンバの値それぞれについてハッシュ生成して、それらを結合して一つのハッシュ値にする
      std::size_t seed = 0;
      hash_combine(seed, data.m_v_str);
      hash_combine(seed, data.m_v_int);
      hash_combine(seed, data.m_v_double);

      return seed;

    }
  };
}

////////////////////////////////////////////////////////////////
// エントリポイント
int main()
{
  std::unordered_map<MyData, int> map;

  map[ { "hello"   , 111 , 6.0e3 } ] = 0;
  map[ { "goodbye" , 111 , 6.0e3 } ] = 0;
  map[ { "hello"   , 222 , 6.0e3 } ] = 0;
  map[ { "goodbye" , 222 , 6.0e3 } ] = 0;
  map[ { "hello"   , 222 , 2.0e4 } ] = 0;
  map[ { "goodbye" , 222 , 3.0e4 } ] = 0;

  for (int i = 0; i < 3; i++) {
    map[{"hello"  , 111, 6.0e3 }]++;
    map[{"goodbye", 111, 6.0e3 }]++;
  }

  using namespace std;

  //結果出力
  for (auto& data : map) {
    cout 
      << "( " 
      << data.first.m_v_str << " , " 
      << data.first.m_v_int << " , " 
      << data.first.m_v_double << " ) = " 
      << data.second 
      << std::endl;
  }

  int i;
  cin >> i;

  return 0;
}

 

実行結果

( goodbye , 222 , 6000 ) = 0
( hello , 111 , 6000 ) = 3
( goodbye , 111 , 6000 ) = 3
( hello , 222 , 6000 ) = 0
( hello , 222 , 20000 ) = 0
( goodbye , 222 , 30000 ) = 0

 

要点

unorderd_mapのキーとなる値が

  • 基本型やstd::string型の時   …   何も考えずそのまま使える
  • 基本型でないとき … 基本型のハッシュ値をhash_combineで結合し一つのハッシュ値としてから使用する

 

std::hash

std::hash – cppreference.com

std::hashはハッシュを生成するクラス(コード上はstruct)のテンプレートです。

これはintやfloat等の基本型や、std::stringやstd::shared_ptr型等の(標準)ライブラリ型に対して特殊化がされており、それらの型のハッシュ値を作成できます。

 

hash_combine

boost Reference l- 1.55.0 Header <boost/functional/hash.hpp>

これはboostにあった関数です。この関数は、与えられたハッシュ値と、与えられたデータから作成した別のハッシュ値の二つを統合し、一つのハッシュ値を作成します。boostではハッシュ生成にboost::hash_valueという関数が使われています。自前実装するときはstd::hashで作成します。

 

 

 

コメントを残す

メールアドレスが公開されることはありません。

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)


この記事のトラックバックURL: