如何在 C++ 中创建一组无序的整数对？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15160889/
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
How can I make an unordered set of pairs of integers in C++?
提问by Pippi
The following program does not compile an unordered set of pairs of integers, but it does for integers. Can unordered_setand its member functions be used on user-defined types, and how can I define it?
下面的程序不会编译一组无序的整数对，但可以编译整数。可以unordered_set及其成员函数用于用户定义的类型，我如何定义它？
#include <unordered_set>
...
class A{
...
private:
std::unordered_set< std::pair<int, int> > u_edge_;
};
Compiler error:
编译器错误：
error: no matching function for call to 'std::unordered_set >::unordered_set()'
错误：没有用于调用“std::unordered_set >::unordered_set()”的匹配函数
采纳答案by Mr.C64
Your code compiles on VS2010 SP1 (VC10), but it fails to compile with GCC g++ 4.7.2.
您的代码可在 VS2010 SP1 (VC10) 上编译，但无法使用 GCC g++ 4.7.2 进行编译。
However, you may want to consider boost::hashfrom Boost.Functionalto hash a std::pair(with this addition, your code compiles also with g++).
但是，您可能需要考虑boost::hash从Boost.Functional到散列 a 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_;
};
回答by dasblinkenlight
There is no standard way of computing a hash on a pair. Add this definition to your file:
没有计算一对散列的标准方法。将此定义添加到您的文件中：
struct pair_hash {
inline std::size_t operator()(const std::pair<int,int> & v) const {
return v.first*31+v.second;
}
};
Now you can use it like this:
现在你可以像这样使用它：
std::unordered_set< std::pair<int, int>, pair_hash> u_edge_;
This works, because pair<T1,T2>defines equality. For custom classes that do not provide a way to test equality you may need to provide a separate function to test if two instances are equal to each other.
这是有效的，因为pair<T1,T2>定义了平等。对于不提供测试相等性的方法的自定义类，您可能需要提供一个单独的函数来测试两个实例是否彼此相等。
Of course this solution is limited to a pair of two integers. Here is a link to an answerthat helps you define a more general way of making hash for multiple objects.
当然，这个解决方案仅限于一对两个整数。这是一个答案的链接，可帮助您定义为多个对象创建哈希的更通用方法。
回答by Mr.C64
The problem is that std::unordered_setis using std::hashtemplate to compute hashes for its entries and there is no std::hashspecialization for pairs. So you will have to do two things:
问题是std::unordered_set使用std::hash模板来计算其条目的哈希值，并且没有std::hash专门化对。所以你必须做两件事：
- Decide what hash function you want to use.
- Specialize
std::hashfor your key type (std::pair<int, int>) using that function.
- 确定要使用的哈希函数。
- 使用该函数专门
std::hash针对您的密钥类型 (std::pair<int, int>)。
Here is a simple example:
这是一个简单的例子：
#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;
}
回答by Andy Prowl
You need to provide a specialization for std::hash<>that works with std::pair<int, int>. Here is a very simple example of how you could define the specialization:
您需要为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_;
};
回答by honk
As already mentioned in most of the other answers on this question, you need to provide a hash function for std::pair<int, int>. However, since C++11, you can also use a lambda expressioninstead of defining a hash function. The following code takes the solution given by dasblinkenlightas basis:
正如在这个问题的大多数其他答案中已经提到的，您需要为std::pair<int, int>. 但是，从C++11 开始，您还可以使用lambda 表达式而不是定义散列函数。以下代码以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);
I'd like repeat dasblinkenlight's disclaimer: This solution is limited to a pair of two integers. This answerprovides the idea for a more general solution.
我想重复 dasblinkenlight 的免责声明：此解决方案仅限于一对两个整数。这个答案提供了一个更通用的解决方案的想法。
回答by Richard
The other answers here all suggest building a hash function that somehow combines your two integers.
这里的其他答案都建议构建一个哈希函数，以某种方式组合您的两个整数。
This will work, but produces non-unique hashes. Though this is fine for your use of unordered_set, for some applications it may be unacceptable. In your case, if you happen to choose a bad hash function, it may lead to many unnecessary collisions.
这会起作用，但会产生非唯一的哈希值。尽管这对您的使用来说很好unordered_set，但对于某些应用程序来说，这可能是不可接受的。在你的情况下，如果你碰巧选择了一个不好的哈希函数，它可能会导致许多不必要的冲突。
But you can produce unique hashes!
但是您可以生成唯一的哈希值！
intis usually 4 bytes. You could make this explicit by using int32_t.
int通常为 4 个字节。您可以使用int32_t.
The hash's datatype is std::size_t. On most machines, this is 8 bytes. You can check this upon compilation.
散列的数据类型是std::size_t. 在大多数机器上，这是 8 个字节。您可以在编译时检查这一点。
Since a pair consists of two int32_ttypes, you can put both numbers into an std::size_tto make a unique hash.
由于一对由两种int32_t类型组成，因此您可以将两个数字放入一个中std::size_t以形成唯一的散列。
That looks like this (I can't recall offhandedly how to force the compiler to treat a signed value as though it were unsigned for bit-manipulation, so I've written the following for uint32_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);
}
回答by juanchopanza
You are missing a hash function for std::pair<int, int>>. For example,
您缺少 .hash 函数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_;
You can also specialize std::hash<T>for std::hash<std::pair<int,int>>, in which case you can omit the second template parameter.
您还可以专门std::hash<T>用于std::hash<std::pair<int,int>>，在这种情况下，您可以省略第二个模板参数。
回答by SkyWalker
OK here is a simple solution with guaranteed non collisions. Simply reduce your problem to an existing solution i.e. convert your pair of intto stringlike so:
好的，这是一个简单的解决方案，可以保证不发生冲突。只需将您的问题简化为现有的解决方案，int即将您的问题转换成string这样：
auto stringify = [](const pair<int, int>& p, string sep = "-")-> string{
return to_string(p.first) + sep + to_string(p.second);
}
unordered_set<string> myset;
myset.insert(stringify(make_pair(1, 2)));
myset.insert(stringify(make_pair(3, 4)));
myset.insert(stringify(make_pair(5, 6)));
Enjoy!
享受！
