Skip to main content

Module std::vector

A variable-sized container that can hold any type. Indexing is 0-based, and vectors are growable. This module has many native functions.

Constants

The index into the vector is out of bounds

const EINDEX_OUT_OF_BOUNDS: u64 = 131072;

Function `empty`

Create an empty vector. 
public fun empty<Element>(): vector<Element>
Implementation 
public native fun empty<Element>(): vector<Element>;

Function `length`

Return the length of the vector. 
public fun length<Element>(v: &vector<Element>): u64
Implementation 
public native fun length<Element>(v: &vector<Element>): u64;

Function `borrow`

Acquire an immutable reference to the ith element of the vector v. Aborts if i is out of bounds. 
public fun borrow<Element>(v: &vector<Element>, i: u64): &Element
Implementation 
public native fun borrow<Element>(v: &vector<Element>, i: u64): ∈

Function `push_back`

Add element e to the end of the vector v. 
public fun push_back<Element>(v: &mut vector<Element>, e: Element)
Implementation 
public native fun push_back<Element>(v: &mut vector<Element>, e: Element);

Function `borrow_mut`

Return a mutable reference to the ith element in the vector v. Aborts if i is out of bounds. 
public fun borrow_mut<Element>(v: &mut vector<Element>, i: u64): &mut Element
Implementation 
public native fun borrow_mut<Element>(v: &mut vector<Element>, i: u64): &mut Element;

Function `pop_back`

Pop an element from the end of vector v. Aborts if v is empty. 
public fun pop_back<Element>(v: &mut vector<Element>): Element
Implementation 
public native fun pop_back<Element>(v: &mut vector<Element>): Element;

Function `destroy_empty`

Destroy the vector v. Aborts if v is not empty. 
public fun destroy_empty<Element>(v: vector<Element>)
Implementation 
public native fun destroy_empty<Element>(v: vector<Element>);

Function `swap`

Swaps the elements at the ith and jth indices in the vector v. Aborts if i or j is out of bounds. 
public fun swap<Element>(v: &mut vector<Element>, i: u64, j: u64)
Implementation 
public native fun swap<Element>(v: &mut vector<Element>, i: u64, j: u64);

Function `singleton`

Return an vector of size one containing element e. 
public fun singleton<Element>(e: Element): vector<Element>
Implementation 
public fun singleton<Element>(e: Element): vector<Element> {
    let mut v = empty();
    v.push_back(e);
    v
}

Function `reverse`

Reverses the order of the elements in the vector v in place. 
public fun reverse<Element>(v: &mut vector<Element>)
Implementation 
public fun reverse<Element>(v: &mut vector<Element>) {
    let len = v.length();
    if (len == 0) return;
    let mut front_index = 0;
    let mut back_index = len - 1;
    while (front_index < back_index) {
        v.swap(front_index, back_index);
        front_index = front_index + 1;
        back_index = back_index - 1;
    }
}

Function `append`

Pushes all of the elements of the other vector into the lhs vector. 
public fun append<Element>(lhs: &mut vector<Element>, other: vector<Element>)
Implementation 
public fun append<Element>(lhs: &mut vector<Element>, other: vector<Element>) {
    other.do!(|e| lhs.push_back(e));
}

Function `is_empty`

Return true if the vector v has no elements and false otherwise. 
public fun is_empty<Element>(v: &vector<Element>): bool
Implementation 
public fun is_empty<Element>(v: &vector<Element>): bool {
    v.length() == 0
}

Function `contains`

Return true if e is in the vector v. Otherwise, returns false. 
public fun contains<Element>(v: &vector<Element>, e: &Element): bool
Implementation 
public fun contains<Element>(v: &vector<Element>, e: &Element): bool {
    let mut i = 0;
    let len = v.length();
    while (i < len) {
        if (&v[i] == e) return true;
        i = i + 1;
    };
    false
}

Function `index_of`

