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

我正在尝试创建一个 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: Implicit instantiation of undefined template 'std::__1::hash, std::__1::basic_string > >'

如果我使用像 map<pair<string, string>, int>这样的常规映射而不是 unordered_map，我就不会得到这个错误。

在无序映射中是否可以使用 pair作为键？

102105 次浏览
小开

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

根据我的编译器:

错误 C2338 C + + 标准没有为此提供散列表 C 类型: 程序文件(x86)微软视觉工作室 14.0 vc 包括 xstddef 381

您可以为 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;
}
小开
最佳答案

您需要为您的键类型提供一个合适的散列函数:

#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 还提供了函数集 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.

小开

我解决这个问题的首选方法是定义一个 key函数，它将您的对转换为一个唯一的整数(或任何散列数据类型)。此键不是哈希键。它是数据对的唯一 ID，然后由 unordered_map进行最佳散列。例如，您希望定义类型的 unordered_map

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

你想使用 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;}

然后将映射的类型更改为

  unordered_map<size_t,double> Map;

We can now use Map[key(i,j)]=value or Map.find(key(i,j)) to operate on the map. Every make_pair now becomes calling the inline key function.

这种方法保证密钥将被最佳散列，因为现在散列部分由系统完成，系统将始终选择内部散列表大小作为素数，以确保每个桶的可能性相同。但是你必须100% 确保 key对于每一对都是独一无二的，也就是说，没有两个不同的对可以有相同的密钥，或者可能有很难找到的错误。

小开

对于配对密钥，我们可以使用升级配对散列函数:

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

类似地，我们可以对矢量使用升压散列,

#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;
}
小开

在 有眼睛的 Baum对 回答的注释中，用户使用 乔 · 布莱克 要求举个例子代替定义散列函数。我同意 有眼睛的 Baum的 意见，这可能会损害可读性，特别是如果你想实现一个更通用的解决方案。因此，我希望通过关注由 OP 提供的 std::pair<std::string, std::string>的特定解决方案来保持我的示例的简短性。该示例还使用了 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);

守则

小开

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

#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
小开

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

我在 Google 中找到的所有解决方案都使用 XOR来生成 pair的哈希码，这是非常糟糕的。见 为什么 xor 是组合散列的默认方式。然而，这本书给了我们最好的解决方案，使用 hash_combine，这是从 Boost。这个解决方案比异或更好，当我测试它在线判断(编码员)。我将代码组织为一个模板，如下所示。你可以尽可能多地复制粘贴它。并且可以方便地将其更改为适合任何自定义结构/类。

更新: 为元组添加哈希模板。

#include <functional>


namespace hash_tuple {
template <typename TT> struct hash {
size_t operator()(TT const &tt) const { return std::hash<TT>()(tt); }
};


// 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(std::size_t &seed, T const &v) {
seed ^= hash_tuple::hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}


// Recursive template code derived from Matthieu M.
template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
struct HashValueImpl {
void operator()(size_t &seed, Tuple const &tuple) const {
HashValueImpl<Tuple, Index - 1>{}(seed, tuple);
hash_combine(seed, std::get<Index>(tuple));
}
};
template <class Tuple> struct HashValueImpl<Tuple, 0> {
void operator()(size_t &seed, Tuple const &tuple) const {
hash_combine(seed, std::get<0>(tuple));
}
};


template <typename... TT> struct hash<std::tuple<TT...>> {
size_t operator()(std::tuple<TT...> const &tt) const {
size_t seed = 0;
HashValueImpl<std::tuple<TT...>>{}(seed, tt);
return seed;
}
};
// 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);
}
};
} // namespace hash_tuple


#include <bits/stdc++.h>


int main() {
using ll = long long;
// std::unordered_map<std::pair<ll, ll>, ll, hash_tuple::pair_hash>
// hashmapPair; std::unordered_set<std::pair<ll, ll>, hash_tuple::pair_hash>
// hashsetPair;


std::unordered_map<std::pair<ll, ll>, ll, hash_tuple::pair_hash>
hashmapPair;
hashmapPair[{0, 0}] = 10;
std::unordered_set<std::pair<ll, ll>, hash_tuple::pair_hash> hashsetPair;
hashsetPair.insert({1, 1});


using TI = std::tuple<ll, ll, ll, ll>;
std::unordered_map<TI, ll, hash_tuple::hash<TI>> hashmapTuple;
hashmapTuple[{0, 1, 2, 3}] = 10;
std::unordered_set<TI, hash_tuple::hash<TI>> hashsetTuple;
hashsetTuple.emplace(0, 1, 2, 3);


return 0;
}
小开

这样的问题有一个 黑客

使用 string的 std:unordered_map

看下面的例子-

我被要求散列一个矩形的端点(角)

Error Approach

unordered_map<pair<int, int>, int> M;           //ERROR


pair<int, int> p;
M[p]++;

黑客

unordered_map<string, int> M;


pair<int, int> p;
string s = to_string(p.first) + "_" + to_string(p.second);
M[s]++;

如果需要创建一个十进制或双精度的散列作为密钥，这种方法甚至可以奏效:)

小开

我已经简化了@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;
}

它使用了与升级库中相同的逻辑(这比 xor 版本更好)。


提交答案