CODEWITHSUNDEEP
c++classhashfindunordered-set
Andy
Andy

Reputation: 71

Setting a custom class to be used with unordered set - element can't be found in the set

What I am trying to do is to make it possible to use std::unordered_set with my custom class Vector2 - including the possibility to search for objects of such class that are already in a set.

Let me give more details. The header of my class Vector2, including the custom hash table, is the following:

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

The implementation of the memeber functions of such class is trivial:

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

Then, my main functions looks like the following:

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

However, while I would expect the output to be Found it!, it is actually Nothing found. It means, while the Vector2 objects Vector2(1, 2), Vector2(3, 11) and Vector2(-5, 0) are inserted in mySet, they later are not found when searching inside such set.

What am I doing wrong?

Upvotes: 5

Views: 1724

Answers (1)

SingerOfTheFall
SingerOfTheFall

Reputation: 29966

The search operations in an unordered_set are largely dependent on the hash value of the elements, requiring that given the hash function h: if A == B, then h(A) == h(B).

When a search is performed, the hash function is used to determine the bucket to which the element belongs. After that, if there are multiple elements in the bucket, additional checks are performed to compare these elements with each other. This may be done by comparing the elements directly, re-hashing them again, or using other techniques.

Your class has two data members, and apparently you expect to "find" an element by these exact members (i.e. you expect that if A.x == B.x && A.y == B.y, then A == B and vice-versa). However your hash function only hashes based on the id of the elements, ignoring their other members, that's why it doesn't work as you expect.

The solution would be to rewrite your hash function to utilize the value of the fields. You also might want to check this documentation page.

Upvotes: 3

Related Questions