C++ Data Structures That Make Video Games Go Round
Talkat CppCon 2024 · on Friday, 2024-09-20· at 14:45· Cottonwood 8/9, 6700 North Gaylord Rockies Boulevard·
summary
Claims that std::vector gets you by 90% but the hard 10% needs custom containers, then shows concrete solutions: an open‑addressing hashmap using Robin Hood hashing for cache friendliness, chunked pools with a free list and versioned chunked pools for stable pointers and O(1) reuse, skip fields to iterate empty slots without branching, quadtrees/octrees for view‑culling (node capacity 4) giving ~O(log n) search, and a DAG for frame passes (Kahn’s algorithm) to reduce memory barriers and synchronization.
AI-written summary · about
chapters (16)
- 0:00Introduction
- 1:02Game engine architecture
- 2:37Engine initialization
- 4:46Resource registry
- 6:30Open addressing hash maps
- 8:10Robin Hood hashing
- 12:05Memory management
- 16:02Free lists and pools
- 17:37Index and versioning
- 20:05Colony data structure
- 22:38Gameplay systems
- 26:01Spatial partitioning
- 30:36Frame rendering
- 33:02Dependency graphs
- 35:03Topological sorting
- 42:16Q&A
related talks
01h 04mBack to Basics: Standard Library Containers in Cpp
55mIntroduction to C++ Containers - Know Your Data Structures
06mUsing STL containers efficiently
24mDesigning Fast and Efficient List-like Data Structures
01h 13mC++ Memory Model Meets High-Update-Rate Data Structures
01h 02m“Lightweight Object Persistence With Relocatable Heaps in Modern C++"
48mA Helicopter Tour of Purely Functional Data Structures
01h 05mImplementing Understandable World Class Hash Tables in C++