Immutable Data Structures in C++

on YouTube ↗40m

" summary

Shows that C++’s reference semantics cause real production bugs (iterator invalidation from concurrent push_back) and that passing heavy objects by value fixes races but costs copies. Introduces persistent vectors (tree of fixed-size arrays, structural sharing, branching factor ≈32) where lookup and append are O(log_32 n) — effectively constant (e.g., a billion → ~5 levels, a trillion → ~8). Implements push_back by copying only the path nodes, reusing most memory; benchmarks aren’t exhaustive but ICFP 2017 C++ results report reasonable performance vs std::vector.

AI-written summary · about

" chapters (6)

1. 0:00Immutable data structures intro
2. 3:18Value vs reference semantics
3. 17:00Value semantics challenges
4. 27:56Persistent data structures
5. 36:22Safety vs performance trade-offs
6. 38:10Conclusion

" related talks

• 01h 06mPostmodern immutable data structuresJuan Pedro Bolivar Puente · CppCon 2017
• 01h 00mOLD VERSION: The Fine Details Behind C++ Containers And AlgorithmsAmir Kirsh · CppNorth 2022
• 01h 00mThe Fine Details Behind C++ Containers And AlgorithmsAmir Kirsh · CppNorth 2022
• 01h 01mFunctional C++Kevlin Henney · NDC London 2017
• 01h 03mFunctional C++ for Fun & ProfitPhil Nash · NDC Oslo 2017
• 44mC++ Performance and OptimisationHubert Matthews · NDC TechTown 2017
• 57mCache friendly data + functional + ranges = ❤️Björn Fahller · NDC TechTown 2024
• 01h 00mMoving Faster: Everyday efficiency in modern C++Alan Talbot · CppCon 2018