This crate contains three fixed size low level array like data structures, primarily intended for use in immutable.rs, but fully supported as a standalone crate.
Their sizing information is encoded in the type using the
typenum crate, which you may want to take a look at before
reading on, but usually all you need to know about it is that it provides
U128 to represent numbers, which the data types take as type
SparseChunk<A, U32> would give you a sparse array with
room for 32 elements of type
A. You can also omit the size, as they all
default to a size of 64, so
SparseChunk<A> would be a sparse array with a
capacity of 64.
All data structures always allocate the same amount of space, as determined by their capacity, regardless of how many elements they contain, and when they run out of space, they will panic.
| Type | Description | Push | Pop | Deref to
| --- | --- | --- | --- | --- |
Chunk | Contiguous array | O(1)/O(n) | O(1) | Yes |
RingBuffer | Non-contiguous array | O(1) | O(1) | No |
SparseChunk | Sparse array | N/A | N/A | No |
RingBuffer are very similar in
practice, in that they both work like a plain array, except that you can
push to either end with some expectation of performance. The difference is
RingBuffer always allows you to do this in constant
time, but in order to give that guarantee, it doesn't lay out its elements
contiguously in memory, which means that you can't dereference it to a slice
Chunk, on the other hand, will shift its contents around when
necessary to accommodate a push to a full side, but is able to guarantee a
contiguous memory layout in this way, so it can always be dereferenced into
a slice. Performance wise, repeated pushes to the same side will always run
in constant time, but a push to one side followed by a push to the other
side will cause the latter to run in linear time if there's no room (which
there would only be if you've popped from that side).
To choose between them, you can use the following rules:
- I only ever want to push to the back: you don't need this crate, try
- I need to push to either side but probably not both on the same array: use
- I need to push to both sides and I don't need slices: use
- I need to push to both sides but I do need slices: use
SparseChunk is a more efficient version of
Vec<Option<A>>: each index is either inhabited or not, but instead of
Option discriminant to decide which is which, it uses a compact
bitmap. You can also think of
SparseChunk<A, N> as a
usize must be less than
N, but without the performance
overhead. Its API is also more consistent with a map than an array - there's
no push, pop, append, etc, just insert, remove and lookup.
A fixed capacity array sized to match some other type
A fixed capacity ring buffer.
A fixed capacity smart array.
A fixed capacity sparse array.
Helper types for chunks.