Return (true, i) if e is in the vector v at index i. Otherwise, returns (false, 0). 
public fun index_of<Element>(v: &vector<Element>, e: &Element): (bool, u64)
Implementation 
public fun index_of<Element>(v: &vector<Element>, e: &Element): (bool, u64) {
    let mut i = 0;
    let len = v.length();
    while (i < len) {
        if (&v[i] == e) return (true, i);
        i = i + 1;
    };
    (false, 0)
}

Function `remove`

Remove the ith element of the vector v, shifting all subsequent elements. This is O(n) and preserves ordering of elements in the vector. Aborts if i is out of bounds. 
public fun remove<Element>(v: &mut vector<Element>, i: u64): Element
Implementation 
public fun remove<Element>(v: &mut vector<Element>, mut i: u64): Element {
    let mut len = v.length();
    // i out of bounds; abort
    if (i >= len) abort EINDEX_OUT_OF_BOUNDS;
    len = len - 1;
    while (i < len) {
        v.swap(i, { i = i + 1; i });
    };
    v.pop_back()
}

Function `insert`

Insert e at position i in the vector v. If i is in bounds, this shifts the old v[i] and all subsequent elements to the right. If i == v.length(), this adds e to the end of the vector. This is O(n) and preserves ordering of elements in the vector. Aborts if i > v.length() 
public fun insert<Element>(v: &mut vector<Element>, e: Element, i: u64)
Implementation 
public fun insert<Element>(v: &mut vector<Element>, e: Element, mut i: u64) {
    let len = v.length();
    // i too big abort
    if (i > len) abort EINDEX_OUT_OF_BOUNDS;
    v.push_back(e);
    while (i < len) {
        v.swap(i, len);
        i = i + 1
    }
}

Function `swap_remove`

Swap the ith element of the vector v with the last element and then pop the vector. This is O(1), but does not preserve ordering of elements in the vector. Aborts if i is out of bounds. 
public fun swap_remove<Element>(v: &mut vector<Element>, i: u64): Element
Implementation 
public fun swap_remove<Element>(v: &mut vector<Element>, i: u64): Element {
    assert!(v.length() != 0, EINDEX_OUT_OF_BOUNDS);
    let last_idx = v.length() - 1;
    v.swap(i, last_idx);
    v.pop_back()
}

Function `skip`

Return a new vector containing the elements of v except the first n elements. If n > length, returns an empty vector. 
public fun skip<T: drop>(v: vector<T>, n: u64): vector<T>
Implementation 
public fun skip<T: drop>(mut v: vector<T>, n: u64): vector<T> {
    let len = v.length();
    if (n >= len) return vector[];
    let mut r = tabulate!(len - n, |_| v.pop_back());
    r.reverse();
    r
}

Function `take`

Take the first n elements of the vector v and drop the rest. Aborts if n is greater than the length of v. 
public fun take<T: drop>(v: vector<T>, n: u64): vector<T>
Implementation 
public fun take<T: drop>(mut v: vector<T>, n: u64): vector<T> {
    assert!(n <= v.length());
    if (n == v.length()) return v;
    v.reverse();
    tabulate!(n, |_| v.pop_back())
}

Macro function `tabulate`

Create a vector of length n by calling the function f on each index. 
public macro fun tabulate<$T>($n: u64, $f: |u64| -> $T): vector<$T>
Implementation 
public macro fun tabulate<$T>($n: u64, $f: |u64| -> $T): vector<$T> {
    let mut v = vector[];
    let n = $n;
    n.do!(|i| v.push_back($f(i)));
    v
}

Macro function `destroy`

Destroy the vector v by calling f on each element and then destroying the vector. Does not preserve the order of elements in the vector (starts from the end of the vector). 
public macro fun destroy<$T, $R: drop>($v: vector<$T>, $f: |$T| -> $R)
Implementation 
public macro fun destroy<$T, $R: drop>($v: vector<$T>, $f: |$T| -> $R) {
    let mut v = $v;
    v.length().do!(|_| $f(v.pop_back()));
    v.destroy_empty();
}

Macro function `do`

