Persistent Iterators with Value Semantics
summary
Proposes persistent iterators that snapshot containers so iterator operations return new versions, implemented as the LibFpp C++ library using a finger tree backbone and iterator zippers that rebuild only the modified path. Claims amortized-constant copying for iterator updates, comparable asymptotic complexity to STL but higher constant factors, and automatic reclamation via reference counting. Presents microbenchmarks versus STL and third-party libs (vectors slower, sets competitive) and supplies reusable artifacts and source.
AI-written summary · about
chapters (15)
- 0:00Persistent iterators intro
- 1:23Persistence advantages
- 2:47Goal of persistence
- 3:31Mutable iterators solution
- 5:59Functional approach drawbacks
- 7:23Persistent iterators with value semantics
- 8:47Finger tree efficiency
- 10:32Benchmarking containers
- 11:56Conclusion and library
- 12:40Q&A
- 13:02Mutable to persistent transition
- 14:06Optimization comparison
- 15:31Insertion operations support
- 16:13Derivative structures
- 16:54Persistent vs mutable
related talks
01h 00mBuilding and Extending the Iterator Hierarchy in a Modern, Multicore World
37mEnhancing STL containers
59mThe Most Valuable Values
01h 13mFrom Iterators to Ranges — the Upcoming Evolution of the Standard Library
57mWriting Great Libraries: 89 Easy Steps
01h 02mWriting Standard Library Compliant Data Structures and Algorithms
32mC++ Standard Library "Little Things”
36mInterfaces Matter