为什么我可以用一对键编译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 ++/c ++/v1/type_traits：948：38：38：demit Intantiatiation' ：__ 1 :: basic_string＆gt; ＆gt;'

如果我使用常规地图，例如map＆lt; pair＆lt; string，string＆gt; gt;而不是unordered_map。

是否不可能将Pair用作无序地图中的键？

Answer 1

您需要为密钥类型提供合适的哈希功能。一个简单的例子：

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

这将起作用，但没有最好的Hash-Properties ^†。您可能想看一下 BOOST.HASH_COMBINE在结合哈希时为更高质量的结果。还可以更详细地讨论这一点 - 包括BOOST的上述解决方案 - 在此答案。

对于现实世界的使用：boost还提供功能集 <代码> hash_value 已经为std ::配对以及std :: Tuple和大多数标准容器提供了哈希功能。

---

^†更确切地说，它会产生太多的碰撞。例如，每个对称对将哈希至0，而仅因排列而不同的对将具有相同的哈希。这对于您的编程练习可能很好，但可能会严重损害现实世界法规的性能。

Answer 2

解决此问题的我首选的方法是定义键函数，该功能将您的配对转换为唯一的整数（或任何可用的数据类型）。该密钥不是哈希键。这是一对数据的唯一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，（i，） j））要在地图上操作。现在，每个make_pair现在都变为呼叫inline 键函数。

此方法可以确保将密钥最佳地放置，因为现在哈希零件是由系统完成的，它将始终选择内部哈希表尺寸以确保每个存储桶的可能性同样可能。但是，您必须使自己100％确定键是每对唯一的，即，没有两个不同的对可以具有相同的键，否则可能会有很难找到的错误。

Answer 3

如果使用Pair不是严格的要求，则只需两次使用地图即可。

#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

Answer 4

对于配对键，我们可以使用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;
}

同样，我们可以将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 5

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

我在Google中找到的所有解决方案XOR XOR 生成对，这完全不好。请参阅 why-is-is-xor-the-default-to-to -combine-hashes 。但是，这本书为我们提供了最佳的解决方案，使用hash_combine，它取自boost。当我在在线法官中对其进行测试时，该解决方案要比XOR好得多（ noreflow noreferrer“> atcoder ）。我将代码作为模板组织为以下模板。您可以尽可能复制和粘贴它。更改它以适合任何自定义结构/类是很方便的。

更新：添加元组的哈希模板。

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

Answer 6

正如您的汇编错误所示，在您的std nesspace中没有有效的std :: std :: hash＆lt; std :: pair＆lt; std :: string，std :: string＆gt;＆gt;。

根据我的编译器的说法：

错误C2338 C ++标准无法为此提供哈希
类型。 C：\ Program Files（X86）\ Microsoft Visual Studio
14.0 \ vc \ include \ xstddef 381

您可以为std :: Hash＆lt; pote＆gt;提供自己的专业化，如下：

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

Answer 7

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

它使用与Boost库中相同的逻辑（比XOR版本更好）。

Answer 8

在 要求使用一个示例 lambda表达式而不是定义哈希功能。我同意 MIT Augen ，这可能会损害可读性，尤其是如果您想实现更普遍的解决方案。因此，我想通过专注于std :: pair＆lt; std :: String，std :: String＆gt;的特定解决方案来简短示例。该示例还使用a 手工制作 std :: Hash＆lt; std :: String＆gt;函数调用的组合：

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

Answer 9

此类问题有一个 hack

使用std：unordered_map string> string

查看以下示例 -

我需要哈希矩形

错误方法

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

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

hack

unordered_map<string, int> M;

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

甚至有效，即使您需要创建十进制或双重键的哈希:)