The Slot Map Data Structure
summary
A slot map provides true constant time lookup, insert and erase (not amortized except when allocation occurs) by storing elements in dense contiguous memory and returning stable unique keys with an index+generation pair so stale keys never access recycled slots. Implementation uses three arrays: data, indices (holds index, generation and a free list), and a reverse mapping for constant-time erase that fills holes by moving the last element and updating its index. Trade-offs: allocation spikes, extra indirection and memory overhead.
AI-written summary · about
chapters (5)
- 0:00Start
- 0:17Guarantees of a slot_map
- 0:45How It Works: Overview
- 3:13Tradeoffs
- 3:51Questions/Comments/Contribute
related talks
30m“Esoteric Data Structures and Where to Find Them”
06mWord's one data structure
51mThe Holy Grail! A Hash Array Mapped Trie for C++
01h 17mWhat Do You Mean by "Cache Friendly"?
50mMastering the unordered_map in C++
58mFrozen data structures in C++14
57mThis Videogame Programmer Used the STL and You Will Never Guess What Happened Next
40mImmutable Data Structures in C++