pairをキーにしたstd::unordered_mapを手軽に使えるようにする

# 概要
C++17の話です（C++14以前でも動きそうですが未確認）。
キーが`pair`, `tuple`, `vector`などのときは、そのままでは`std::unordered_map`が使えません。手軽に使えるようにする方法をまとめました。
競技プログラミングなどで、`map`で書いたコードがTLE(時間切れ)した時に、素早く`unordered_map`に変更できて便利です。`unordered_set`, `unordered_multiset`, `unordered_multimap`にも使えます。

:::note warn
本記事で紹介している方法は、規格上は未定義動作である可能性が高いとのご指摘をコメントに頂きました。本記事の内容を、規格上問題のない形に修正して下さっていますので（@hmitoさんありがとうございます！）、コメントにあるラッパークラスをお使いください。
ラッパークラスを使う方法でも、
①貼る
②"map"を"unordered_map"に置換
だけで動くので、特に競プロではおすすめです。
:::

# やり方
以下のコードは、`map`のキーが`pair<int,int>`です。

``` c++
int main(){
    std::map<std::pair<int,int>,int> mp;
    mp[{1,2}]=5;
    mp[{3,4}]=33;
    std::cout << mp[{3,4}] << '\n'; //33
    return 0;
}
```

以下のコードの「以下を貼る」の部分をコピペすると、`map`を`unordered_map`に置換するだけで動くようになります。

``` c++
//////////////// 以下を貼る ////////////////
template<class T> size_t HashCombine(const size_t seed,const T &v){
    return seed^(std::hash<T>()(v)+0x9e3779b9+(seed<<6)+(seed>>2));
}
/* pair用 */
template<class T,class S> struct std::hash<std::pair<T,S>>{
    size_t operator()(const std::pair<T,S> &keyval) const noexcept {
        return HashCombine(std::hash<T>()(keyval.first), keyval.second);
    }
};
////////////////////////////////////////////

int main(){
    std::unordered_map<std::pair<int,int>,int> mp; //mapをunordered_mapに変えただけ
    mp[{1,2}]=5;
    mp[{3,4}]=33;
    std::cout << mp[{3,4}] << '\n'; //33
    return 0;
}
```

unordered_mapに変えるだけでは速くならないかもしれませんが、reserveもすると格段に速くなります。

``` c++
    mp.reserve(10000); //あらかじめキーの個数最大値より多く予約しておく
```


キーが`vector`なら以下を貼ればOK。

``` c++
//////////////// 以下を貼る ////////////////
template<class T> size_t HashCombine(const size_t seed,const T &v){
    return seed^(std::hash<T>()(v)+0x9e3779b9+(seed<<6)+(seed>>2));
}
/* vector用 */
template<class T> struct std::hash<std::vector<T>>{
    size_t operator()(const std::vector<T> &keyval) const noexcept {
        size_t s=0;
        for (auto&& v: keyval) s=HashCombine(s,v);
        return s;
    }
};
////////////////////////////////////////////
```

キーが`tuple`なら以下を貼ればOK。
``` c++
//////////////// 以下を貼る ////////////////
template<class T> size_t HashCombine(const size_t seed,const T &v){
    return seed^(std::hash<T>()(v)+0x9e3779b9+(seed<<6)+(seed>>2));
}
/* tuple用 */
template<int N> struct HashTupleCore{
    template<class Tuple> size_t operator()(const Tuple &keyval) const noexcept{
        size_t s=HashTupleCore<N-1>()(keyval);
        return HashCombine(s,std::get<N-1>(keyval));
    }
};
template <> struct HashTupleCore<0>{
    template<class Tuple> size_t operator()(const Tuple &keyval) const noexcept{ return 0; }
};
template<class... Args> struct std::hash<std::tuple<Args...>>{
    size_t operator()(const tuple<Args...> &keyval) const noexcept {
        return HashTupleCore<tuple_size<tuple<Args...>>::value>()(keyval);
    }
};
////////////////////////////////////////////
```

キーに`pair`、`tuple`、`vector`が混在していたら全部マージした以下を貼りましょう。

``` c++
//////////////// 以下を貼る ////////////////
template<class T> size_t HashCombine(const size_t seed,const T &v){
    return seed^(std::hash<T>()(v)+0x9e3779b9+(seed<<6)+(seed>>2));
}
/* pair用 */
template<class T,class S> struct std::hash<std::pair<T,S>>{
    size_t operator()(const std::pair<T,S> &keyval) const noexcept {
        return HashCombine(std::hash<T>()(keyval.first), keyval.second);
    }
};
/* vector用 */
template<class T> struct std::hash<std::vector<T>>{
    size_t operator()(const std::vector<T> &keyval) const noexcept {
        size_t s=0;
        for (auto&& v: keyval) s=HashCombine(s,v);
        return s;
    }
};
/* tuple用 */
template<int N> struct HashTupleCore{
    template<class Tuple> size_t operator()(const Tuple &keyval) const noexcept{
        size_t s=HashTupleCore<N-1>()(keyval);
        return HashCombine(s,std::get<N-1>(keyval));
    }
};
template <> struct HashTupleCore<0>{
    template<class Tuple> size_t operator()(const Tuple &keyval) const noexcept{ return 0; }
};
template<class... Args> struct std::hash<std::tuple<Args...>>{
    size_t operator()(const tuple<Args...> &keyval) const noexcept {
        return HashTupleCore<tuple_size<tuple<Args...>>::value>()(keyval);
    }
};
////////////////////////////////////////////

int main(){
    //↓こんな複雑なキーでもOK   キーがtuple<vector,pair,char>
    std::unordered_map<std::tuple<std::vector<int>,std::pair<int,int>,char>,int> mp;
    mp[{{1,2,3,4},{5,6},'a'}]=10;
    mp[{{11,22,3},{0,9},'b'}]=100;
    std::cout << mp[{{11,22,3},{0,9},'b'}] << '\n'; //100
    return 0;
}
```

# 解説
`std::hash`クラステンプレートを`pair`などに特殊化することで実現しています。キーに`pair`を使えるようにする方法はいくつかあるようですが、`std::hash`の特殊化で実現する記事が見つからず、やってみるととても手軽だったので記事にしてみました。

`pair`などには複数の値が含まれています。各々のハッシュ値を求め、それらを結合することで全体のハッシュ値を得ています。結合には、boostの[hash_combine](https://www.boost.org/doc/libs/1_55_0/doc/html/hash/reference.html#boost.hash_combine) という関数と同じアルゴリズムを使っています。

# 参考にした記事
pair他をキーにする方法いろいろ↓

https://qiita.com/izmktr/items/8e0fd1b6e37de59a9bd0

https://qiita.com/ganyariya/items/df35d253726269bda436

可変長tupleを扱う方法を参考にした↓

https://nsb248.hatenablog.com/entry/2016/05/02/190405