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

Question

我正在尝试创建一个 unordered_map用整数映射对:

#include <unordered_map>

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

我有一个类(class)，我声明了 Unordered_map作为私有(private)成员(member)。

但是，当我尝试编译它时出现以下错误:

/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> 这样的常规 map ，我不会收到此错误。而不是 unordered_map .

难道不能用pair作为无序映射的键？

Answer 1

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

#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 这样的东西在组合哈希时获得更高质量的结果。这也在 this answer 中进行了更详细的讨论——包括上述来自 boost 的解决方案。 .

对于实际使用:Boost 还提供了函数集 hash_value它已经为 std::pair 以及 std::tuple 和大多数标准容器提供了哈希函数。

---

^†更准确地说，它会产生太多的碰撞。例如，每个对称对将散列为 0，仅通过排列不同的对将具有相同的散列。这可能适合您的编程练习，但可能会严重影响实际代码的性能。