24

我正在尝试像这样定义一个 unordered_set：

unordered_set<Point> m_Points;

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

C++ 标准不提供这种类型的散列。

类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);
        }
};
  • 如何/在哪里为Point定义哈希函数？
  • 对于 2D 点，什么是好的散列函数？
4

1 回答 1

27

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

std命名空间中的基本类型和许多类型在std::hash<Key>. 这些函数遵循一定的规则：

  1. 接受一个类型的参数Key。

  2. 返回一个size_t表示参数哈希值的类型值。

  3. 调用时不抛出异常。

  4. 对于两个参数k1和k2相等，std::hash<Key>()(k1) == std::hash<Key>()(k2)。

  5. 对于不相等的两个不同参数k1，应该很小的概率，接近.k2std::hash<Key>()(k1) == std::hash<Key>()(k2)1.0/std::numeric_limits<size_t>::max()

现在我们已经完成了定义，让我们考虑一下什么是适合您的点结构的好的散列函数。有一个请求（std::pair与点结构非常相似）得到一个散列函数，但不幸的是，它没有进入 C++11 标准。

但我们很幸运：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())
            );
        }
    };
}

我们完成了。

于 2013-08-07T08:36:12.730 回答