为什么我不能用一个对作为键编译一个unordered_map呢？

Question

我正在尝试创建一个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:未定义模板“std::__1::hash，std::__1::basic_string>”的隐式实例化；>‘

如果使用常规映射，如map int> 而不是unordered_map，则不会出现此错误。

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

Answer 1

对于配对密钥，我们可以使用boost配对哈希函数:

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

类似地，我们可以对向量使用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;
}

Answer 2

解决这个问题的首选方法是定义一个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;

我们现在可以使用map[key(i，j)]=value或map.find（key(i，j))对映射进行操作。每个make_pair现在都变成调用内联key函数。

这种方法保证密钥将被优化哈希，因为现在哈希部分由系统完成，系统将始终选择内部哈希表大小为素数，以确保每个桶的可能性相等。但是您必须100%地确保键对于每对都是唯一的，也就是说，没有两个不同的对具有相同的键，否则可能会有非常难找到的bug。

Answer 3

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

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

这可以工作，但没有最佳的哈希属性^user。您可能需要查看类似boost.hash_combined的内容，以便在组合散列时获得更高质量的结果。

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

^*更确切地说，它会产生太多的冲突。例如，每个对称对将散列为0，而仅因排列不同的对将具有相同的散列。这对于您的编程练习来说可能很好，但可能会严重影响实际代码的性能。