ぬの部屋(仮)
nu-no-he-ya
  • 1234567
    891011121314
    15161718192021
    22232425262728
    2930     
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
       1234
    567891011
    12131415161718
    19202122232425
    26272829   
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
      12345
    6789101112
    13141516171819
    20212223242526
    27282930   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
        123
    45678910
    11121314151617
    18192021222324
    252627282930 
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
       1234
    567891011
    12131415161718
    19202122232425
    2627282930  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728     
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
     123456
    78910111213
    14151617181920
    21222324252627
    282930    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
       1234
    567891011
    12131415161718
    19202122232425
    2627282930  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
      12345
    6789101112
    13141516171819
    20212223242526
    27282930   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
        123
    45678910
    11121314151617
    18192021222324
    252627282930 
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
     123456
    78910111213
    14151617181920
    21222324252627
    28      
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    2930     
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
      12345
    6789101112
    13141516171819
    20212223242526
    27282930   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
     123456
    78910111213
    14151617181920
    21222324252627
    282930    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
       1234
    567891011
    12131415161718
    19202122232425
    2627282930  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
    1234567
    891011121314
    15161718192021
    22232425262728
           
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    30      
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
     123456
    78910111213
    14151617181920
    21222324252627
    282930    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    2930     
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
      12345
    6789101112
    13141516171819
    20212223242526
    27282930   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
         12
    3456789
    10111213141516
    17181920212223
    242526272829 
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
        123
    45678910
    11121314151617
    18192021222324
    252627282930 
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    30      
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    2930     
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
        123
    45678910
    11121314151617
    18192021222324
    25262728   
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
       1234
    567891011
    12131415161718
    19202122232425
    2627282930  
           
    1234567
    15161718192021
    293031    
           
         12
    3456789
    10111213141516
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
        123
    45678910
    11121314151617
    18192021222324
    252627282930 
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    30      
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
      12345
    6789101112
    13141516171819
    20212223242526
    27282930   
           
        123
    45678910
    11121314151617
    18192021222324
    252627282930 
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
       1234
    567891011
    12131415161718
    19202122232425
    2627282930  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728     
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
     123456
    78910111213
    14151617181920
    21222324252627
    282930    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
        123
    45678910
    11121314151617
    18192021222324
    252627282930 
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
     123456
    78910111213
    14151617181920
    21222324252627
    28293031   
           
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
     123456
    78910111213
    14151617181920
    21222324252627
    282930    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    31      
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    2930     
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
      12345
    6789101112
    13141516171819
    20212223242526
    27282930   
           
          1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031     
          1
    2345678
    9101112131415
    16171819202122
    232425262728 
           
       1234
    567891011
    12131415161718
    19202122232425
    262728293031 
           
    1234567
    891011121314
    15161718192021
    22232425262728
    293031    
           
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
           
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031  
           
    1234567
    891011121314
    15161718192021
    22232425262728
    2930     
           
        123
    45678910
    11121314151617
    18192021222324
    25262728293031
           
  • 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で作成します。