[−][src]Crate vec_array

This library provides VecArray, an array-like type that holds a number of values backed by a fixed-sized array for no-allocation, quick access. If more items than the array's capacity are stored, it automatically converts into using a Vec.

This crate similar to the staticvec crate but has different emphasis: e.g. it can grow beyond the array's capacity, and it compiles on stable.

Implementation

A VecArray holds data in either one of two storages:

  1. a fixed-size array of MAX_ARRAY_SIZE (defaults to 4) items, and
  2. a dynamic Vec with unlimited items.

At any time, either one of them (or both) must be empty, depending on the capacity of the array.

There is a len field containing the total number of items held by the VecArray.

The fixed-size array is not initialized (i.e. initialized with MaybeUninit::uninit()).

When len <= MAX_ARRAY_SIZE, all elements are stored in the fixed-size array. Array slots >= len are MaybeUninit::uninit() while slots < len are considered actual data. In this scenario, the Vec (more) is empty.

As soon as we try to push a new item into the VecArray that makes the total number exceed MAX_ARRAY_SIZE, all the items in the fixed-sized array are taken out, replaced with MaybeUninit::uninit() (via mem::replace) and pushed into the Vec. Then the new item is added to the Vec.

Therefore, if len > MAX_ARRAY_SIZE, then the fixed-size array is considered empty and uninitialized while all data resides in the Vec.

When popping an item off of the VecArray, the reverse is true. If len == MAX_ARRAY_SIZE + 1, after popping the item, all the items residing in the Vec are moved back to the fixed-size array. The Vec will then be empty.

Therefore, if len <= MAX_ARRAY_SIZE, data is in the fixed-size array. Otherwise, data is in the Vec.

Limitations

  1. The constant MAX_ARRAY_SIZE must be compiled in, at least until constant generics land in Rust. It defaults to 4, and you must clone this repo and change it to another number.

  2. It automatically converts itself into a Vec when over MAX_ARRAY_SIZE and back into an array when the number of items drops below this threshold. If it so happens that the data is constantly added and removed from the VecArray that straddles this threshold, you'll see excessive moving and copying of data back-and-forth, plus allocations and deallocations of the Vec.

Structs

VecArray

An array-like type that holds a number of values in static storage for no-allocation, quick access.

Constants

MAX_ARRAY_SIZE

Maximum slots of fixed-size storage for a VecArray. Defaults to 4, which should be enough for many cases and is a good balance between memory consumption (for the fixed-size array) and reduced allocations.