LoginSignup
0

More than 3 years have passed since last update.

[C++] unorder_set custom hash function

Last updated at Posted at 2019-02-22

When we use set we can override operator < for the custom class. Because it is implemented by Red-Black tree. But it does not work for unordered_set, because unordered_set is based on hash. If we want to use unordered_set for our custom class. We must tell unordered_set the hash value for a object.

What we need to do.

  • override == operator
  • implement hash function

Here is a example

struct Point {
    int x, y;

    Point(int x, int y) : x(x), y(y) { }
    // override == operator
    bool operator == (const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// implement hash function
namespace std {
    template<>
    struct hash<Point> {
        size_t operator () (const Point& point) {
            // just a simple way to hash a point range between 0..100
            return point.x * 100 + point.y;
        }
    };
}

Test our custom class Point

int main() {
    unordered_set<Point> point_set;
    point_set.insert(Point(0,0));
    point_set.insert(Point(0,1));
    point_set.insert(Point(0,1));

    for (auto& point : point_set) {
        cout << point.x << " " << point.y << endl;
    }
    return 0;
}

Output

0 1
0 0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
0