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 |
#163 in Data structures
3,330 downloads per month
Used in 2 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-----------+ +---------------+