4 releases (2 stable)
| 1.0.1 | Sep 14, 2023 |
|---|---|
| 1.0.0 | Sep 13, 2023 |
| 0.1.0 | Sep 1, 2023 |
| 0.0.1 | Aug 30, 2023 |
#114 in Data structures
800,197 downloads per month
Used in 56 crates
(via hashx)
25KB
420 lines
FixedCapacityVec - like a Vec but with capacity fixed at compile-time
FixedCapacityVec is a simple special-purpose data structure.
One use case is applications which want to incrementally construct
a nontrivial fixed-size table.
Relationship to types from std
All of the following types store only the actual buffer on the heap, and they are interconvertible without copying the data.
| Type | Size and representation (as eg on stack) | Full? | Mutability |
|---|---|---|---|
Vec |
3 words: pointer, length, capacity | maybe | indefinitely appendable |
Box<[T]> |
2 words: pointer, length = capacity | always | length fixed at runtime |
FixedCapacityVec<T, N> |
2 words: pointer, length | maybe | appendable, but capacity fixed at compile time |
Box<[T; N]> |
1 word: pointer | always | length fixed at compile time |
Vec<T> HEAP Box<[T]> HEAP
+----------+ +------------+ +----------+ +----------+
| pointer -----> | T | | pointer -----> | T |
| length | | T ... | | length | | T ... |
| capacity | +--length----+ +----------+ +--length--+
+----------+ | (spare) |
+--capacity--+
FixedCapacityVec<T, N> HEAP Box<[T; N]> HEAP
+----------+ +-------------+ +----------+ +---------+
| pointer -----> | T | | pointer -----> | T |
| length | | T ... | +----------+ | T ... |
+----------+ |--length-----| +--N------+
| (spare) |
+--N----------|
Relationship to some other crates' vec-like types
FixedCapacityVec serves a different purpose to
ArrayVec
and
SmallVec.
The data for a FixedCapacityVec always lives on the heap.
The advantage of a FixedCapacityVec over Vec is that the size
of the FixedCapacityVec itself is small,
and that the capacity does not need to be represented or looked up.
And it can be converted very cheaply to a boxed array,
or to a Vec or boxed slice,
without copying.
ArrayVec is also a fixed-capacity vec-like structure.
But the data for an ArrayVec lives next to the metadata.
So to convert a full ArrayVec to a boxed array,
the data must be copied.
Even if it was a full Box<ArrayVec<..>>,
at the very least, its allocation would have to be shrunk.
One of ArrayVec's use cases is its ability to
incrementally construct (usually short) arrays without heap allocation.
SmallVec's benefit is that a small amount of data can be stored on the stack,
not that the SmallVec itself is particularly small;
indeed, both the ArrayVec and SmallVec are big enough for N items T.
ArrayVec<T, N> SmallVec<[T; N]> SmallVec<[T; N]>
+-----------+ +--------------+ +---------------+ HEAP
| T | | length <= N | | capacity > N | +------------+
| T ... | +--0-----------+ | pointer ----------> | T |
+--length---+ | T | OR | length | | T ... |
| (uninit) | | T ... | +---------------+ +--length----+
+--N--------+ |--length------| | (unused) | | (uninit) |
| length | | (spare) | | | +--capacity--+
+-----------+ +--N-----------+ +---------------+