Step 4 of 5

Hashing your own keys

std::unordered_map<std::string, int> works out of the box because the standard library ships std::hash<std::string>. For your own key types, like a Point, it doesn't compile until you provide two things:

1. Equality: how to tell whether two keys are the same. bool operator==(const Point&) const = default; generates a member-by-member comparison.
2. A hash: a struct whose operator() turns a key into a std::size_t, passed as an extra template argument.

#include <functional>
#include <iostream>
#include <string>
#include <unordered_map>

struct Cell {
    int row, col;
    bool operator==(const Cell&) const = default;
};

struct CellHash {
    std::size_t operator()(const Cell& c) const {
        std::size_t h = std::hash<int>{}(c.row);
        return h ^ (std::hash<int>{}(c.col) + 0x9e3779b9 + (h << 6) + (h >> 2));
    }
};

int main() {
    std::unordered_map<Cell, std::string, CellHash> sheet;
    sheet[{0, 0}] = "Name";
    sheet[{0, 1}] = "Score";
    sheet[{1, 0}] = "Ada";
    std::cout << sheet[{0, 1}] << " " << sheet.size() << " " << sheet.contains({1, 1}) << "\n";

    CellHash h;
    std::cout << (h({1, 2}) != h({2, 1})) << "\n";   // order matters to this hash
}

Score 3 0
1

Combining hashes

The formula is hash_combine from the Boost library: it mixes the second hash into the first with shifts and a constant, so that (1, 2) and (2, 1) land in different buckets. A lazy x ^ y would make those two collide, and every point with x == y would hash to 0. A hash that sends many keys to the same bucket still gives correct answers, but lookups degrade toward O(n).

Your task

Write PointHash the same way. In revisits, keep a std::unordered_set<Point, PointHash> of visited points, starting with {0, 0}. For each move, update the position; if insert(...).second is false, the point was already visited, so count it.

Your task

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).

Challenge 2

Write KillHash for Kill { std::string player; int round; } by combining the hashes of both fields (for example h1 * 31 + h2, or h1 ^ (h2 << 1)), and int distinct_kills(const std::vector<Kill>& kills) that counts different kills with an std::unordered_set<Kill, KillHash>.

Challenge 3

Write std::vector<std::vector<std::string>> group_anagrams(const std::vector<std::string>& words). Words are anagrams when they have the same letters, so use the sorted letters as the key of an std::unordered_map. Return the groups in order of each group's first word, with the words in each group in their original order.

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