Vec

Vec<T> is the growable, contiguous, owned sequence — the vector you reach for by default. import std.vec for literals and methods.

import std.io
import std.vec

fn main() -> Int {
    let scores: Vec<Int> = [70, 85]
    scores.push(92)
    scores.insert(0, 60)

    println(scores.length)      // 4
    println(scores.first)       // 60
    println(scores.last)        // 92
    println(scores.contains(85))
    return 0
}

The type was called List<T> before 0.1's collections work. That spelling is now an error that names Vec<T>; nothing else about the type changed.

Build one

The element type comes from what the literal is assigned to — an annotation, a struct field, a parameter. [1, 2] written as a Vec<I64> holds I64s.

A literal needs its elements to implement Copy (every scalar, String, and any struct that writes the impl), because each element is duplicated into the new Vec. Past twelve elements, push them.

Methods

v.name(args) is the call; properties are read without parentheses.

Size

Read

An index outside the Vec answers the element type's zero, not an error — 0 for an Int, "" for a String. Check length first, or use get, which says whether the element was there. last reads its receiver twice, so it has to be a name or a field of one; bind a call's result first.

Search

Requires T: Eq (from std.eq, which covers every scalar and String).

Change

push, insert and set move the value in: the name you pushed is no longer usable. pop, removeAt, get and extend hand out copies, so they need T: Copy.

import std.io
import std.vec
import std.option

fn main() -> Int {
    let queue: Vec<String> = ["build", "test"]
    queue.insert(0, "fetch")
    queue.push("ship")

    let next = queue.removeAt(0)
    println(next)                  // fetch

    let finished = queue.pop()
    match (finished) {
        Option.Some(task) => { println(task) }   // ship
        Option.None => { println("nothing left") }
    }

    queue.truncate(1)
    println(queue.length)          // 1
    return 0
}

An insert or removeAt index outside the Vec stops the program with a message naming the index and the length. A removal that did nothing would leave you holding a copy of an element you did not take.

Copy

Removing an element another name still reads

v[i] is a view of the element, not a copy, and nothing stops the Vec losing that element while the view is still in use:

import std.io
import std.vec

fn main() -> Int {
    let words: Vec<String> = ["a long enough string to own its own memory", "b"]
    let first = words[0]
    words.clear()
    println(first)       // still the string
    return 0
}

This is safe. A removed element that owns memory is released with the Vec, not at the removal, which releases exactly what the Vec would have released had the element stayed. So a removal can never free something a view still reads. Scalars and structs with no owned fields own nothing, so removing them holds nothing back.

The cost is that a long-lived Vec which keeps removing Strings keeps their memory until the Vec itself is released. Releasing at the removal when the compiler can prove no view exists is planned; see COLLECTIONS.md in the compiler repository.

Ownership

The Vec owns its elements and is itself move-only. Pushing moves the element in, so the pushed name cannot be used again:

import std.vec

struct Item { id: Int }

fn main() -> Int {
    let items: Vec<Item> = []
    let item = Item { id: 7 }
    items.push(item)
    return item.id
}

A Vec<T> parameter borrows the Vec, so the caller still owns it afterwards. inout borrows it mutably, and sink hands the whole Vec to the callee.

import std.vec

fn total(values: Vec<Int>) -> Int {
    let mut sum = 0
    for v in values {
        sum = sum + v
    }
    return sum
}

fn main() -> Int {
    let values: Vec<Int> = [1, 2, 3]
    return total(values) - 6
}

Storage follows the element type. Scalars, Strings and structs with no pointer-bearing fields live directly in the Vec's block; everything else is stored as one pointer per element. That choice is made when the program is compiled and changes nothing about how the Vec is used, and neither layout is a stable foreign ABI.

Sorting

Sorting needs an order, so it needs T: Ord — from std.ord, which covers every integer type, Char, Float and String.

import std.io
import std.vec

fn main() -> Int {
    let xs: Vec<Int> = [5, 1, 4]
    xs.sort()
    println(xs.first)              // 1
    println(xs.binarySearch(4))    // 1
    return 0
}

sort is pattern-defeating quicksort (pdqsort) and is not stable. Ranges under 24 elements go to insertion sort. The pivot is a median of three, or of nine above 128 elements. A range that keeps splitting badly is finished by heapsort, so the worst case is O(n log n) and recursion stays O(log n) deep whatever the input.

Ordered and repetitive input are fast, not just correct. A Vec already in order costs about one pass, and 10 000 equal values sort in linear time.

A struct sorts once it has an impl Ord:

import std.io
import std.vec
import std.ord

struct Version {
    major: Int,
    minor: Int
}

impl Ord for Version {
    fn cmp(self, other: Self) -> Int {
        if (self.major != other.major) { return cmp(self.major, other.major) }
        return cmp(self.minor, other.minor)
    }
}

fn main() -> Int {
    let older = Version { major: 1, minor: 9 }
    let newer = Version { major: 2, minor: 0 }
    println(cmp(older, newer))
    return 0
}

Float's order is not total. NaN compares as neither less nor greater, so cmp answers 0 for it. A sort over data containing NaN has an unspecified order rather than a corrupted one.

Higher-order

With closures:

import std.io
import std.vec

fn main() -> Int {
    let xs: Vec<Int> = [3, 9, 1]
    xs.sortBy(|a: Int, b: Int| b - a)
    println(xs.first)                              // 9

    let big = xs.filter(|v: Int| v > 2)
    println(big.length)                            // 2
    println(xs.countWhere(|v: Int| v % 2 == 1))    // 3
    return 0
}

mapInto takes its destination rather than returning one. A map that returned a Vec<U> would have to learn U from the closure's return type, and Prismio solves a type parameter from argument types only. With the destination as an argument, U is solvable.

The runtime layer

The list_* functions (list_new, list_push, list_len, …) are what the methods compile to, as the str_* functions are under String. They still work, and they are not the interface this page describes.