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

Why can't I compile an unordered_map with a pair as key?

提问by Mapplet

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

我正在尝试创建一个unordered_map映射对的整数：

#include <unordered_map>

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

I have a class where I have declared an Unordered_mapas a private member.

我有一个类，我已将 a 声明Unordered_map为私有成员。

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: Implicit instantiation of undefined template 'std::__1::hash, std::__1::basic_string > >'

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

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

如果我使用常规地图map<pair<string, string>, int>而不是unordered_map.

Is it not possible to use pairas key in unordered maps?

pair在无序映射中不能用作键吗？

回答by Baum mit Augen

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;
}

This will work, but not have the best hash-properties^?. You might want to have a look at something like boost.hash_combinefor higher quality results when combining the hashes.

这会起作用，但没有最好的哈希属性^？. boost.hash_combine在组合散列时，您可能想看看类似的东西以获得更高质量的结果。

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

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

---

---

^?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.

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

回答by Zhuoran He

My preferred way of solving this problem is to define a keyfunction that transforms your pair into a unique integer (or any hashable data type). This key is not the hash key. It is the unique ID of the pair of data that will then be optimally hashed by the unordered_map. For example, you wanted to define an unordered_mapof the type

我解决这个问题的首选方法是定义一个key函数，将您的对转换为唯一的整数（或任何可散列的数据类型）。这个键不是散列键。它是这对数据的唯一 ID，然后将由unordered_map. 例如，你想定义一个unordered_map类型

  unordered_map<pair<int,int>,double> Map;

And you want to use Map[make_pair(i,j)]=valueor Map.find(make_pair(i,j))to operate on the map. Then you'll have to tell the system how to hash a pair of integers make_pair(i,j). Instead of that, we can define

并且您要使用Map[make_pair(i,j)]=value或Map.find(make_pair(i,j))在地图上进行操作。然后你必须告诉系统如何散列一对整数make_pair(i,j)。取而代之的是，我们可以定义

  inline size_t key(int i,int j) {return (size_t) i << 32 | (unsigned int) j;}

and then change the type of the map to

然后将地图类型更改为

  unordered_map<size_t,double> Map;

We can now use Map[key(i,j)]=valueor Map.find(key(i,j))to operate on the map. Every make_pairnow becomes calling the inline keyfunction.

我们现在可以使用Map[key(i,j)]=value或Map.find(key(i,j))对地图进行操作。make_pair现在每时每刻都变成调用内联key函数。

This method guarantees that the key will be optimally hashed, because now the hashing part is done by the system, which will always choose the internal hash table size to be prime to make sure every bucket is equally likely. But you have to make yourself 100% sure that the keyis unique for every pair, i.e., no two distinct pairs can have the same key, or there can be very difficult bugs to find.

这种方法保证了密钥将被最优地散列，因为现在散列部分是由系统完成的，它总是会选择内部散列表大小为素数，以确保每个桶的可能性相等。但是您必须让自己 100% 确定key每一对都是唯一的，即，没有两个不同的对可以具有相同的密钥，否则可能很难找到错误。

回答by Felix Guo

For pair key, we can use boost pair hash function:

对于pair key，我们可以使用boost pair hash函数：

#include <iostream>
#include <boost/functional/hash.hpp>
#include <unordered_map>
using namespace std;

int main() {
  unordered_map<pair<string, string>, int, boost::hash<pair<string, string>>> m;

  m[make_pair("123", "456")] = 1;
  cout << m[make_pair("123", "456")] << endl;
  return 0;
}

Similarly we can use boost hash for vectors,

类似地，我们可以对向量使用 boost hash，

#include <iostream>
#include <boost/functional/hash.hpp>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
  unordered_map<vector<string>, int, boost::hash<vector<string>>> m;
  vector<string> a({"123", "456"});

  m[a] = 1;
  cout << m[a] << endl;
  return 0;
}

回答by Efreeto

If using pairis not a strict requirement, you can simply use map twice.

如果使用pair不是严格要求，您可以简单地使用 map 两次。

#include <unordered_map>

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

Unordered_map um;
um["Region1"]["Candidate1"] = 10;
cout << um["Region1"]["Candidate1"];    // 10

回答by bku_drytt

As your compilation error indicates, there is no valid instantiation of std::hash<std::pair<std::string, std::string>>in your std namespace.

正如您的编译错误所示，std::hash<std::pair<std::string, std::string>>您的 std 命名空间中没有有效的实例化。

According to my compiler:

根据我的编译器：

Error C2338 The C++ Standard doesn't provide a hash for this type. c:\program files (x86)\microsoft visual studio 14.0\vc\include\xstddef 381

