stl · advanced

STL: Custom Objects in map/unordered_map — operator< and Hash

Custom types as container keys require different things for map vs unordered_map. std::map: operator< with strict weak ordering (3 rules: irreflexive, asymmetric, transitive). Lexicographic ordering (compare x, then y) naturally satisfies all three. C++20: auto operator<=>() = default generates all comparison operators. std::unordered_map: hash functor (selects bucket) + operator== (confirms match in chain). Options: 1) Custom hasher struct as template parameter. 2) Specialize std::hash<T> in namespace std. Hash combination pattern: h ^= hash<int>{}(field) + 0x9e3779b9 + (h<<6) + (h>>2) (FNV-1a style). Rule: equal objects must have equal hashes; hash collision (unequal objects, same hash) is allowed but degrades performance. Never mutate a key after insertion: map UB (breaks RB tree); unordered_map silent loss (wrong bucket).

The code

// Custom objects in map — requires operator<
struct Point {
    int x, y;
    // map needs strict weak ordering via operator<
    bool operator<(const Point& o) const {
        if (x != o.x)
            return x < o.x;
        return y < o.y; // lexicographic order
    }
};
std::map<Point, string> m;
m[{1, 2}] = "A";
m[{3, 4}] = "B";
// m[{1,2}] == "A" ✓

// Custom objects in unordered_map — requires hash + ==
struct PointHash {
    size_t operator()(const Point& p) const {
        // FNV-1a style combination:
        size_t h = std::hash<int>{}(p.x);
        h ^= std::hash<int>{}(p.y) + 0x9e3779b9 + (h << 6) + (h >> 2);
        return h;
    }
};
struct PointEq {
    bool operator()(const Point& a, const Point& b) const {
        return a.x == b.x && a.y == b.y;
    }
};
std::unordered_map<Point, string, PointHash, PointEq> um;
um[{1, 2}] = "A"; // hash({1,2}) → bucket

// Alternative: specialize std::hash<Point>
namespace std {
template <>
struct hash<Point> {
    size_t operator()(const Point& p) const {
        return hash<int>{}(p.x) ^ (hash<int>{}(p.y) << 16);
    }
};
} // namespace std
// Now: unordered_map<Point, string> just works
// Point STILL needs operator== (separate from hash)

// Strict weak ordering requirements for map:
// 1. Irreflexivity:  NOT (a < a)
// 2. Asymmetry:      if a < b then NOT (b < a)
// 3. Transitivity:   if a < b and b < c then a < c
// Violating any → undefined behavior in std::map/set

What this lesson walks through

1. 01map requires operator< — strict weak ordering
2. 02Strict weak ordering — 3 rules that must hold
3. 03unordered_map requires hash + operator==
4. 04std::hash specialization — the cleaner approach
5. 05map vs unordered_map with custom types — comparison
6. 06Common pitfalls — mutable keys and hash invalidation

To store a custom type as a map key, it must provide operator< with strict weak ordering (irreflexive, asymmetric, transitive). The map uses this to navigate the red-black tree. Lexicographic ordering (compare x first, then y) is the standard pattern and naturally satisfies all three requirements.