C++ pair<int,int> 对作为 unordered_map 问题的键
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4870437/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
pair<int,int> pair as key of unordered_map issue
提问by icn
My code:
我的代码：
typedef pair<int,int> Pair
tr1::unordered_map<Pair,bool> h;
h.insert(make_pair(Pair(0,0),true));
Erorr
错误
undefined reference to `std::tr1::hash<std::pair<int, int> >::operator()(std::pair<int, int>) const'
Something I need to fix?
我需要修复什么？
thanks
谢谢
回答by Murilo Vasconcelos
This happens because there is no specialization for std::tr1::hash<Key>with Key = std::pair<int, int>.
You must to specialize std::tr1::hash<Key>with Key = std::pair<int, int>before declaring tr1::unordered_map<Pair,bool> h;.
This happens because stddon't know how to hash a pair<int, int>.
发生这种情况是因为没有专门化std::tr1::hash<Key>with Key = std::pair<int, int>。你必须专注std::tr1::hash<Key>与Key = std::pair<int, int>申报前tr1::unordered_map<Pair,bool> h;。发生这种情况是因为std不知道如何散列 a pair<int, int>。
Following there is a example of how to specialize std::tr1::hash<>
下面是一个如何专业化的例子 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;
}
};
回答by fight_club
Unordered Map does not contain a hash function for a pair, So if we want to hash a pair then we have to explicitly provide it with a hash function that can hash a pair.
Unordered Map 不包含一个对的哈希函数，所以如果我们想对一个对进行哈希，那么我们必须明确地为它提供一个可以对一对进行哈希的哈希函数。
If we want to use pair as a key to unordered_map, there are 2 ways to do it :
如果我们想使用pair作为unordered_map的键，有两种方法：
- Define specializaion for std::hash
- 为 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;
}
- Using Boost Library Another good way is to use boost::hash from Boost.functional which can be used to hash integers,floats,pointers,strings,arrays,pairs and theh STL containers.
- 使用 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;
}
回答by Manohar Reddy Poreddy
Ran into the same issue:
遇到同样的问题：
unordered_map <pair<x, y>, z> m1;
A few workarounds are:
一些解决方法是：
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)
