Can you consider adding persistent vector data-structure?

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.

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

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.

6 Likes

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

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?

2 Likes

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.

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.

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.

9 Likes