arxiv: 2604.14072 · v1 · submitted 2026-04-15 · 💻 cs.PL

Recognition: unknown

Persistent Iterators with Value Semantics

Yihe Li , Gregory J. Duck

Authors on Pith no claims yet

Pith reviewed 2026-05-10 11:39 UTC · model grok-4.3

classification 💻 cs.PL

keywords persistent iteratorsvalue semanticsiterator invalidationpersistent data structuresC++ containersiterator safety

0 comments

The pith

Persistent iterators snapshot a container's version at creation to enable safe value-semantic operations on a local copy.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proposes persistent iterators to combine the familiar iteration style of imperative languages with the safety guarantees of persistent data structures. A persistent iterator captures the state of its underlying container when created, after which all operations work exclusively on an iterator-local copy rather than the shared original. This approach prevents the classic problems of iterator invalidation, aliasing, and unintended side effects while still allowing variables to be rebound to new versions without disturbing prior ones. The authors realize the idea in a C++ library supplying persistent counterparts to standard containers and report that the resulting code retains the expressiveness of ordinary iterator-based algorithms.

Core claim

Persistent iterators snapshot the version of their underlying container at creation. Iterator operations thereafter execute against this local copy of the container, delivering true value semantics in which rebinding a variable to a fresh persistent value leaves all previous versions intact and accessible.

What carries the argument

The persistent iterator, which holds a private snapshot of the container and routes all read and write operations through that snapshot.

If this is right

Iterator invalidation hazards disappear because each iterator works on its own snapshot.
Aliasing and data-race problems are avoided since operations never mutate the original container through the iterator.
Value semantics become available inside iteration loops, allowing safe rebinding of variables to new container versions.
Existing iterator-based algorithms from the STL can be reused without rewriting them in a recursive or combinator style.
The library supplies persistent vectors, maps, sets, and strings whose iterator interfaces match the familiar STL pattern.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same snapshot-and-local-copy pattern could be applied to other mutable abstractions such as file handles or database cursors.
Because each iterator is isolated, the design naturally supports safe concurrent traversal of different versions of the same logical container.
Programmers could mix persistent and non-persistent containers in the same codebase by choosing iterator type at the point of use.

Load-bearing premise

The persistent data structures and their local copies can be implemented so that asymptotic costs stay comparable to ordinary containers without large constant-factor or memory overhead in practice.

What would settle it

A direct performance comparison showing that traversal, insertion, or lookup through persistent iterators is asymptotically slower or uses asymptotically more memory than the corresponding operations on standard containers.

Figures

Figures reproduced from arXiv: 2604.14072 by Gregory J. Duck, Yihe Li.

**Figure 1.** Figure 1: Comparing a simple “filter non-ASCII characters from a string” function across paradigms using C++ STL, C++ LibFpp, and Haskell. Version (a) is the idiomatic implementation using LibFpp persistent iterators. Versions (b) and (c) are idiomatic implementations for std::list<char> and std::string, respectively. Finally, we consider (d)/(e) as the idiomatic combinator/recursive implementation over Haskell Stri… view at source ↗