Destroy the vector v by calling f on each element and then destroying the vector. Preserves the order of elements in the vector. 
public macro fun do<$T, $R: drop>($v: vector<$T>, $f: |$T| -> $R)
Implementation 
public macro fun do<$T, $R: drop>($v: vector<$T>, $f: |$T| -> $R) {
    let mut v = $v;
    v.reverse();
    v.length().do!(|_| $f(v.pop_back()));
    v.destroy_empty();
}

Macro function `do_ref`

Perform an action f on each element of the vector v. The vector is not modified. 
public macro fun do_ref<$T, $R: drop>($v: &vector<$T>, $f: |&$T| -> $R)
Implementation 
public macro fun do_ref<$T, $R: drop>($v: &vector<$T>, $f: |&$T| -> $R) {
    let v = $v;
    v.length().do!(|i| $f(&v[i]))
}

Macro function `do_mut`

Perform an action f on each element of the vector v. The function f takes a mutable reference to the element. 
public macro fun do_mut<$T, $R: drop>($v: &mut vector<$T>, $f: |&mut $T| -> $R)
Implementation 
public macro fun do_mut<$T, $R: drop>($v: &mut vector<$T>, $f: |&mut $T| -> $R) {
    let v = $v;
    v.length().do!(|i| $f(&mut v[i]))
}

Macro function `map`

Map the vector v to a new vector by applying the function f to each element. Preserves the order of elements in the vector, first is called first. 
public macro fun map<$T, $U>($v: vector<$T>, $f: |$T| -> $U): vector<$U>
Implementation 
public macro fun map<$T, $U>($v: vector<$T>, $f: |$T| -> $U): vector<$U> {
    let v = $v;
    let mut r = vector[];
    v.do!(|e| r.push_back($f(e)));
    r
}

Macro function `map_ref`

Map the vector v to a new vector by applying the function f to each element. Preserves the order of elements in the vector, first is called first. 
public macro fun map_ref<$T, $U>($v: &vector<$T>, $f: |&$T| -> $U): vector<$U>
Implementation 
public macro fun map_ref<$T, $U>($v: &vector<$T>, $f: |&$T| -> $U): vector<$U> {
    let v = $v;
    let mut r = vector[];
    v.do_ref!(|e| r.push_back($f(e)));
    r
}

Macro function `filter`

Filter the vector v by applying the function f to each element. Return a new vector containing only the elements for which f returns true. 
public macro fun filter<$T: drop>($v: vector<$T>, $f: |&$T| -> bool): vector<$T>
Implementation 
public macro fun filter<$T: drop>($v: vector<$T>, $f: |&$T| -> bool): vector<$T> {
    let v = $v;
    let mut r = vector[];
    v.do!(|e| if ($f(&e)) r.push_back(e));
    r
}

Macro function `partition`

Split the vector v into two vectors by applying the function f to each element. Return a tuple containing two vectors: the first containing the elements for which f returns true, and the second containing the elements for which f returns false. 
public macro fun partition<$T>($v: vector<$T>, $f: |&$T| -> bool): (vector<$T>, vector<$T>)
Implementation 
public macro fun partition<$T>($v: vector<$T>, $f: |&$T| -> bool): (vector<$T>, vector<$T>) {
    let v = $v;
    let mut r1 = vector[];
    let mut r2 = vector[];
    v.do!(|e| if ($f(&e)) r1.push_back(e) else r2.push_back(e));
    (r1, r2)
}

Macro function `find_index`

Finds the index of first element in the vector v that satisfies the predicate f. Returns some(index) if such an element is found, otherwise none(). 
public macro fun find_index<$T>($v: &vector<$T>, $f: |&$T| -> bool): std::option::Option<u64>
Implementation 
public macro fun find_index<$T>($v: &vector<$T>, $f: |&$T| -> bool): Option<u64> {
    let v = $v;
    'find_index: {
        v.length().do!(|i| if ($f(&v[i])) return 'find_index option::some(i));
        option::none()
    }
}

Macro function `find_indices`

