Lune

PLDI2026Top-tier venue

Persistent Iterators with Value Semantics

Yihe Li, Gregory J. Duck

Abstract

Iterators are a fundamental programming abstraction for traversing and modifying elements in containers in mainstream imperative languages such as C++. Iterators provide a uniform access mechanism that hides low-level implementation details of the underlying data structure. However, iterators over mutable containers suffer from well-known hazards including invalidation, aliasing, data races, and subtle side effects. Immutable data structures, as used in functional programming languages, avoid the pitfalls of mutation but rely on a very different programming model based on recursion and higher-order combinators (map, foldl, traverse, etc.) rather than iteration. However, these combinators are not always well-suited to expressing certain algorithms, and recursion can expose implementation details of the underlying data structure. In this paper, we propose persistent iterators-a new abstraction that reconciles the familiar iterator-based programming style of imperative languages with the semantics of persistent data structures. A persistent iterator snapshots the version of its underlying container at creation, ensuring safety against invalidation and aliasing. Iterator operations (++, erase, etc.) operate on the iterator-local copy of the container, giving true value semantics: variables can be rebound to new persistent values while previous versions remain accessible. We implement our approach in the form of LibFpp-a C++ container library providing persistent vectors, maps, sets, strings, and other abstractions as persistent counterparts to the Standard Template Library (STL). Our evaluation shows that LibFpp retains the expressiveness of iterator-based programming, eliminates iterator-invalidation, and achieves asymptotic complexities comparable to STL implementations-albeit with the higher constant-factor overheads of persistence. Our design targets use cases where persistence and safety are desired, while allowing developers to retain familiar iterator-based programming patterns.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. FliT: a library for simple and efficient persistent algorithmsYuanhao Wei, Naama Ben-David, Michal Friedman, Guy E. Blelloch et al.PPoPP 2022 · 19 citations
  2. Concurrent deferred reference counting with constant-time overheadDaniel Anderson, Guy E. Blelloch, Yuanhao WeiPLDI 2021 · 26 citations
  3. Pronto: Easy and Fast Persistence for Volatile Data StructuresAmir Saman Memaripour, Joseph Izraelevitz, Steven SwansonASPLOS 2020 · 55 citations
  4. Compositionality and Observational Refinement for Linearizability with CrashesArthur Oliveira Vale, Zhongye Wang, Yixuan Chen, Peixin You et al.OOPSLA 2024 · 1 citation
  5. The Path to Durable LinearizabilityEmanuele D'Osualdo, Azalea Raad, Viktor VafeiadisPOPL 2023 · 6 citations
Dusk over the sea between two cliffs drawn in fine vertical lines