C++ 如何使用 unordered_set？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/18098178/
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 do I use unordered_set?
提问by brainydexter
I am trying to define an unordered_set like this:
我正在尝试像这样定义一个 unordered_set：
unordered_set<Point> m_Points;
When I compile it, I get the following error:
当我编译它时，我收到以下错误：
The C++ Standard doesn't provide a hash for this type.
C++ 标准不提供这种类型的哈希值。
Class Point:
班级Point：
class Point{
private:
int x, y;
public:
Point(int a_x, int a_y)
: x(a_x), y(a_y)
{}
~Point(){}
int getX()const { return x; }
int getY()const { return y; }
bool operator == (const Point& rhs) const{
return x == rhs.x && y == rhs.y;
}
bool operator != (const Point& rhs) const{
return !(*this == rhs);
}
};
- How/where do I define a hash function for Point?
- What would be a good hash function for a 2D point?
- 我如何/在哪里为Point定义哈希函数？
- 对于 2D 点，什么是好的散列函数？
回答by nijansen
std::unordered_setrequires you to write hash functionsto store and find your own types.
std::unordered_set要求您编写哈希函数来存储和查找您自己的类型。
Base types and many types in the stdnamespace do have such hash functions within std::hash<Key>. These functions follow certain rules:
std命名空间中的基本类型和许多类型在std::hash<Key>. 这些函数遵循一定的规则：
Accepts a single parameter of type
Key.Returns a value of type
size_tthat represents the hash value of the parameter.Does not throw exceptions when called.
For two parameters
k1andk2that are equal,std::hash<Key>()(k1) == std::hash<Key>()(k2).For two different parameters
k1andk2that are not equal, the probability thatstd::hash<Key>()(k1) == std::hash<Key>()(k2)should be very small, approaching1.0/std::numeric_limits<size_t>::max().
接受类型为 的单个参数
Key。返回一个
size_t表示参数哈希值的类型值。调用时不抛出异常。
对于两个参数
k1，并k2认为是相等的，std::hash<Key>()(k1) == std::hash<Key>()(k2)。对于两个不同的参数
k1和k2不相等的，但这种可能性std::hash<Key>()(k1) == std::hash<Key>()(k2)应该是非常小的，接近1.0/std::numeric_limits<size_t>::max()。
Now that we got the definitions out of the way, let's think about what would be a good hash function for your point structure. There was a requestthat std::pair(which is very similar to a point structure) got a hash function, but, unfortunately, that did not make it into the C++11 standard.
现在我们已经了解了定义，让我们考虑一下什么是适合您的点结构的好的散列函数。有一个请求，那std::pair（这是非常相似点结构）有一个哈希函数，但不幸的是，这并没有使入C ++ 11标准。
But we are lucky: SO is awesome and, of course, you can basically already find the answer. Note that you do not have to hash integers yourself, because std::hashhas a specialization for that already. So let's dig into our hash function, according to this answer:
但我们很幸运：SO 很棒，当然，您基本上已经可以找到答案了。请注意，您不必自己对整数进行散列，因为std::hash已经对此进行了专门化。所以让我们根据这个答案深入研究我们的哈希函数：
namespace std
{
template <>
struct hash<Point>
{
size_t operator()(Point const & x) const noexcept
{
return (
(51 + std::hash<int>()(x.getX())) * 51
+ std::hash<int>()(x.getY())
);
}
};
}
And we are done.
我们已经完成了。