Finds all indices of elements in the vector v that satisfy the predicate f. Returns a vector of indices of all found elements. 
public macro fun find_indices<$T>($v: &vector<$T>, $f: |&$T| -> bool): vector<u64>
Implementation 
public macro fun find_indices<$T>($v: &vector<$T>, $f: |&$T| -> bool): vector<u64> {
    let v = $v;
    let mut indices = vector[];
    v.length().do!(|i| if ($f(&v[i])) indices.push_back(i));
    indices
}

Macro function `count`

Count how many elements in the vector v satisfy the predicate f. 
public macro fun count<$T>($v: &vector<$T>, $f: |&$T| -> bool): u64
Implementation 
public macro fun count<$T>($v: &vector<$T>, $f: |&$T| -> bool): u64 {
    let v = $v;
    let mut count = 0;
    v.do_ref!(|e| if ($f(e)) count = count + 1);
    count
}

Macro function `fold`

Reduce the vector v to a single value by applying the function f to each element. Similar to fold_left in Rust and reduce in Python and JavaScript. 
public macro fun fold<$T, $Acc>($v: vector<$T>, $init: $Acc, $f: |$Acc, $T| -> $Acc): $Acc
Implementation 
public macro fun fold<$T, $Acc>($v: vector<$T>, $init: $Acc, $f: |$Acc, $T| -> $Acc): $Acc {
    let v = $v;
    let mut acc = $init;
    v.do!(|e| acc = $f(acc, e));
    acc
}

Function `flatten`

Concatenate the vectors of v into a single vector, keeping the order of the elements. 
public fun flatten<T>(v: vector<vector<T>>): vector<T>
Implementation 
public fun flatten<T>(v: vector<vector<T>>): vector<T> {
    let mut r = vector[];
    v.do!(|u| r.append(u));
    r
}

Macro function `any`

Whether any element in the vector v satisfies the predicate f. If the vector is empty, returns false. 
public macro fun any<$T>($v: &vector<$T>, $f: |&$T| -> bool): bool
Implementation 
public macro fun any<$T>($v: &vector<$T>, $f: |&$T| -> bool): bool {
    let v = $v;
    'any: {
        v.do_ref!(|e| if ($f(e)) return 'any true);
        false
    }
}

Macro function `all`

Whether all elements in the vector v satisfy the predicate f. If the vector is empty, returns true. 
public macro fun all<$T>($v: &vector<$T>, $f: |&$T| -> bool): bool
Implementation 
public macro fun all<$T>($v: &vector<$T>, $f: |&$T| -> bool): bool {
    let v = $v;
    'all: {
        v.do_ref!(|e| if (!$f(e)) return 'all false);
        true
    }
}

Macro function `zip_do`

Destroys two vectors v1 and v2 by calling f to each pair of elements. Aborts if the vectors are not of the same length. The order of elements in the vectors is preserved. 
public macro fun zip_do<$T1, $T2, $R: drop>($v1: vector<$T1>, $v2: vector<$T2>, $f: |$T1, $T2| -> $R)
Implementation 
public macro fun zip_do<$T1, $T2, $R: drop>(
    $v1: vector<$T1>,
    $v2: vector<$T2>,
    $f: |$T1, $T2| -> $R,
) {
    let v1 = $v1;
    let mut v2 = $v2;
    v2.reverse();
    let len = v1.length();
    assert!(len == v2.length());
    v1.do!(|el1| $f(el1, v2.pop_back()));
    v2.destroy_empty();
}

Macro function `zip_do_reverse`

Destroys two vectors v1 and v2 by calling f to each pair of elements. Aborts if the vectors are not of the same length. Starts from the end of the vectors. 
public macro fun zip_do_reverse<$T1, $T2, $R: drop>($v1: vector<$T1>, $v2: vector<$T2>, $f: |$T1, $T2| -> $R)
Implementation 
public macro fun zip_do_reverse<$T1, $T2, $R: drop>(
    $v1: vector<$T1>,
    $v2: vector<$T2>,
    $f: |$T1, $T2| -> $R,
) {
    let v1 = $v1;
    let mut v2 = $v2;
    let len = v1.length();
    assert!(len == v2.length());
    v1.destroy!(|el1| $f(el1, v2.pop_back()));
}

Macro function `zip_do_ref`

