如何使用unordered_set？ [英] How do I use unordered_set?

问题描述

我想这样定义一个unordered_set：

I am trying to define an unordered_set like this:

unordered_set<Point> m_Points;

当我编译它，我得到以下错误：

When I compile it, I get the following error:

C ++标准不为此类型提供散列。

The C++ Standard doesn't provide a hash for this type.

code> Point ：

Class 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);
        }
};

• 如何/在何处为点定义散列函数？


• 对于2D点，什么是好的哈希函数？



推荐答案

std :: unordered_set 需要您写散列函数来存储和查找自己的类型。

std::unordered_set requires you to write hash functions to store and find your own types.

基本类型和许多类型在 std 命名空间在 std :: hash< Key> 中有这样的散列函数。这些函数遵循某些规则：

Base types and many types in the std namespace do have such hash functions within std::hash<Key>. These functions follow certain rules:




1. 接受键的单个参数。

在调用时不会抛出异常

对于两个参数 k1 和 k2 等于 std :: hash< Key>（）（k1）== std :: hash< Key>（）（k2）。

对于两个不同的参数 k1 和 k2 ，则 std :: hash< Key>（）（k1）== std :: hash< Key>（）（k2）的概率应该非常小， code> 1.0 / std :: numeric_limits< size_t> :: max（）。

For two different parameters k1 and k2 that are not equal, the probability that std::hash<Key>()(k1) == std::hash<Key>()(k2) should be very small, approaching 1.0/std::numeric_limits<size_t>::max().


$ b b

现在我们得到了定义，让我们考虑一下什么是你的点结构的好的哈希函数。有请求 std :: pair （非常类似于点结构）有一个散列函数，但不幸的是，没有使它成为C ++ 11标准。

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 request that 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.

但我们很幸运：SO是真棒，当然，你基本上可以找到答案。注意，你不必自己散列整数，因为 std :: hash 已经有一个专门化。因此，让我们深入一下哈希函数，根据此答案：

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::hash has a specialization for that already. So let's dig into our hash function, according to this answer:

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())
            );
        }
    };
}

我们完成了。

这篇关于如何使用unordered_set？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！