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>
Click to open
Implementation
public native fun empty<Element>(): vector<Element>;

Function length​

Return the length of the vector.

public fun length<Element>(v: &vector<Element>): u64
Click to open
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
Click to open
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)
Click to open
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
Click to open
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
Click to open
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>)
Click to open
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)
Click to open
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>
Click to open
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>)
Click to open
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>)
Click to open
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
Click to open
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
Click to open
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)
Click to open
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
Click to open
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)
Click to open
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
Click to open
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>
Click to open
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>
Click to open
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>
Click to open
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)
Click to open
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)
Click to open
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)
Click to open
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)
Click to open
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>
Click to open
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>
Click to open
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>
Click to open
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>)
Click to open
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>
Click to open
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>
Click to open
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
Click to open
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
Click to open
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>
Click to open
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
Click to open
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
Click to open
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)
Click to open
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)
Click to open
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)
Click to open
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)
Click to open
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>
Click to open
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>
Click to open
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)
Click to open
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)
Click to open
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
Click to open
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>
Click to open
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>
Click to open
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
}