错误 C2338 C++ 标准不提供此类型的散列。c:\程序文件 (x86)\Microsoft Visual Studio 14.0\vc\include\xstddef 381

You can provide your own specialization for std::hash<Vote>as follows:

您可以提供自己的专业std::hash<Vote>如下：

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

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

namespace std
{
    template<>
    struct hash<Vote>
    {
        size_t operator()(Vote const& v) const
        {
            // ... hash function here ...
        }
    };
}

int main()
{
    Unordered_map m;
}

回答by user106329

Reference: C++ Standard Library: A tutorial and reference, Second versionChapter 7.9.2: Creating and Controlling unordered Container

参考：C++ 标准库：教程和参考，第二版第 7.9.2 章：创建和控制无序容器

All solutions I found in Google use XORto generate hashcode of pair, which is totally bad. see why-is-xor-the-default-way-to-combine-hashes. However, the book has given us the best solution, using hash_combine, which is taken from Boost. The solution is much better than XOR when I tested it in Online Judge(Atcoder). I organized the code as a template as follow. You can copy and paste it as much as you can. And it is convenient to change it to fit any custom struct/class.

我在 Google 中找到的所有解决方案都XOR用于生成 的哈希码pair，这非常糟糕。看看为什么是异或默认方式到组合哈希。然而，这本书给了我们最好的解决方案，使用hash_combine，它取自Boost. 当我在 Online Judge ( Atcoder) 中对其进行测试时，该解决方案比 XOR好得多。我将代码组织为模板如下。您可以尽可能多地复制和粘贴它。更改它以适应任何自定义结构/类很方便。

#include <functional>
// from boost (functional/hash):
// see http://www.boost.org/doc/libs/1_35_0/doc/html/hash/combine.html template
template <typename T>
inline void hash_combine(std::size_t &seed, const T &val) {
    seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
// auxiliary generic functions to create a hash value using a seed
template <typename T> inline void hash_val(std::size_t &seed, const T &val) {
    hash_combine(seed, val);
}
template <typename T, typename... Types>
inline void hash_val(std::size_t &seed, const T &val, const Types &... args) {
    hash_combine(seed, val);
    hash_val(seed, args...);
}

template <typename... Types>
inline std::size_t hash_val(const Types &... args) {
    std::size_t seed = 0;
    hash_val(seed, args...);
    return seed;
}

struct pair_hash {
    template <class T1, class T2>
    std::size_t operator()(const std::pair<T1, T2> &p) const {
        return hash_val(p.first, p.second);
    }
};

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    unordered_map<pair<ll, ll>, ll, pair_hash> slopeCount;
    unordered_set<pair<ll, ll>, pair_hash> seen;
    return 0;
}

回答by Gaurav Pant

I know this is too naive implementation compared to other answers, but there is a workaround.

我知道与其他答案相比，这太天真了，但有一个解决方法。

If you are taking the input of pairs, just hash the pair with another integer in an unordered_hash while taking input and then use this integral value indirectly to hash the pair, i.e.

如果您正在输入对，只需在输入时用 unordered_hash 中的另一个整数散列该对，然后间接使用此整数值来散列该对，即

unordered_hash<int, Vote> h;
using Unordered_map = unordered_map<i, int>; // i is corresponding value to pair

回答by honk

In the comments on the answerby Baum mit Augen, the user Joe Blackasked for an exampleon using a lambda expressionsinstead of defining a hash function. I agree with the opinionof Baum mit Augen, that this might harm readability, especially if you want to implement a more universal solution. Therefore, I'd like to keep my example short by focusing on a specific solution for std::pair<std::string, std::string>, as presented by the OP. The example also uses a handcraftedcombination of std::hash<std::string>function calls:

在上的评论答案由鲍姆麻省理工学院的眼球，用户乔黑色要求的例子在使用lambda表达式而不是定义的哈希函数。我同意意见的鲍姆麻省理工学院的眼球，这可能伤害可读性，特别是如果你想实现一个更通用的解决方案。因此，我想通过专注于std::pair<std::string, std::string>OP 提供的特定解决方案来保持我的示例简短。该示例还使用了手工制作的std::hash<std::string>函数调用组合：

using Vote = std::pair<std::string, std::string>;
auto hash = [](const Vote& v){
    return std::hash<std::string>()(v.first) * 31 + std::hash<std::string>()(v.second);
};
using Unordered_map = std::unordered_map<Vote, int, decltype(hash)>;
Unordered_map um(8, hash);

Code on Ideone

Ideone 上的代码