What properties should an object have to be used as a…

In the standard C++ library, to use a type as a key in std::map or std::unordered_map, it must possess the following properties:

For std::map (based on a red-black tree):

Comparability: The type must support a weak strict ordering, usually implemented by the < operator. This < operator must be:
- Irreflexive: x < x is always false.
- Transitive: If f(x, y) and f(y, z) are true, then f(x, z) is also true (where f is the relation, e.g., <).
- Asymmetric: If x < y is true, then y < x is false.
- Alternatively, a comparator (e.g., a lambda function or functor class) can be provided when creating the container.

For std::unordered_map (based on a hash table):

Hashability: There must be a hash function defined for the type, which computes a std::size_t value based on an object of that type. This is usually implemented by:
- Specializing the std::hash template class for the type.
- Using built-in hash functions for primitive types and pointers.
- For user-defined types, it is often necessary to explicitly define a specialization of std::hash or provide a hash functor when creating the container.
Equality comparability: The type must support equality comparison, usually implemented by the == operator. This operator must be:
- Reflexive: x == x is always true.
- Symmetric: If x == y is true, then y == x is also true.
- Transitive: If x == y and y == z are true, then x == z is also true.
- Alternatively, a comparison function for equality (e.g., a lambda or functor) can be provided when creating the container.

Example specialization of std::hash:

#include <functional> // For std::hash

struct Point {
    int x, y;

    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// Specialization of std::hash for Point to make it hashable
namespace std {
    template <>
    struct hash<Point> {
        size_t operator()(const Point& p) const {
            // Simple combined hash function
            return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
        }
    };
}

Example comparator for std::map:

#include <map>

struct Point {
    int x, y;
};

struct PointCompare {
    bool operator()(const Point& a, const Point& b) const {
        if (a.x != b.x) {
            return a.x < b.x;
        }
        return a.y < b.y;
    }
};

// Creating a map with a custom comparator
// std::map<Point, int, PointCompare> my_map;

What properties should an object have to be used as a key in associative containers?