**Figure 2.** Figure 2: Example of a classic iterator invalidation bug variant of [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 3.** Figure 3: Sample programs that illustrate the advantages of persistent iterators, including stateful filtering [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗

**Figure 4.** Figure 4: Example finger trees representing the sequences [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗

**Figure 5.** Figure 5: Example finger tree A with a zipper Z pointing to element 8, and a zipper Y pointing to a newly inserted element 9. Note that zippers are also persistent structures with complex structural sharing relationships (even between zippers), as represented by the dashed lines. 7 8 10 11 12 13 14 15 16 17 18 19 20 21 22 23 3 4 5 6 24 25 26 27 1 2 28 29 1 Ⓐ 1 0 0 0 1 0 0 2 9 d ⓏⓎ provide a familiar, STL-style ite… view at source ↗

**Figure 6.** Figure 6: Highly optimized (de)allocation routines ( [PITH_FULL_IMAGE:figures/full_fig_p014_6.png] view at source ↗

**Figure 7.** Figure 7: Figure showing container micro-benchmark results for [PITH_FULL_IMAGE:figures/full_fig_p018_7.png] view at source ↗

**Figure 8.** Figure 8: Figure showing iterator micro-benchmark results for [PITH_FULL_IMAGE:figures/full_fig_p019_8.png] view at source ↗

**Figure 9.** Figure 9: Figure showing heap consumption for vectors and sets in LibFpp and other libraries under different container size. Scales are logarithmic. For Immer, transient-mode is not used. In addition to the asymptotic complexity and run time of containers, memory consumption is also an important metric. In light of this, each of LibFpp and other baseline containers are parameterized with unsigned 64-bit integers, an… view at source ↗

read the original 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 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 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. Our design targets use cases where persistence and safety are desired, while allowing developers to retain familiar iterator-based programming patterns.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper offers safe persistent iterators in C++ via snapshots and local copies, but performance details are thin.

read the letter

The key takeaway is that this work introduces persistent iterators for C++ that capture a container snapshot on creation and perform operations on an iterator-local copy, delivering value semantics and protection against invalidation and aliasing while preserving the familiar iterator programming style. The paper does a good job laying out the problems with standard mutable iterators in the STL, such as hazards from mutation and the mismatch with persistent data structures from functional programming. By implementing LibFPP with persistent versions of common containers like vectors and maps, it shows a practical path forward. The approach allows rebinding variables to new versions without losing access to old ones, which fits well with versioned data needs in systems code. This reconciliation of imperative iteration with persistence is the main novelty. On the positive side, the design targets exactly the use cases where developers want safety but prefer not to adopt recursive or higher-order functional patterns. The abstract indicates that the library retains expressiveness and achieves good complexities, which if true would make it a drop-in improvement for many applications. The main soft spot is around the performance of those local copies. The central claim relies on the persistent structures enabling efficient snapshots and sharing so that iterator operations stay fast and memory use stays reasonable. Without shown benchmarks or detailed analysis of how the local copies are managed, especially in scenarios with many iterators like in loops or algorithms, it's difficult to assess if the comparable to STL promise holds in practice. If the copies aren't cheap enough, it could lead to unexpected overheads. This paper is for C++ programmers and library implementers focused on safer and more robust data structure usage. It has enough of a concrete proposal and implementation to warrant a serious referee, who could probe the evaluation and any trade-offs. I recommend sending it for peer review.

Referee Report

2 major / 0 minor

Summary. The paper proposes persistent iterators as a new abstraction for C++ that snapshot the version of an underlying persistent container (e.g., vector, map) at creation time. Iterator operations then act on an iterator-local copy, delivering value semantics, immunity to invalidation and aliasing, and compatibility with familiar imperative iterator-based code. The design is realized in the LibFPP library, which supplies persistent counterparts to STL containers; the abstract asserts that the library preserves expressiveness while achieving asymptotic complexities comparable to standard STL implementations.

Significance. If the efficiency claims hold, the work offers a practical bridge between imperative iterator idioms and persistent data structures, allowing developers to retain STL-style traversal without mutation hazards. This could be relevant for concurrent, versioned, or safety-critical C++ codebases that currently must choose between mutable containers with invalidation risks or a full shift to recursive/functional styles.

major comments (2)

[Abstract] Abstract: the central claim that LibFPP 'achieves asymptotic complexities comparable to STL implementations' is unsupported by any derivation, benchmark data, or implementation description. The text provides only the high-level design statement; without evidence that iterator-local copies incur only logarithmic (or better) overhead via structural sharing, the practicality assertion cannot be evaluated.
[Design description] Design description (persistent iterators section): the mechanism of 'iterator-local copy of the container' is presented as cheap due to persistence, yet no concrete representation (e.g., how a persistent vector or map maintains structural sharing when an iterator is created) or complexity analysis is supplied. If the local copy is not a constant-time persistent reference but a full duplication, algorithms that instantiate many iterators (nested loops, std::for_each with side effects) would incur linear space per iterator and potentially quadratic total cost, directly contradicting the comparable-complexity guarantee.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive assessment of the significance of our work and for the constructive major comments. We agree that the current manuscript would benefit from more explicit support for the complexity claims and a more detailed description of the implementation. Below we respond to each comment and outline the revisions we will make to the next version of the paper.

read point-by-point responses

Referee: [Abstract] Abstract: the central claim that LibFPP 'achieves asymptotic complexities comparable to STL implementations' is unsupported by any derivation, benchmark data, or implementation description. The text provides only the high-level design statement; without evidence that iterator-local copies incur only logarithmic (or better) overhead via structural sharing, the practicality assertion cannot be evaluated.

Authors: We acknowledge that the abstract's claim would be stronger with direct supporting material. The manuscript states that evaluation demonstrates comparable complexities, but we agree the abstract itself provides no derivation or data. In revision we will update the abstract to briefly note that complexities are achieved via structural sharing (with full details and benchmarks in the evaluation section) and add a short complexity paragraph early in the design description. This will make the practicality assertion evaluable without requiring the reader to reach later sections. revision: yes
Referee: [Design description] Design description (persistent iterators section): the mechanism of 'iterator-local copy of the container' is presented as cheap due to persistence, yet no concrete representation (e.g., how a persistent vector or map maintains structural sharing when an iterator is created) or complexity analysis is supplied. If the local copy is not a constant-time persistent reference but a full duplication, algorithms that instantiate many iterators (nested loops, std::for_each with side effects) would incur linear space per iterator and potentially quadratic total cost, directly contradicting the comparable-complexity guarantee.

Authors: This is a valid concern about the current level of detail. The manuscript describes the iterator-local copy at a high level but does not specify the underlying representation or analyze space costs for multiple iterators. We will revise the persistent iterators section to describe LibFPP's concrete structures (path-copying trees for vectors and maps) and explain that an iterator stores only a persistent root reference obtained in constant time. Operations then traverse the shared structure at logarithmic cost. We will add a complexity table and a brief argument showing that space remains proportional to distinct versions rather than the number of iterators, directly addressing the risk of quadratic blow-up. revision: yes

Circularity Check

0 steps flagged

No circularity: design proposal with independent implementation claims

full rationale

The paper introduces persistent iterators as a new abstraction reconciling iterator style with persistent data structures, implemented in LibFPP. No equations, fitted parameters, or first-principles derivations appear in the abstract or described content. Claims of comparable asymptotic complexity rest on evaluation and implementation details rather than reducing to self-definitions, self-citations, or renamed inputs. The central design (snapshotting versions for value semantics) is presented as a proposal, not derived from prior results by the same authors in a load-bearing way. This matches the default expectation of no significant circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The design rests on standard persistent data structure techniques from functional programming and C++ container semantics; no free parameters or invented entities are introduced.

axioms (1)

domain assumption Persistent data structures can be implemented with efficient path-copying or similar techniques.
Invoked implicitly when claiming comparable asymptotic complexity to STL.

pith-pipeline@v0.9.0 · 5572 in / 1110 out tokens · 17292 ms · 2026-05-10T11:39:36.239130+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

22 extracted references · 8 canonical work pages

[1]

Technical Report 14882:2024

2024.Programming Languages — C++. Technical Report 14882:2024. ISO/IEC

2024
[2]

Driscoll, N

J. Driscoll, N. Sarnak, D. Sleator, and R. Tarjan. 1986. Making data structures persistent. InSymposium on Theory of computing. ACM

1986
[3]

URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs

J. Eyolfson and P. Lam. 2016. C++ const and immutability: an empirical study of writes-through-const. InEuropean Conference on Object-Oriented Programming. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs. ECOOP.2016.8

work page doi:10.4230/lipics 2016
[4]

Gamma, R

E. Gamma, R. Helm, R. Johnson, and J. Vlissides. 1995.Design patterns: elements of reusable object-oriented software. Addison-Wesley

1995
[5]

Hinze and R

R. Hinze and R. Paterson. 2006. Finger trees: a simple general-purpose data structure.Journal of Functional Programming 16, 2 (2006), 197–217. doi:10.1017/S0956796805005769

work page doi:10.1017/s0956796805005769 2006
[6]

G. Huet. 1997. The Zipper.Journal of Functional Programming7, 5 (1997), 549–554. doi:10.1017/S0956796897002864

work page doi:10.1017/s0956796897002864 1997
[7]

Josuttis

N. Josuttis. 2024.Healing the Filter View. Technical Report P3329R0. ISO/IEC JTC1/SC22/WG21 C++ Standards Committee. https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p3329r0.pdf WG21 paper

2024
[8]

J. Lakos. 1996.Large-Scale C++ Software Design. Addison-Wesley

1996
[9]

Persistent Iterators with Value Semantics

Yihe Li and Gregory Duck. 2026.Artifact for the paper "Persistent Iterators with Value Semantics" - Version 2. doi:10. 5281/zenodo.19392634

2026
[10]

Meta. 2026. Folly: An open-source C++ library developed and used at Facebook. https://github.com/facebook/folly

2026
[11]

Nikolakopoulos, A

Y. Nikolakopoulos, A. Gidenstam, M. Papatriantafilou, and P. Tsigas. 2015.Of Concurrent Data Structures and Iterations. Springer International Publishing, Cham, 358–369. doi:10.1007/978-3-319-24024-4_20

work page doi:10.1007/978-3-319-24024-4_20 2015
[12]

C. Okasaki. 1995. Simple and efficient purely functional queues and deques.Journal of Functional Programming5, 4 (1995), 583–592. doi:10.1017/S0956796800001489

work page doi:10.1017/s0956796800001489 1995
[13]

Oracle Corporation. 2026. Java Collections Framework. https://docs.oracle.com/en/java/javase/21/docs/api/java.base/ java/util/doc-files/coll-overview.html

2026
[14]

J. Puente. 2017. Persistence for the masses: RRB-vectors in a systems language. InInternational Conference on Functional Programming. ACM. doi:10.1145/3110260

work page doi:10.1145/3110260 2017
[15]

Python Software Foundation. 2026. Iterator Types. https://docs.python.org/3/library/stdtypes.html#iterator-types

2026
[16]

Rust Project Developers. 2026. Iterator Trait. https://doc.rust-lang.org/std/iter/trait.Iterator.html

2026
[17]

2011.The Boost C++ Libraries

Boris Schling. 2011.The Boost C++ Libraries. XML Press

2011
[18]

Steindorfer and J

M. Steindorfer and J. Vinju. 2015. Optimizing hash-array mapped tries for fast and lean immutable JVM collections. In Object-Oriented Programming, Systems, Languages, and Applications. ACM. doi:10.1145/2814270.2814312

work page doi:10.1145/2814270.2814312 2015
[19]

Stepanov and M

A. Stepanov and M. Lee. 1995.The Standard Template Library. Technical Report. Hewlett-Packard Laboratories

1995
[20]

Stucki, T

N. Stucki, T. Rompf, V. Ureche, and P. Bagwell. 2015. RRB vector: a practical general purpose immutable sequence. In International Conference on Functional Programming. ACM. doi:10.1145/2784731.2784739

work page doi:10.1145/2784731.2784739 2015
[21]

The Abseil Team. 2026. Abseil Common Libraries (C++). https://github.com/abseil/abseil-cpp

2026
[22]

The Catch2 Team. 2026. Catch2: A modern, C++-native, test framework for unit-tests, TDD and BDD. https: //github.com/catchorg/Catch2. Received 2025-11-14; accepted 2026-04-03 Proc. ACM Program. Lang., Vol. 10, No. PLDI, Article 246. Publication date: June 2026

2026