[解決済み] ペアをキーにしたunordered_mapがコンパイルできないのはなぜですか？

質問

私は unordered_map を作り、ペアを整数でマッピングしようとしています。

#include <unordered_map>

using namespace std;
using Vote = pair<string, string>;
using Unordered_map = unordered_map<Vote, int>;

あるクラスで Unordered_map をプライベートメンバとして宣言しています。

しかし、コンパイルしようとすると、以下のようなエラーが発生します。

/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/type_traits:948:38: Implicit instantiation of undefined template 'std::__1::hash, std::__1::basic_string > >'」 と表示されます。

のような通常のマップを使用すると、このエラーは発生しません。 map<pair<string, string>, int> の代わりに unordered_map .

を使用することはできないのでしょうか？ pair をキーにすることはできないのでしょうか？

どのように解決するのですか？

キータイプに適したハッシュ関数を用意する必要があります。簡単な例です。

#include <unordered_map>
#include <functional>
#include <string>
#include <utility>

// Only for pairs of std::hash-able types for simplicity.
// You can of course template this struct to allow other hash functions
struct pair_hash {
    template <class T1, class T2>
    std::size_t operator () (const std::pair<T1,T2> &p) const {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);

        // Mainly for demonstration purposes, i.e. works but is overly simple
        // In the real world, use sth. like boost.hash_combine
        return h1 ^ h2;  
    }
};

using Vote = std::pair<std::string, std::string>;
using Unordered_map = std::unordered_map<Vote, int, pair_hash>;

int main() {
    Unordered_map um;
}

これは動作しますが、最適なハッシュプロパティを持ちません。 ^† . あなたは以下のようなものを見てみたいかもしれません。 boost.hash_combine のようにすると、ハッシュを結合する際の品質が向上します。これについては、前述の boost による解決策も含め、より詳細に この回答 .

実戦で使うために Boostはまた、関数セット hash_value に対するハッシュ関数を提供します。 std::pair と同様に std::tuple およびほとんどの標準的なコンテナです。

^† より正確には、それはあまりにも多くの衝突を生成します。例えば、すべての対称的なペアは0にハッシュされ、並べ換えによってのみ異なるペアは同じハッシュを持つことになります。これはおそらくプログラミングの練習としては問題ないでしょうが、現実世界のコードのパフォーマンスを著しく低下させるかもしれません。