Expand description
A persistent vector.
This is a sequence of elements in insertion order - if you need a list of things, any kind of list of things, this is what you’re looking for.
It’s implemented as an RRB vector with smart
head/tail chunking. In performance terms, this means
that practically every operation is O(log n), except push/pop on
both sides, which will be O(1) amortised, and O(log n) in the
worst case. In practice, the push/pop operations will be
blindingly fast, nearly on par with the native
VecDeque, and other operations will have decent, if
not high, performance, but they all have more or less the same
O(log n) complexity, so you don’t need to keep their performance
characteristics in mind - everything, even splitting and merging,
is safe to use and never too slow.
§Performance Notes
Because of the head/tail chunking technique, until you push a
number of items above double the tree’s branching factor (that’s
self.len() = 2 × k (where k = 64) = 128) on either side, the
data structure is still just a handful of arrays, not yet an RRB
tree, so you’ll see performance and memory characteristics fairly
close to Vec or VecDeque.
This means that the structure always preallocates four chunks of
size k (k being the tree’s branching factor), equivalent to a
Vec with an initial capacity of 256. Beyond that, it will
allocate tree nodes of capacity k as needed.
In addition, vectors start out as single chunks, and only expand into the
full data structure once you go past the chunk size. This makes them
perform identically to Vec at small sizes.
Structs§
- An iterator over the leaf nodes of a vector.
- A mutable iterator over the leaf nodes of a vector.
- A consuming iterator over vectors with values of type
A. - An iterator over vectors with values of type
A. - A mutable iterator over vectors with values of type
A. - A memory pool for
Vector. - A persistent vector.