Iterate through v1 and v2 and apply the function f to references of each pair of elements. The vectors are not modified. Aborts if the vectors are not of the same length. The order of elements in the vectors is preserved. 
public macro fun zip_do_ref<$T1, $T2, $R: drop>($v1: &vector<$T1>, $v2: &vector<$T2>, $f: |&$T1, &$T2| -> $R)
Implementation 
public macro fun zip_do_ref<$T1, $T2, $R: drop>(
    $v1: &vector<$T1>,
    $v2: &vector<$T2>,
    $f: |&$T1, &$T2| -> $R,
) {
    let v1 = $v1;
    let v2 = $v2;
    let len = v1.length();
    assert!(len == v2.length());
    len.do!(|i| $f(&v1[i], &v2[i]));
}

Macro function `zip_do_mut`

Iterate through v1 and v2 and apply the function f to mutable references of each pair of elements. The vectors may be modified. Aborts if the vectors are not of the same length. The order of elements in the vectors is preserved. 
public macro fun zip_do_mut<$T1, $T2, $R: drop>($v1: &mut vector<$T1>, $v2: &mut vector<$T2>, $f: |&mut $T1, &mut $T2| -> $R)
Implementation 
public macro fun zip_do_mut<$T1, $T2, $R: drop>(
    $v1: &mut vector<$T1>,
    $v2: &mut vector<$T2>,
    $f: |&mut $T1, &mut $T2| -> $R,
) {
    let v1 = $v1;
    let v2 = $v2;
    let len = v1.length();
    assert!(len == v2.length());
    len.do!(|i| $f(&mut v1[i], &mut v2[i]));
}

Macro function `zip_map`

Destroys two vectors v1 and v2 by applying the function f to each pair of elements. The returned values are collected into a new vector. Aborts if the vectors are not of the same length. The order of elements in the vectors is preserved. 
public macro fun zip_map<$T1, $T2, $U>($v1: vector<$T1>, $v2: vector<$T2>, $f: |$T1, $T2| -> $U): vector<$U>
Implementation 
public macro fun zip_map<$T1, $T2, $U>(
    $v1: vector<$T1>,
    $v2: vector<$T2>,
    $f: |$T1, $T2| -> $U,
): vector<$U> {
    let mut r = vector[];
    zip_do!($v1, $v2, |el1, el2| r.push_back($f(el1, el2)));
    r
}

Macro function `zip_map_ref`

Iterate through v1 and v2 and apply the function f to references of each pair of elements. The returned values are collected into a new vector. Aborts if the vectors are not of the same length. The order of elements in the vectors is preserved. 
public macro fun zip_map_ref<$T1, $T2, $U>($v1: &vector<$T1>, $v2: &vector<$T2>, $f: |&$T1, &$T2| -> $U): vector<$U>
Implementation 
public macro fun zip_map_ref<$T1, $T2, $U>(
    $v1: &vector<$T1>,
    $v2: &vector<$T2>,
    $f: |&$T1, &$T2| -> $U,
): vector<$U> {
    let mut r = vector[];
    zip_do_ref!($v1, $v2, |el1, el2| r.push_back($f(el1, el2)));
    r
}

Macro function `insertion_sort_by`

Performs an in-place insertion sort on the vector v using the comparison function le. The sort is stable, meaning that equal elements will maintain their relative order.

Please, note that the comparison function le expects less or equal, not less.

Example:

let mut v = vector[2, 1, 3];
v.insertion_sort_by(|a, b| a <= b);
assert!(v == vector[1, 2, 3]);

Insertion sort is efficient for small vectors (~30 or less elements), and can be faster than merge sort for almost sorted vectors (e.g. when the vector is already sorted or nearly sorted).

public macro fun insertion_sort_by<$T>($v: &mut vector<$T>, $le: |&$T, &$T| -> bool)
Implementation 
public macro fun insertion_sort_by<$T>($v: &mut vector<$T>, $le: |&$T, &$T| -> bool) {
    let v = $v;
    let n = v.length();
    if (n < 2) return;
    // do insertion sort
    let mut i = 1;
    while (i < n) {
        let mut j = i;
        while (j > 0 && !$le(&v[j - 1], &v[j])) {
            v.swap(j, j - 1);
            j = j - 1;
        };
        i = i + 1;
    }
}

