#vec #heap #variable-length #n #following-types #fixed-size #n-items #nontrivial-fixed #stack-full

fixed-capacity-vec

Variable-length buffer backed by a fixed-size heap array

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

Download history 560/week @ 2023-11-01 475/week @ 2023-11-08 945/week @ 2023-11-15 834/week @ 2023-11-22 918/week @ 2023-11-29 870/week @ 2023-12-06 642/week @ 2023-12-13 121/week @ 2023-12-20 182/week @ 2023-12-27 453/week @ 2024-01-03 896/week @ 2024-01-10 652/week @ 2024-01-17 992/week @ 2024-01-24 1017/week @ 2024-01-31 614/week @ 2024-02-07 473/week @ 2024-02-14

3,330 downloads per month
Used in 2 crates (via hashx)

MIT/Apache

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-----------+        +---------------+

No runtime deps

Features