Add Slot Map data structure

[jsrivaya]

Description

Implement a slot map (also known as a generational arena) for O(1) insert, delete, and lookup with stable handles.

A slot map stores objects in a dense array and hands out opaque keys (index + generation counter) to callers. When a slot is freed, its generation is bumped, invalidating any stale keys — so dangling handle access is detectable at O(1).

Use Cases

• Game entity/component systems (ECS)
• Connection tracking in network servers
• HFT order management (stable order IDs with fast lookup)
• Any system that needs stable external handles to objects that can be deleted

Suggested API

loon::SlotMap<T, N> map;          // capacity of N slots

auto key = map.insert(value);     // O(1), returns a Key{index, generation}
map.insert(T&& value);            // move support
T* obj  = map.get(key);           // O(1), returns nullptr if key is stale
bool ok = map.remove(key);        // O(1), bumps generation, returns to free list
bool    = map.contains(key);      // O(1) validity check
size_t  = map.size();             // current number of live objects

Key Properties

• Stable handles: keys remain valid as long as the slot is live
• Stale detection: accessing a freed slot via an old key returns nullptr (generation mismatch)
• Dense storage: objects stored contiguously for cache-friendly iteration
• No heap allocation after construction: pre-allocated std::vector backing store + free list

Implementation Notes

Each slot holds:

struct Slot {
    T value;
    uint32_t generation; // bumped on remove
};

Key encodes both index and generation:

struct Key {
    uint32_t index;
    uint32_t generation;
};

get(key) checks slots[key.index].generation == key.generation before returning the value. Free list threads through unused slots using the same uint32_t index pattern as the LRU cache.

Complexity

Operation	Time
insert	O(1)
remove	O(1)
get	O(1)
contains	O(1)
size	O(1)
Iteration	O(capacity)

References

• Slot Map — Allan Deutsch — C++ standards proposal
• EnTT — uses sparse sets + generational ids for ECS
• Game Programming Patterns — Object Pool