为什么我不能用一对作为键编译 unordered_map ? [英] Why can't I compile an unordered_map with a pair as key?

问题描述

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

I am trying to create an unordered_map to map pairs with integers:

#include <unordered_map>

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

我有一个类，我将 Unordered_map 声明为私有成员.

I have a class where I have declared an Unordered_map as a private member.

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

However, I am getting the following error when I try to compile it:

/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/type_traits:948:38: 未定义模板的隐式实例化 'std::__1::hash, std::__1::basic_string > >'

/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，我不会收到这个错误.

I am not getting this error if I use a regular map like map<pair<string, string>, int> instead of an unordered_map.

在无序映射中不能使用 pair 作为键吗?

Is it not possible to use pair as key in unordered maps?

推荐答案

您需要为您的密钥类型提供合适的散列函数.一个简单的例子:

You need to provide a suitable hash function for your key type. A simple example:

#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的解决方案.

This will work, but not have the best hash-properties^†. You might want to have a look at something like boost.hash_combine for higher quality results when combining the hashes. This is also discussed in greater detail – including the aforementioned solution from boost – in this answer.

对于现实世界的使用:Boost 还提供了函数集 hash_value 已经为 std::pair 以及 std::tuple 和大多数标准容器提供了一个哈希函数.

For real world use: Boost also provides the function set hash_value which already provides a hash function for std::pair, as well as std::tuple and most standard containers.

^†更准确地说，它会产生过多的碰撞.例如，每个对称对都将散列到 0，并且仅在排列上不同的对将具有相同的散列.这对于您的编程练习来说可能没问题，但可能会严重损害现实世界代码的性能.

^†More precisely, it will produce too many collisions. E.g., every symmetric pair will hash to 0 and pairs that differ only by permutation will have the same hash. This is probably fine for your programming exercise, but might seriously hurt performance of real world code.

这篇关于为什么我不能用一对作为键编译 unordered_map ?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！