为什么不能编译以一对为键的unordered_map?

问题描述

我正在尝试创建一个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:

如果我使用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之类的内容组合散列时可获得更高质量的结果.

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.

供现实世界使用: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?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！