fixed-capacity-vec

Crates.iofixed-capacity-vec
lib.rsfixed-capacity-vec
version1.0.1
sourcesrc
created_at2023-08-30 16:53:38.124089
updated_at2023-09-14 15:40:21.074577
descriptionVariable-length buffer backed by a fixed-size heap array
homepage
repositoryhttps://gitlab.torproject.org/tpo/core/rust-fixed-capacity-vec.git/
max_upload_size
id959116
size43,383
Gabi Moldovan (gabi-250)

documentation

README

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-----------+        +---------------+
Commit count: 0

cargo fmt