スポンサーリンク
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; }
unorderd_mapのキーとなる値が
std::hashはハッシュを生成するクラス(コード上はstruct)のテンプレートです。
これはintやfloat等の基本型や、std::stringやstd::shared_ptr型等の(標準)ライブラリ型に対して特殊化がされており、それらの型のハッシュ値を作成できます。
boost Reference l- 1.55.0 Header <boost/functional/hash.hpp>
これはboostにあった関数です。この関数は、与えられたハッシュ値と、与えられたデータから作成した別のハッシュ値の二つを統合し、一つのハッシュ値を作成します。boostではハッシュ生成にboost::hash_valueという関数が使われています。自前実装するときはstd::hashで作成します。