以下程序不会编译一组无序的整数对,但它会对整数进行编译。 unordered_set
及其成员函数可以用于用户定义的类型,我该如何定义它?
#include <unordered_set>
...
class A{
...
private:
std::unordered_set< std::pair<int, int> > u_edge_;
};
编译错误:
错误:没有匹配函数来调用'std :: unordered_set> :: unordered_set()'
您的代码在VS2010 SP1(VC10)上编译,但无法使用GCC g ++ 4.7.2进行编译。
但是,您可能需要考虑boost::hash
中的Boost.Functional来散列std::pair
(使用此添加,您的代码也会使用g ++编译)。
#include <unordered_set>
#include <boost/functional/hash.hpp>
class A
{
private:
std::unordered_set<
std::pair<int, int>,
boost::hash< std::pair<int, int> >
> u_edge_;
};
没有标准方法来计算对上的散列。将此定义添加到您的文件中:
struct pair_hash {
inline std::size_t operator()(const std::pair<int,int> & v) const {
return v.first*31+v.second;
}
};
现在您可以像这样使用它:
std::unordered_set< std::pair<int, int>, pair_hash> u_edge_;
这是有效的,因为pair<T1,T2>
定义了相等性。对于不提供测试相等性的方法的自定义类,您可能需要提供单独的函数来测试两个实例是否彼此相等。
当然,这种解决方案仅限于一对两个整数。这是a link to an answer,它可以帮助您定义为多个对象制作哈希的更通用方法。
问题是std::unordered_set
正在使用std::hash
模板来计算其条目的哈希值,并且没有std::hash
对的特化。所以你必须做两件事:
std::hash
)使用std::pair<int, int>
。这是一个简单的例子:
#include <unordered_set>
namespace std {
template <> struct hash<std::pair<int, int>> {
inline size_t operator()(const std::pair<int, int> &v) const {
std::hash<int> int_hasher;
return int_hasher(v.first) ^ int_hasher(v.second);
}
};
}
int main()
{
std::unordered_set< std::pair<int, int> > edge;
}
你需要为与std::hash<>
合作的std::pair<int, int>
提供专业化。以下是如何定义专业化的一个非常简单的示例:
#include <utility>
#include <unordered_set>
namespace std
{
template<>
struct hash<std::pair<int, int>>
{
size_t operator () (std::pair<int, int> const& p)
{
// A bad example of computing the hash,
// rather replace with something more clever
return (std::hash<int>()(p.first) + std::hash<int>()(p.second));
}
};
}
class A
{
private:
// This won't give you problems anymore
std::unordered_set< std::pair<int, int> > u_edge_;
};
你缺少std::pair<int, int>>
的哈希函数。例如,
struct bad_hash
{
std::size_t operator()(const std::pair<int,int>& p) const
{
return 42;
}
};
....
std::unordered_set< std::pair<int, int>, bad_hash> u_edge_;
你也可以为std::hash<T>
专门化std::hash<std::pair<int,int>>
,在这种情况下你可以省略第二个模板参数。
这里的其他答案都建议构建一个以某种方式组合你的两个整数的哈希函数。
这将起作用,但会产生非唯一的哈希值。虽然这对你使用unordered_set
很好,但对于某些应用来说这可能是不可接受的。在您的情况下,如果您碰巧选择了错误的哈希函数,则可能会导致许多不必要的冲突。
但是你可以产生独特的哈希!
int
通常是4个字节。你可以使用int32_t
来明确这一点。
哈希的数据类型是std::size_t
。在大多数机器上,这是8个字节。你可以在编译时检查这个。
由于一对由两个int32_t
类型组成,您可以将两个数字放入std::size_t
以制作唯一的哈希值。
这看起来像这样(我不记得如何强迫编译器处理一个有符号的值,好像它是无符号的位操作,所以我为uint32_t
编写了以下内容。):
#include <cassert>
#include <cstdint>
#include <unordered_set>
#include <utility>
struct IntPairHash {
std::size_t operator()(const std::pair<uint32_t, uint32_t> &p) const {
assert(sizeof(std::size_t)>=8); //Ensure that std::size_t, the type of the hash, is large enough
//Shift first integer over to make room for the second integer. The two are
//then packed side by side.
return (((uint64_t)p.first)<<32) | ((uint64_t)p.second);
}
};
int main(){
std::unordered_set< std::pair<uint32_t, uint32_t>, IntPairHash> uset;
uset.emplace(10,20);
uset.emplace(20,30);
uset.emplace(10,20);
assert(uset.size()==2);
}
正如在这个问题的大多数其他答案中已经提到的,你需要为std::pair<int, int>
提供一个哈希函数。但是,从C++11开始,您也可以使用lambda expression而不是定义哈希函数。以下代码以solution given by dasblinkenlight为基础:
auto hash = [](const std::pair<int, int>& p){ return p.first * 31 + p.second; };
std::unordered_set<std::pair<int, int>, decltype(hash)> u_edge_(8, hash);
我想重复一下dasblinkenlight的免责声明:这个解决方案仅限于一对两个整数。 This answer提供了一个更通用的解决方案的想法。