Frozen data structures in C++14
summary
Frozen provides header-only replacements for map/set/unordered_map/unordered_set that are truly immutable and constructed at compile time via constexpr constructors, eliminating static init cost and the initialization-order fiasco. It uses compile-time-sorted arrays and a branch-light binary search to cut lookup time on small sets, and a compile-time generator for perfect minimal hashing (bucket sorting plus per-bucket seeds) to make collision-free unordered tables; users report thousands-of-entry tables (e.g., HTML entities) compile and run with smaller binaries and faster lookups.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 3:15Const and data sections
- 7:51Need for frozen containers
- 10:04Frozen set and map design
- 13:22Performance benefits
- 18:00Perfect minimal hashing
- 23:44Binary search assembly
- 27:21Compile-time hashing algorithm
- 32:01Implementation details
- 39:41Use cases and examples
- 45:36Compile-time limits
- 47:04Algorithm trade-offs
- 48:36Real-world applications
- 51:30Q&A
related talks
01h 03mFunctional C++ for Fun & Profit
40mImmutable Data Structures in C++
01h 01mFunctional C++
49mMy favorite (constexpr) data structures
57mCache friendly data + functional + ranges = ❤️
51mThe Holy Grail! A Hash Array Mapped Trie for C++
51m“Cache Optimized Hash Tables”
52mC++ Performance Tips - Cutting Down on Unnecessary Objects