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

概要

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

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

やり方

以下のコードは、mapのキーがpair<int,int>です。

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に置換するだけで動くようになります。

//////////////// 以下を貼る ////////////////
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もすると格段に速くなります。

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

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

//////////////// 以下を貼る ////////////////
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。

//////////////// 以下を貼る ////////////////
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が混在していたら全部マージした以下を貼りましょう。

//////////////// 以下を貼る ////////////////
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 という関数と同じアルゴリズムを使っています。

参考にした記事

pair他をキーにする方法いろいろ↓

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