# Can you consider adding persistent vector data-structure?

**URL:** <https://forums.swift.org/t/can-you-consider-adding-persistent-vector-data-structure/60643>\
**Category:** Collections\
**Created:** [October 4, 2022, 8:00am UTC](https://forums.swift.org/t/can-you-consider-adding-persistent-vector-data-structure/60643 "2022-10-04T08:00:28Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Serendipity](https://avatars.discourse-cdn.com/v4/letter/s/f17d59/32.png) [@Serendipity](https://forums.swift.org/u/Serendipity)\
**Post date:** [October 4, 2022, 8:00am UTC](https://forums.swift.org/t/can-you-consider-adding-persistent-vector-data-structure/60643/1 "2022-10-04T08:00:28Z")

</div>

Hello folks.

Can you consider adding an implementation for "persistent vector" data structure. That works like an array but with \<= O(log n) complexity for all operations. Here are examples.

- [List Struct Reference](http://attaswift.github.io/BTree/api/Structs/List.html)
- [Vector in im::vector - Rust](https://docs.rs/im/latest/im/vector/struct.Vector.html)

Please let me know if I'm missing something already exists.

---

<div class="post-metadata">

**Author:** ![lorentey](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/lorentey/32/1299_2.png) [@lorentey](https://forums.swift.org/u/lorentey)\
**Post date:** [October 5, 2022, 7:46pm UTC](https://forums.swift.org/t/can-you-consider-adding-persistent-vector-data-structure/60643/2 "2022-10-05T19:46:56Z")

</div>

Yes, this would be a very high-value data structure to add to the package! I expect the implementation will most likely be based on (a possibly adapted version of) the same underlying (count-augmented) BTree implementation as will ship for `SortedSet`/`SortedDictionary`.

There are preliminary versions of SortedSet & SortedDictionary on the release/1.1 branch now, but they aren't ready for production use yet. The persistent vector implementation would ideally come immediately after work on these two data structures has concluded.

---

<div class="post-metadata">

**Author:** ![garrettm](https://avatars.discourse-cdn.com/v4/letter/g/74df32/32.png) [@garrettm](https://forums.swift.org/u/garrettm)\
**Post date:** [January 31, 2023, 1:23am UTC](https://forums.swift.org/t/can-you-consider-adding-persistent-vector-data-structure/60643/3 "2023-01-31T01:23:38Z")

</div>

I would also find this very useful! Any word on progress here?

---

<div class="post-metadata">

**Author:** ![garrettm](https://avatars.discourse-cdn.com/v4/letter/g/74df32/32.png) [@garrettm](https://forums.swift.org/u/garrettm)\
**Post date:** [February 27, 2024, 1:31am UTC](https://forums.swift.org/t/can-you-consider-adding-persistent-vector-data-structure/60643/4 "2024-02-27T01:31:39Z")

</div>

Hello, sorry to bump, but I still would find this very useful to have, and a very sensible addition to Swift. Has there been any progress made on this?

---

<div class="post-metadata">

**Author:** ![lorentey](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/lorentey/32/1299_2.png) [@lorentey](https://forums.swift.org/u/lorentey)\
**Post date:** [July 8, 2024, 10:23pm UTC](https://forums.swift.org/t/can-you-consider-adding-persistent-vector-data-structure/60643/5 "2024-07-08T22:23:01Z")

</div>

We have an unstable `Rope` implementation, but it isn't ready for use yet -- it will see source incompatible changes on the way to finalization.

> [@A Rope type seems to be present, but undocumented](https://forums.swift.org/t/a-rope-type-seems-to-be-present-but-undocumented/67973/4):
>
> Rope is production ready in the narrow sense that [AttributedString is using it in production](https://github.com/apple/swift-foundation/blob/main/Sources/FoundationEssentials/AttributedString/AttributedString%2BGuts.swift) in the variant that recently shipped in Foundation. The implementation is complete inasmuch that it has a real life adopter that is using it to solve a real problem, and it seems to work as we expected it would. The current implementation does have some obvious missing functionality, and (as always) there are some low-hanging performance optimizations yet to be done. Rope is not ready for general public…

As a practical matter, all feature work on new data structures in swift-collections is currently on hold, while we're focusing on Swift's [roadmap for improving performance predictability](https://forums.swift.org/t/a-roadmap-for-improving-swift-performance-predictability-arc-improvements-and-ownership-control/54206).

The introduction of ownership control (e.g. support for `~Copyable` types, strictly distinguishing between borrowing and consuming use) is a _major_ language development; it requires us to dismantle Swift's pre-existing container concepts and to reassemble them from scratch, targeting these new features. (The current `Sequence`/`Collection` protocols will survive, of course, but I expect they will remain limited to high level (copyable) use cases.)

All existing data structure implementations will need to be extensively redone to support this work -- in the short term, I expect our hands will be quite full with designing and implementing a multitude of new variants of the existing container types, inside and outside the stdlib.

I expect work on finalizing ropes (and adding new data structure implementations) in swift-collections will resume once the dust has settled on these lower-level issues.
