为什么我不能用一对作为键来编译 unordered_map？

Question

我正在尝试创建一个 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：未定义模板’std::__1::hash，std::__1的隐式实例化： :basic_string > >’

如果我使用像 map<pair<string, string>, int> 这样的常规地图而不是 unordered_map ，我不会收到此错误。

在无序地图中不能使用 pair 作为键吗？

原文由 Marre 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

您需要为您的密钥类型提供合适的哈希函数。一个简单的例子：

 #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，而仅通过排列不同的对将具有相同的散列。这对于您的编程练习可能很好，但可能会严重损害现实世界代码的性能。

原文由 Baum mit Augen 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

我已将@YoungForest 的 答案 简化为只使用对（= 不使用任意长度的元组），正如 OP 所要求的那样。我还最小化了样板代码：

 #include <functional>
#include <iostream>
#include <unordered_map>
#include <utility>       # pair

using namespace std;

// from boost (functional/hash):
// see http://www.boost.org/doc/libs/1_35_0/doc/html/hash/combine.html template
template <class T> inline void hash_combine(size_t &seed, T const &v) {
    seed ^= hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

struct pair_hash {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2> &p) const {
        size_t seed = 0;
        hash_combine(seed, p.first);
        hash_combine(seed, p.second);
        return seed;
    }
};

int main() {
    unordered_map<pair<int, int>, int, pair_hash> d;
    d[{1, 2}] = 3;
    cout << d.find({1, 2})->second << endl;

    return 0;
}

它使用与 boost 库中相同的逻辑（比 xor 版本更好）。

原文由 Antony Hatchkins 发布，翻译遵循 CC BY-SA 4.0 许可协议