fixed-capacity-vec 1.0.1

Variable-length buffer backed by a fixed-size heap array
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

# `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 |

```text
         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`](https://docs.rs/arrayvec/latest/arrayvec/struct.ArrayVec.html)
and
[`SmallVec`](https://docs.rs/smallvec/latest/smallvec/struct.SmallVec.html).

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`.

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