unordered_map中使用pair<int,int>作为键的问题

Question

我的代码：

 typedef pair<int,int> Pair
  tr1::unordered_map<Pair,bool> h;
  h.insert(make_pair(Pair(0,0),true));

错误

 undefined reference to `std::tr1::hash<std::pair<int, int> >::operator()(std::pair<int, int>) const'

有什么需要我修复的吗？

谢谢

- icn

Answer 1

这是因为没有针对 Key = std::pair<int, int> 的 std::tr1::hash<Key> 专门化。在声明 tr1::unordered_map<Pair,bool> h; 前，您必须用 Key = std::pair<int, int> 对 std::tr1::hash<Key> 进行特殊化处理。这是因为 std 不知道如何哈希一个 pair<int, int>。

以下是如何特殊化 std::tr1::hash<> 的示例。

template <>
struct std::tr1::hash<std::pair<int, int> > {
public:
        size_t operator()(std::pair<int, int> x) const throw() {
             size_t h = SOMETHING;//something with x   
             return h;
        }
};

- Murilo Vasconcelos

---

很不幸，如果我将其专门用于我的库，而你将其专门用于你的库，并且我们的定义不相同，那么当我们的库链接在一起时，就会出现未定义的行为。std::tr1::hash有点不够明确，最好能够通过指定一个自定义的哈希类作为unordered_map的第三个模板参数来解决这个问题。 - Steve Jessop

@Murilo：如果不会带来痛苦，那就不是 C++。 - Steve Jessop

@Murilo：这并不是必须的。标准类型可以很容易地拥有标准但未指定的哈希值。这仅对非标准类型是必要的，即使这也是有争议的。 - GManNickG

当然可以：template <typename T, U> struct hash<pair<T,U> > { size_t operator() { return hash<T>()(first) ^ hash<U>()(second); }};。只要T和U的hashcodes是有效的，这将为pair<T,U>提供有效的哈希码。正如我所说，C++0x对于向量具有通用哈希函数，Java和Python也对集合具有通用哈希函数。因此，我不明白为什么TR1甚至C++0x都没有通用哈希对于pair，更不用说了。 - Steve Jessop

我正在Ubuntu上使用g++ 4.7.3进行编译。将代码粘贴到答案中时，会出现错误：在不同的命名空间中特化了模板<class_Tp> std::tr1::hash。因此，我将代码块包装在namespace std { namespace tr1 //// code block /// }}中。然后我遇到了另一个错误：显式特化非模板std::tr1<anonymous struct>。 - darKoram

Answer 2

无序映射不包含对于pair的哈希函数，如果我们想要哈希一个pair，则必须显式提供一个可以哈希pair的哈希函数。

如果我们想要将pair作为无序映射的键，有两种方法可以实现：

1. 定义std::hash的特化

typedef std::pair<std::string,std::string> pair;

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

int main()
{
    std::unordered_map<pair,int,pair_hash> unordered_map =
    {
        {{"C++", "C++11"}, 2011},
        {{"C++", "C++14"}, 2014},
        {{"C++", "C++17"}, 2017},
        {{"Java", "Java 7"}, 2011},
        {{"Java", "Java 8"}, 2014},
        {{"Java", "Java 9"}, 2017}
    };

    for (auto const &entry: unordered_map)
    {
        auto key_pair = entry.first;
        std::cout << "{" << key_pair.first << "," << key_pair.second << "}, "
                  << entry.second << '\n';
    }

    return 0;
}

2. 使用 Boost 库 另一个好方法是使用 Boost.functional 中的 boost::hash，它可以用于散列整数、浮点数、指针、字符串、数组、对和 STL 容器。

#include <iostream>
#include <boost/functional/hash.hpp>
#include <unordered_map>
#include <utility>

typedef std::pair<std::string,std::string> pair;

int main()
{
    std::unordered_map<pair,int,boost::hash<pair>> unordered_map =
    {
        {{"C++", "C++11"}, 2011},
        {{"C++", "C++14"}, 2014},
        {{"C++", "C++17"}, 2017},
        {{"Java", "Java 7"}, 2011},
        {{"Java", "Java 8"}, 2014},
        {{"Java", "Java 9"}, 2017}
    };

    for (auto const &entry: unordered_map)
    {
        auto key_pair = entry.first;
        std::cout << "{" << key_pair.first << "," << key_pair.second << "}, "
                  << entry.second << '\n';
    }

    return 0;
}

- fight_club

Answer 3

遇到了同样的问题：

unordered_map <pair<x, y>, z> m1;

一些解决方法包括：

unordered_map <stringxy, z> m1;
// the first and second of the pair merged to a string
//   though string parsing may be required, looks same complexity overall

unordered_multimap <x, pair<y, z>> m1;
// second of the pair of the key went into value.  
//   time complexity slightly increases

deque<deque<x>> d1;
// here x & y are of same type, z is stored as: d1[x][y] = z
//   space required is x * y, however time complexity is O(1)

- Manohar Reddy Poreddy

---

unordered_multimap <x, pair<y, z>> m1; 这个定义足以插入两个成对的值 (x,y)，其中 x 相同而 y 不同吗？如果值部分包含 y，那么哈希函数如何知道要使用它？ - Rez

我真的想帮忙，但我失去了上面细节的背景。上面给出的评论有帮助吗？ - Manohar Reddy Poreddy