Vector

An inline array has the length its type says, fixed while compiling. Most real data is not like that: lines read from a file, results that pass a test, orders placed today. You do not know how many there will be until they arrive.

The Memory lessons solved that by hand — ask an allocator for a block, keep count, ask for a larger block when it is full. A Vector<T>, from the Collections package, does that bookkeeping for you. It owns a block, hands out room as values are pushed, and moves to a larger block when the current one is full. It is the container you will reach for most often.

Making a vector

A vector keeps its values somewhere, so it is given an allocator when it is made:

var system = SystemAllocator();
let allocator: Allocator = system;

var numbers = Vector<int>(allocator);

Vector<int> is a generic type: a vector of int. Making one asks the allocator for nothing yet — an empty vector has no block, and a capacity of zero. The binding is a var, because pushing changes the vector.

Length and capacity

Two numbers describe a vector, and they are worth keeping apart:

Pushing raises the length by one every time; the capacity only jumps now and then. The program pushes nine values and prints a line whenever the capacity changes:

for i in 1..=9 {
    let before = numbers.Capacity();
    numbers.Push(i * 10)?;
    if numbers.Capacity() != before {
        PrintLine("push {}      length {}  capacity {}  (grew)", i, numbers.Length(),
            numbers.Capacity());
    }
}

push 1      length 1  capacity 4  (grew)
push 5      length 5  capacity 8  (grew)
push 9      length 9  capacity 16  (grew)

Nine pushes, three moves. The capacity grows ahead of the length on purpose: each time the vector moves it takes twice the room, so the pushes that follow cost nothing. The vector moves house a handful of times, not once per value.

flowchart LR
    push["Push(value)"] --> room{"Is length below<br/>capacity?"}
    room -- "yes" --> write["Write the value<br/>into the next slot"]
    room -- "no" --> grow["Ask the allocator<br/>for a larger block"]
    grow --> copy["Move the values across,<br/>give the old block back"]
    copy --> write
    grow -- "no memory" --> fail["Push fails with<br/>CollectionError"]

Pushing can fail

That last arrow is why Push returns ! CollectionError: a push may need a larger block, and the allocator may have none to give. The ? hands that failure on to Main, which is declared fallible for exactly this reason:

func Main() -> ! CollectionError {

A failed push leaves the vector exactly as it was — no value half-added.

Reserving room up front

When the final size is known, Reserve makes the room in one step:

numbers.Reserve(100)?;

At least 100 more values will now fit, so the pushes that follow never need to grow. The program prints a capacity of 128: the vector rounded the request up.

Reading the values

A vector is a container a for loop can walk, in the order the values went in:

for value in numbers {
    Print(" {}", value);
}

To read one value, use Get. It is bounds-checked: it returns int?, an optional, with none past the end:

PrintLine("index 2     {}", numbers.Get(2) ?? -1);
PrintLine("index 50    {}", numbers.Get(50) ?? -1);

Index 2 is 30; index 50 does not exist, and the ?? fallback gives -1.

Nothing in the program frees anything. The vector's destructor gives its block back to the allocator when numbers goes out of scope.

The program

The whole lesson is one package in the Examples repository. Its comments explain every step.

// The Memory lessons asked for a block of a fixed size and kept count by hand. A `Vector<T>` does
// that bookkeeping for you: it owns a block, hands out room as values are pushed, and moves to a
// larger block when the current one is full.
//
// Two numbers describe a vector, and they are worth keeping apart. Its length is how many values
// it holds. Its capacity is how many would fit before it needs a larger block. Pushing raises the
// length by one every time; the capacity only jumps now and then.
import Allocator::{ Allocator, SystemAllocator };
import Collections::{ CollectionError, Vector };
import Io::{ Print, PrintLine };

func Main() -> ! CollectionError {
    var system = SystemAllocator();
    let allocator: Allocator = system;

    // A vector keeps its storage somewhere, so it is given an allocator. Making one asks for
    // nothing yet: an empty vector has a capacity of zero.
    var numbers = Vector<int>(allocator);
    PrintLine("empty       length {}  capacity {}", numbers.Length(), numbers.Capacity());

    // A push may need a larger block, and the allocator may have none to give, so `Push`
    // returns `! CollectionError`. The `?` hands that failure to `Main`.
    for i in 1..=9 {
        let before = numbers.Capacity();
        numbers.Push(i * 10)?;
        if numbers.Capacity() != before {
            PrintLine("push {}      length {}  capacity {}  (grew)", i, numbers.Length(),
                numbers.Capacity());
        }
    }
    PrintLine("after 9     length {}  capacity {}", numbers.Length(), numbers.Capacity());

    // The capacity grows ahead of the length on purpose. Taking more room than needed means the
    // next pushes cost nothing, so the vector moves house a handful of times, not once a value.

    // When the final size is known up front, `Reserve` makes the room in one step: at least 100
    // more values will now fit, so the pushes that follow never need to grow.
    numbers.Reserve(100)?;
    PrintLine("reserved    length {}  capacity {}", numbers.Length(), numbers.Capacity());

    // A vector is a container a `for` loop can walk, in the order the values went in.
    Print("contents   ");
    for value in numbers {
        Print(" {}", value);
    }
    PrintLine();

    // `Get` is bounds-checked: it returns `int?`, and `none` past the end.
    PrintLine("index 2     {}", numbers.Get(2) ?? -1);
    PrintLine("index 50    {}", numbers.Get(50) ?? -1);

    // Nothing here frees anything. The vector's destructor gives its block back to the allocator
    // when `numbers` goes out of scope.
}

Besides Io, its Rux.toml lists Allocator and Collections under [Dependencies].

Run it

cd Examples/Collections/Vector
rux run

empty       length 0  capacity 0
push 1      length 1  capacity 4  (grew)
push 5      length 5  capacity 8  (grew)
push 9      length 9  capacity 16  (grew)
after 9     length 9  capacity 16
reserved    length 9  capacity 128
contents    10 20 30 40 50 60 70 80 90
index 2     30
index 50    -1

Common mistakes

Try it yourself

1. Push 1000 values and count how many times the capacity grew.
2. Make the vector with Vector::WithCapacity<int>(allocator, 100)? instead. What are its length and capacity before the first push?
3. Remove the first value with RemoveAt(0), which returns an optional, and print what is left.
4. Add up the values with a for loop, then again by indexing numbers.AsSlice().

Learn more

• Allocator — where a vector's block comes from
• Dynamic array — a run whose length is set at run time and never changes
• Deque — a vector that is quick at both ends
• Slices in the Rux Reference