Module im::vector[][src]

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 similar 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.

Structs

ConsumingIter

A consuming iterator over vectors with values of type A.

Iter

An iterator over vectors with values of type A.

IterMut

A mutable iterator over vectors with values of type A.

Vector

A persistent vector.