A Slot Map is a high-performance associative container with persistent unique keys to access stored values. It's designed for performance-critical applications where stable references, O(1) operations, and memory efficiency are essential.
- What is a Slot Map?
- Key Features
- Quick Start
- Building
- API Reference
- Key Types
- Advanced Features
- Performance
- Implementation Details
- Thread Safety
- Examples
- References
A Slot Map solves the problem of storing collections of objects that need stable, safe references but have no clear ownership hierarchy. Unlike std::unordered_map where you provide keys, a slot map generates unique keys when you insert values.
Key differences from std::unordered_map:
- Slot map generates keys for you (no key collisions)
- Guaranteed O(1) insertion, removal, and access
- Memory-stable pointers (values never move in memory)
- Automatic key invalidation when items are removed
- Efficient memory layout with page-based allocation
Perfect for:
- Game entities and component systems
- Resource management (textures, sounds, etc.)
- Object pools and handle-based systems
- Any scenario requiring safe, stable references
- O(1) Performance: Insertion, removal, and access are all O(1) in best, worst, and average case
- Memory Stability: Pointers to values remain valid until explicitly removed
- Safe References: Keys automatically become invalid when items are removed
- Memory Efficient: Page-based allocation prevents memory fragmentation
- Type Safety: Keys are typed to prevent mixing between different slot maps
- Iteration Support: Both value-only and key-value iteration
- Custom Allocators: Support for custom memory allocators
- Header Only: Single header file, easy to integrate
#include "slot_map.h"
// Create a slot map for strings
dod::slot_map<std::string> strings;
// Insert values and get unique keys
auto red_key = strings.emplace("Red");
auto green_key = strings.emplace("Green");
auto blue_key = strings.emplace("Blue");
// Access values using keys
const std::string* red_value = strings.get(red_key);
if (red_value) {
printf("Color: %s\n", red_value->c_str()); // Output: Color: Red
}
// Remove a value
strings.erase(green_key);
// Check if keys are still valid
printf("Green exists: %d\n", strings.has_key(green_key)); // Output: 0
printf("Blue exists: %d\n", strings.has_key(blue_key)); // Output: 1
// Iterate over all values
for (const auto& color : strings) {
printf("Color: %s\n", color.c_str());
}
// Iterate over key-value pairs
for (const auto& [key, color] : strings.items()) {
printf("Key: %" PRIslotkey ", Color: %s\n", uint64_t(key), color.get().c_str());
}- C++17 or later
- CMake 3.10 or later (for building tests)
Simply include the header file in your project:
#include "slot_map/slot_map.h"git clone https://github.com/SergeyMakeev/SlotMap.git
cd SlotMap
mkdir build && cd build
cmake ..
cmake --build .
# Run tests
./SlotMapTest01
./SlotMapTest02
./SlotMapTest03
./SlotMapTest04Define custom allocator macros before including the header:
#define SLOT_MAP_ALLOC(sizeInBytes, alignment) your_aligned_alloc(alignment, sizeInBytes)
#define SLOT_MAP_FREE(ptr) your_free(ptr)
#include "slot_map.h"Constructs element in-place and returns a unique key.
auto key = slot_map.emplace("Hello", "World"); // Construct string from argsReturns pointer to value or nullptr if key is invalid.
const std::string* value = slot_map.get(key);Returns true if the key exists and is valid.
if (slot_map.has_key(key)) { /* key is valid */ }Removes element if key exists. Key becomes invalid.
slot_map.erase(key);Removes and returns the value if key exists.
auto value = slot_map.pop(key); // Returns optional<T>Returns number of elements.
Returns true if container is empty.
Removes all elements but keeps allocated memory. Invalidates all keys.
Removes all elements and releases memory. Warning: Only call when no keys are in use.
Exchanges contents with another slot map.
for (const auto& value : slot_map) {
// Process value
}for (const auto& [key, value] : slot_map.items()) {
// Process key and value
}Returns internal statistics (O(n) complexity).
auto stats = slot_map.debug_stats();
printf("Active items: %u\n", stats.numAliveItems);dod::slot_map<T> // Uses 64-bit keys
dod::slot_map64<T> // Explicit 64-bit keys| Component | Bits | Range |
|---|---|---|
| Tag | 12 | 0..4,095 |
| Version | 20 | 0..1,048,575 |
| Index | 32 | 0..4,294,967,295 |
dod::slot_map32<T> // Uses 32-bit keys| Component | Bits | Range |
|---|---|---|
| Tag | 2 | 0..3 |
| Version | 10 | 0..1,023 |
| Index | 20 | 0..1,048,575 |
auto key = slot_map.emplace(value);
// Type-safe: this won't compile
// slot_map<int>::key int_key = int_map.emplace(42);
// string_map.get(int_key); // Compiler error!
// Convert to/from raw numeric type
uint64_t raw_key = key; // Implicit conversion
slot_map<T>::key restored_key{raw_key}; // Explicit constructionKeys can store small amounts of user data:
auto key = slot_map.emplace("Value");
key.set_tag(42); // Store application data
auto tag = key.get_tag(); // Retrieve: tag == 42
// Tag limits:
// 64-bit keys: 0..4,095 (12 bits)
// 32-bit keys: 0..3 (2 bits)Adjust memory allocation granularity:
// Default page size is 4096 elements
dod::slot_map<T, dod::slot_map_key64<T>, 8192> large_pages;
dod::slot_map<T, dod::slot_map_key64<T>, 1024> small_pages;Control when slot indices are reused:
// Default threshold is 64
dod::slot_map<T, dod::slot_map_key64<T>, 4096, 128> conservative_reuse;- Insertion: O(1) amortized
- Removal: O(1)
- Access: O(1)
- Iteration: O(n) where n is number of alive elements
- Page-based allocation: 4096 elements per page by default
- Pointer stability: Values never move once allocated
- Memory efficiency: Pages are released when all slots become inactive
- Cache-friendly: Sequential iteration over alive elements only
When a slot's version counter reaches maximum value:
- The slot is marked as inactive
- No new keys will be generated for this slot
- Guarantees no key collisions even with version wrap-around
- Recently freed slots aren't immediately reused
- Minimum threshold (default 64) prevents rapid version increments
- Balances memory usage with collision avoidance
- Elements are allocated in pages (default 4096 elements)
- Pages are released when all slots in a page become inactive
- Provides memory stability and prevents fragmentation
Slot maps are NOT thread-safe. External synchronization is required for:
- Concurrent access from multiple threads
- Reader-writer scenarios
For thread-safe usage:
std::shared_mutex mutex;
dod::slot_map<T> slot_map;
// Reader
{
std::shared_lock lock(mutex);
auto value = slot_map.get(key);
}
// Writer
{
std::unique_lock lock(mutex);
auto key = slot_map.emplace(value);
}struct Transform { float x, y, z; };
struct Health { int hp, max_hp; };
dod::slot_map<Transform> transforms;
dod::slot_map<Health> healths;
// Create entity
auto entity_id = generate_entity_id();
auto transform_key = transforms.emplace(Transform{0, 0, 0});
auto health_key = healths.emplace(Health{100, 100});
// Store keys in entity
register_component(entity_id, transform_key);
register_component(entity_id, health_key);dod::slot_map<Texture> textures;
dod::slot_map<Sound> sounds;
class ResourceManager {
using TextureHandle = dod::slot_map<Texture>::key;
using SoundHandle = dod::slot_map<Sound>::key;
TextureHandle load_texture(const std::string& path) {
return textures.emplace(load_texture_from_file(path));
}
const Texture* get_texture(TextureHandle handle) {
return textures.get(handle);
}
};class BulletPool {
struct Bullet { float x, y, dx, dy; bool active; };
dod::slot_map<Bullet> bullets;
public:
using BulletHandle = dod::slot_map<Bullet>::key;
BulletHandle spawn(float x, float y, float dx, float dy) {
return bullets.emplace(Bullet{x, y, dx, dy, true});
}
void update() {
for (auto& bullet : bullets) {
if (bullet.active) {
bullet.x += bullet.dx;
bullet.y += bullet.dy;
}
}
}
void destroy(BulletHandle handle) {
bullets.erase(handle); // Handle becomes invalid automatically
}
};- Sean Middleditch: Data Structures for Game Developers: The Slot Map, 2013
- Niklas Gray: Building a Data-Oriented Entity System, 2014
- Noel Llopis: Managing Data Relationships, 2010
- Stefan Reinalter: Adventures in Data-Oriented Design - External References, 2013
- Niklas Gray: Managing Decoupling Part 4 - The ID Lookup Table, 2011
- Sander Mertens: Making the Most of ECS Identifiers, 2020
- Michele Caini: ECS back and forth. Part 9 - Sparse Sets and EnTT, 2020
- Andre Weissflog: Handles are the Better Pointers, 2018
- Allan Deutsch: C++Now 2017: "The Slot Map Data Structure", 2017
- Jeff Gates: Init, Update, Draw - Data Arrays, 2012
- Niklas Gray: Data Structures Part 1: Bulk Data, 2019