设置与无序集一起使用的自定义类 - 在集中找不到元素

Question

我想做的是使 std::unordered_set 与我的自定义类 Vector2 一起使用成为可能 -包括搜索已经在 set 中的此类的对象的可能性。

让我提供更多细节。我的 Vector2 类的标头（包括自定义哈希表）如下：

Class Vector2
{
private:
    static int lastID;
    const int id;
    int x;
    int y;

public:
    Vector2(int _x, int _y);
    ~Vector2();

    bool Vector2::operator==(const Vector2& other) const;

    int getId() const;
    int getX() const;
    int getY() const;
};

namespace std
{
    template<>
    struct hash<Vector2>
    {
        size_t
            operator()(const Vector2& obj) const
        {
            return hash<int>()(obj.getId());
        }
    };
}

此类的成员函数的实现很简单：

int Vector2::lastID = 0;

Vector2::Vector2(int _x, int _y) : id(lastID++)
{
    x = _x;
    y = _y;
}

int Vector2::getId() const
{
    return id;
}

int Vector2::getX() const
{
    return x;
}

int Vector2::getY() const
{
    return y;
}

bool Vector2::operator==(const Vector2& other) const
{
    if (x != other.x || y != other.y) return false;
    return true;
}

然后，我的主要功能如下所示：

std::unordered_set<Vector2> mySet;
mySet.insert(Vector2(1, 2));
mySet.insert(Vector2(3, 11));
mySet.insert(Vector2(-5, 0));

Vector2 whatToLookFor(1, 2);
if (mySet.find(whatToLookFor) != mySet.end())
{
    std::cout << "Found it!" << std::endl;
}
else
{
    std::cout << "Nothing found." << std::endl;
}

然而，虽然我期望输出是Found it!，但实际上是Nothing found。这意味着，虽然 Vector2 对象Vector2(1, 2)、Vector2(3, 11)和Vector2(-5, 0)被插入到 中mySet，但随后在此类集合中搜索时找不到它们。

我究竟做错了什么？

Answer 1

an 中的搜索操作unordered_set很大程度上依赖于元素的哈希值，要求给定哈希函数h： if A == B, then h(A) == h(B)。

当执行搜索时，哈希函数用于确定元素所属的桶。之后，如果桶中有多个元素，则会执行额外的检查以将这些元素相互比较。这可以通过直接比较元素、再次重新散列它们或使用其他技术来完成。

您的类有两个数据成员，显然您希望通过这些确切的成员“找到”一个元素（即您希望 if A.x == B.x && A.y == B.y，then A == B，反之亦然）。然而，您的散列函数仅根据id元素进行散列，忽略它们的其他成员，这就是它不能按您预期工作的原因。

解决方案是重写哈希函数以利用字段的值。您可能还想查看此文档页面。