My favorite (constexpr) data structures
summary
A Clank interpreter models the constexpr abstract machine using an AP value (an arbitrary‑precision, variant‑style runtime value) and symbolic addresses, which lets std::vector and std::string become constexpr but leaves list, deque and associative containers behind because of pointer provenance, pointer comparison and hashing rules. Key blockers are lack of pointer tagging, no constexpr atomics or variable‑sized object storage and lifetime/temporary rules. Favorite structure is an HH array mapped trie — compressed bitmap nodes giving O(1) lookup and cheap persistence via refcounts — which needs pointer tagging and constexpr atomics to be practical.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 1:32Constexpr data structures matter
- 3:23Clang’s constexpr interpreter basics
- 9:06Pointer provenance in symbolic execution
- 13:50Lvalues vs rvalues in Clang’s interpreter
- 17:48Implementing features in interpreter
- 20:38Standard library containers and constexpr
- 27:32Why only vector and string are constexpr
- 28:16Atomic operations and control flow
- 31:39Variables in constexpr evaluation
- 34:13Virtual functions and exceptions
- 37:29Pointer-based containers challenges
- 39:17Favorite data structure: HAMT
- 47:56Q&A
related talks
39mconstexpr everything?!
56mCute C++ Tricks (and what you can learn from them): Part 2 of N
01h 03mFunctional C++ for Fun & Profit
30m“Esoteric Data Structures and Where to Find Them”
55mTemplates Made Easy With C++20
01h 39m“Leak-Freedom in C++... By Default.”
40mImmutable Data Structures in C++
01h 01mFunctional C++