Step 4 of 5

Hashing your own keys

std::unordered_map<Point, int> doesn't compile until you tell it how to hash a Point (and how to compare two for equality). Give it a hasher struct:

struct PointHash {
    std::size_t operator()(const Point& p) const {
        std::size_t h = std::hash<int>{}(p.x);
        return h ^ (std::hash<int>{}(p.y) + 0x9e3779b9 + (h << 6) + (h >> 2));   // hash_combine
    }
};
std::unordered_map<Point, int, PointHash> visits;

The hash_combine formula (from Boost) mixes the second hash in so that (1, 2) and (2, 1) land in different buckets. A lazy x ^ y would make them collide, and all points with x == y hash to 0.

Your turn: write PointHash and int revisits(const std::string& moves): starting at (0,0), apply moves U/D/L/R and count how many moves land on a point already visited (the start counts as visited).

Previous: A string-keyed map with erase Next: Challenge: an LRU cache