std::unordered_map のキーに独自の型を使用する #C++

C++11 で追加された std::unordered_map は、連想配列を扱うことができる。

以前からある std::map では、キーとして扱えることができるのは
順序関係が定義されたオブジェクトのみである。一方、 std::unordered_map では順序関係が定義されていキーを使うことができ、純粋な連想配列（ハッシュテーブル）として使うことができる。

ただし、 std::unordered_map のキーはハッシュ値へ変換できる必要がある。多くの標準型のように std::hash() でハッシュ値への変換が定義されている型はそのままキーに使うことができるが、自分で定義した型など変換が定義されていない型をキーとして使用する場合はハッシュ計算を行う関数を自分で用意する必要がある。

このハッシュ関数を定義するには、 std::hash() を特殊化する方法と、関数オブジェクトを作成して std::unordered_map のテンプレート引数として渡す方法がある。

今回はテンプレート引数に渡す方法を試してみた。

キーとして使用するオブジェクトの定義

以下のような構造体をキーとして使う場合を考える。

struct HashTableKey {
    int32_t x;
    int32_t y;

    bool operator==(const HashTableKey& rhs) const;
    bool operator!=(const HashTableKey& rhs) const;
};

inline bool HashTableKey::operator==(const HashTableKey& rhs) const {
    const HashTableKey& lhs = *this;
    return lhs.x == rhs.x && lhs.y == rhs.y;
}

inline bool HashTableKey::operator!=(const HashTableKey& rhs) const {
    return !(this->operator==(rhs));
}

キーが等しいかどうか判定する関係演算子を定義する必要がある。
これは自由関数として定義してもよい。

ハッシュ関数の定義

キーを受け取ってそのハッシュ値を返す関数オブジェクトを定義する。

struct Hash {
    typedef std::size_t result_type;

    std::size_t operator()(const HashTableKey& key) const;
};

inline std::size_t Hash::operator()(const HashTableKey& key) const {
    std::string bytes(reinterpret_cast<const char*>(&key), sizeof(HashTableKey));
    return std::hash<std::string>()(bytes);
}

ハッシュ関数は適当に定義した。自作のハッシュ関数を作成してもよい。
ただし、ハッシュ関数の善し悪しはパフォーマンスに影響するので気をつけること。
パフォーマンスを気にしないのであれば、極端な話、常に 0 を返す関数でも良い。

ハッシュテーブルの定義

std::unordered_map のテンプレート引数に適切な型を渡してハッシュテーブルを定義する。第1引数はキーの型、第2引数は値の型、第3引数にハッシュ関数を定義した関数オブジェクトを指定する。

typedef int32_t RecordValue;

typedef std::unordered_map<HashTableKey, RecordValue, HashTableKey::Hash> HashMap;

これで独自の型をキーにしたハッシュテーブルが定義できた。

サンプルコード

sample.cpp

//======================================
// Includes
//======================================
#include <cstdint>  // for int32_t

#include <iostream>
#include <unordered_map>  // for std::unordered_map

//======================================
// Keys
//======================================

/**
 * ハッシュテーブルのキーとして使用するオブジェクト
 */
struct HashTableKey {
    int32_t x;
    int32_t y;

    struct Hash;

    HashTableKey(int32_t x, int32_t y);
    bool operator==(const HashTableKey& rhs) const;
    bool operator!=(const HashTableKey& rhs) const;

private:
    friend std::ostream& operator<<(std::ostream& s, const HashTableKey& obj);
};

/**
 * コンストラクタ
 */
inline HashTableKey::HashTableKey(int32_t x, int32_t y) {
    this->x = x;
    this->y = y;
    return;
}

/**
 * 比較演算子
 */
inline bool HashTableKey::operator==(const HashTableKey& rhs) const {
    const HashTableKey& lhs = *this;
    return lhs.x == rhs.x && lhs.y == rhs.y;
}

/**
 * 比較演算子
 */
inline bool HashTableKey::operator!=(const HashTableKey& rhs) const {
    return !(this->operator==(rhs));
}

/**
 * 表示用
 */
/* friend */ inline std::ostream& operator<<(std::ostream& s,
                                             const HashTableKey& obj) {
    s << "(" << obj.x << "," << obj.y << ")";
    return s;
}

/**
 * ハッシュ関数
 */
struct HashTableKey::Hash {
    typedef std::size_t result_type;

    std::size_t operator()(const HashTableKey& key) const;
};

inline std::size_t HashTableKey::Hash::operator()(const HashTableKey& key) const {
    std::string bytes(reinterpret_cast<const char*>(&key), sizeof(HashTableKey));
    return std::hash<std::string>()(bytes);
}


//======================================
// Value
//======================================

/**
 * ハッシュテーブルの値として使用する型
 */
typedef int32_t HashTableValue;


//======================================
// Hash Table
//======================================

/**
 * ハッシュテーブルの型
 */
typedef std::unordered_map<HashTableKey, HashTableValue, HashTableKey::Hash> HashMap;


//======================================
// Sample Code
//======================================

/**
 * 表示用
 */
void DumpRecord(const HashMap& map, const HashTableKey& key) {
    std::cout << "The key " << key << " is ";
    if (map.count(key)) {
        int32_t value = map.at(key);
        std::cout << "contained: value = " << value;
    } else {
        std::cout << "not contained.";
    }
    std::cout << std::endl;
    return;
}

int main(int argc, char* argv[]) {

    HashTableKey key1(0, 1);
    HashTableKey key2(1, 1);

    HashMap map;

    DumpRecord(map, key1);
    map[key1] = 1;
    DumpRecord(map, key1);

    DumpRecord(map, key2);
    map[key2] = 2;
    DumpRecord(map, key2);
    map[key2] = 20;
    DumpRecord(map, key2);

    return 0;
}

実行結果。

$ g++ -std=c++0x -o sample sample.cpp
$ ./sample
The key (0,1) is not contained.
The key (0,1) is contained: value = 1
The key (1,1) is not contained.
The key (1,1) is contained: value = 2
The key (1,1) is contained: value = 20