一句话:提出持久迭代器抽象,将命令式迭代器风格与持久化数据结构的值语义结合,兼顾安全性与迭代器表达力。
主流命令式语言(如 C++)中可变容器的迭代器存在失效、别名、数据竞争与隐蔽副作用等隐患;而函数式语言采用的不可变数据结构虽规避了变异风险,却依赖递归与 map、foldl、traverse 等高阶组合子,既不适合表达某些算法,又暴露底层结构细节。本文提出持久迭代器(persistent iterators):迭代器在创建时对其底层容器做版本快照,从而免疫失效与别名问题;++、erase 等迭代器操作作用于迭代器本地的容器副本,实现真正的值语义——变量可重新绑定到新的持久值,同时旧版本仍可访问。作者以 LibFpp 实现该设计,这是一个 C++ 容器库,提供持久化 vector、map、set、string 等 STL 对应抽象。评估表明,LibFpp 保留了基于迭代器编程的表达力,消除了迭代器失效,且渐近复杂度与 STL 实现相当,仅因持久化而具有更高的常数因子开销;其目标场景是既需要持久性与安全性、又希望沿用熟悉迭代器模式的开发者。
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.