Macro function `merge_sort_by`

Performs an in-place merge sort on the vector v using the comparison function le. Merge sort is efficient for large vectors, and is a stable sort.

Please, note that the comparison function le expects less or equal, not less.

Example:

let mut v = vector[2, 1, 3];
v.merge_sort_by(|a, b| a <= b);
assert!(v == vector[1, 2, 3]);

Merge sort performs better than insertion sort for large vectors (~30 elements or more).

public macro fun merge_sort_by<$T>($v: &mut vector<$T>, $le: |&$T, &$T| -> bool)
Implementation 
public macro fun merge_sort_by<$T>($v: &mut vector<$T>, $le: |&$T, &$T| -> bool) {
    let v = $v;
    let n = v.length();
    if (n < 2) return;
    let mut flags = vector[false];
    let mut starts = vector[0];
    let mut ends = vector[n];
    while (!flags.is_empty()) {
        let (halves_sorted, start, end) = (flags.pop_back(), starts.pop_back(), ends.pop_back());
        let mid = (start + end) / 2;
        if (halves_sorted) {
            let mut mid = mid;
            let mut l = start;
            let mut r = mid;
            while (l < mid && r < end) {
                if ($le(&v[l], &v[r])) {
                    l = l + 1;
                } else {
                    let mut i = r;
                    while (i > l) {
                        v.swap(i, i - 1);
                        i = i - 1;
                    };
                    l = l + 1;
                    mid = mid + 1;
                    r = r + 1;
                }
            }
        } else {
            // set up the "merge"
            flags.push_back(true);
            starts.push_back(start);
            ends.push_back(end);
            // set up the recursive calls
            // v[start..mid]
            if (mid - start > 1) {
                flags.push_back(false);
                starts.push_back(start);
                ends.push_back(mid);
            };
            // v[mid..end]
            if (end - mid > 1) {
                flags.push_back(false);
                starts.push_back(mid);
                ends.push_back(end);
            }
        }
    }
}

Macro function `is_sorted_by`

Check if the vector v is sorted in non-decreasing order according to the comparison function le (les). Returns true if the vector is sorted, false otherwise. 
public macro fun is_sorted_by<$T>($v: &vector<$T>, $le: |&$T, &$T| -> bool): bool
Implementation 
public macro fun is_sorted_by<$T>($v: &vector<$T>, $le: |&$T, &$T| -> bool): bool {
    let v = $v;
    let n_minus_1 = v.length().max(1) - 1;
    'is_sorted_by: {
        n_minus_1.do!(|i| if (!$le(&v[i], &v[i + 1])) return 'is_sorted_by false);
        true
    }
}

Macro function `take_while`

Return a new vector containing the elements of v except the first n elements that satisfy the predicate p. If all elements satisfy the predicate, returns an empty vector. 
public macro fun take_while<$T: drop>($v: vector<$T>, $p: |&$T| -> bool): vector<$T>
Implementation 
public macro fun take_while<$T: drop>($v: vector<$T>, $p: |&$T| -> bool): vector<$T> {
    let v = $v;
    'take: {
        let mut r = vector[];
        v.do!(|e| if ($p(&e)) r.push_back(e) else return 'take r);
        r
    }
}

Macro function `skip_while`

Take all elements of the vector v except the first n elements that satisfy the predicate p and drop the rest, where n <= v.length(). 
public macro fun skip_while<$T: drop>($v: vector<$T>, $p: |&$T| -> bool): vector<$T>
Implementation 
public macro fun skip_while<$T: drop>($v: vector<$T>, $p: |&$T| -> bool): vector<$T> {
    let mut v = $v;
    v.reverse();
    let mut i = v.length();
    while (i > 0) {
        i = i - 1;
        if ($p(&v[i])) v.pop_back() else break;
    };
    v.reverse();
    v
}