C++でpairをキーとするunordered_mapを作成する方法

このチュートリアルでは、C++でpair（ペア）をキーとするunordered_mapを作成する方法について詳しく解説します。

unordered_mapは、デフォルトではpair型に対するハッシュ関数を提供していません。そのため、pairをキーとして使用したい場合は、カスタムハッシュ関数を明示的に指定する必要があります。

カスタムハッシュ関数の実装例

以下のコードでは、hash_pairという構造体を定義し、unordered_mapのテンプレート引数として渡しています。

#include <bits/stdc++.h>
using namespace std;
// 任意のpairに対するハッシュ値を計算する
struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const{
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        return hash1 ^ hash2;
    }
};
int main(){
    // ハッシュ関数を明示的に指定
    unordered_map<pair<int, int>, bool, hash_pair> um;
    // キーとして使用するpairを作成
    pair<int, int> p1(1000, 2000);
    pair<int, int> p2(2000, 3000);
    pair<int, int> p3(2005, 3005);
    um[p1] = true;
    um[p2] = false;
    um[p3] = true;
    cout << "Contents of the unordered_map : \n";
    for (auto p : um)
        cout << "[" << (p.first).first << ", " << (p.first).second << "] ==> " << p.second << "\n";
    return 0;
}

実行結果

Contents of the unordered_map :
[1000, 2000] ==> 1
[2005, 3005] ==> 1
[2000, 3000] ==> 0

コードの解説

1. カスタムハッシュ関数の定義

hash_pair構造体では、関数呼び出し演算子operator()をオーバーロードしています。内部では、pairのfirstとsecondそれぞれに対して標準のstd::hashを適用し、得られた2つのハッシュ値をXOR演算子（^）で組み合わせています。テンプレートを使用しているため、int以外の型の組み合わせにも対応できます。

2. unordered_mapの宣言方法

unordered_mapは3つのテンプレート引数を受け取ります。第1引数がキーの型（pair<int, int>）、第2引数が値の型（bool）、第3引数がハッシュ関数（hash_pair）です。この第3引数にカスタムハッシュを指定することで、pairをキーとして扱えるようになります。

注意点：ハッシュ衝突への対策

単純なXORによるハッシュ結合は、(a, b)と(b, a)が同一のハッシュ値になるなど、衝突が発生しやすいという弱点があります。実務で利用する場合は、以下のようにビットシフトと定数を組み合わせたboost::hash_combine風の手法を採用すると、より分散性の高いハッシュになります。

size_t seed = hash1 + 0x9e3779b9;
seed ^= hash2 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
return seed;

このようにカスタムハッシュ関数を用意することで、C++のunordered_mapでもpairを自由にキーとして扱うことが可能になります。