Postmodern immutable data structures
summary
Library Immer implements persistent vectors using Relaxed Radix Balanced Trees with a 32-way branching factor (≈7 levels for 32-bit indexes) and an embedding variant for large or tiny Ts, offering logarithmic concatenation/insertion and effectively constant random access. Transient and rvalue-aware updates avoid many copies; default policy uses atomic reference counting but supports alternate GC/allocators. Iteration via buffer-aware callbacks is about 1.5× slower than std::vector, and the demo editor Ewig opens the ~1 GB Esperanto Wikipedia file instantly and saves asynchronously while editing.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 0:59The problem with mutability
- 4:07Immutable data structures
- 6:38The immu library
- 7:40Radix balanced trees
- 13:34Concatenation and optimization
- 17:01Transient data structures
- 21:11Composing transients
- 23:56Benchmarking performance
- 25:58Text editor application
- 32:12MVC vs. unidirectional flow
- 36:47Implementing the text editor
- 45:47Implementing undo/redo
- 50:53Q&A and future work
