Vector in Rust

Things on this page are fragmentary and immature notes/thoughts of the author. Please read with your own judgement!

:timing
:sccache 1

Tips and Traps¶

Summary of Collections in Rust has a good summary on when to each which collection in Rust.

use std::vec::Vec;

Construct a Vector¶

Construct an empty vector.

let v1: Vec<i32> = Vec::new();
v1

[]

v1.len()

0

Construct an empty vector with an (initial) capacity.

let w1: Vec<i32> = Vec::with_capacity(10);
w1

[]

w1.len()

0

Construct a vector of predefined values.

let v1 = vec![0, 1, 2, 30, 4, 5, 6, 7, 8, 9];
v1

[0, 1, 2, 30, 4, 5, 6, 7, 8, 9]

v1.capacity()

10

Construct a vector of 0’s.

let v2: Vec<i32> = vec![0; 10];
v2

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

v2.capacity()

10

Construct of vector of a fixed value with a dynamic size.

let n = 10;
let v3: Vec<i32> = vec![100; n];
v3

[100, 100, 100, 100, 100, 100, 100, 100, 100, 100]

Define a mutable vector.

let mut v4: Vec<i32> = vec![0; n];
v4

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

v4[0] = 1000;
v4

[1000, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Vec is NOT Copiable¶

let vec1 = vec![1, 2, 3];
let vec2 = vec1;
println!("{:?}", vec1);
println!("{:?}", vec2);

let vec2 = vec1;
           ^^^^ value moved here
println!("{:?}", vec1);
                 ^^^^ value borrowed here after move
let vec1 = vec![1, 2, 3];
    ^^^^ move occurs because `vec1` has type `std::vec::Vec<i32>`, which does not implement the `Copy` trait
borrow of moved value: `vec1`

let v1 = vec![1, 2, 3];
let v2 = &v1;
println!("{:?}", v1);
println!("{:?}", v2);

let v2 = &v1;
         ^^^ borrowed value does not live long enough
`v1` does not live long enough

let v2 = &v1;
         ^^^ borrow of `v1` occurs here
cannot move out of `v1` because it is borrowed

Vec is Clonable¶

let vec1 = vec![1, 2, 3];
vec1

[1, 2, 3]

let vec2 = vec1.clone();
vec2

[1, 2, 3]

Vector Slicing¶

A slice is a dynamically sized type representing a “view” into a sequence of elements of type T. The slice type is written as [T]. To use a slice type it generally has to be used behind a pointer, e.g., as &[T], which is a “shared slice” (often just called a “slice”). A shared slice does not own the data it points to but instead borrows it.

let v = vec![0, 1, 2, 30, 4, 5, 6, 7, 8, 9];
v

[0, 1, 2, 30, 4, 5, 6, 7, 8, 9]

&v[0..3]

[0, 1, 2]

&v[5..]

[5, 6, 7, 8, 9]

Create a New Sub Vector¶

Create a New Sub Vector via Slicing¶

(&v[5..]).to_vec()

[5, 6, 7, 8, 9]

Create a New Sub Vector via Iterator¶

v.iter().skip(6).collect::<Vec<_>>()

[6, 7, 8, 9]

Reference to Vectors¶

{
    let v: Vec<i32> = Vec::new();
    let r = &v;
    println!("{:?}", r);
}

[]

()

{
    let v: Vec<i32> = Vec::new();
    let mut r = &v;
    let v1: Vec<i32> = vec![0; 5];
    r = &v1;
    println!("{:?}", r);
}

[0, 0, 0, 0, 0]

()

{
    let mut v: Vec<i32> = Vec::new();
    let r = &mut v;
    println!("{:?}", r);
}

[]

()

Vec::chunks¶

let v = vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
v

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

v.chunks(3)

Chunks { v: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], chunk_size: 3 }

v.chunks(3).collect::<Vec<_>>()

[[0, 1, 2], [3, 4, 5], [6, 7, 8], [9]]

Vec::binary_search¶

let s = vec![0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];

let index = s.binary_search(&21);
index

Ok(10)

index.is_ok()

true

index.unwrap()

10

let index = s.binary_search(&23);
index

Err(11)

index.unwrap_err()

11

s.binary_search(&100)

Err(13)

s.binary_search(&-10)

Err(0)

let s2: Vec<u64> = [2 as u64, 3 as u64, 5 as u64, 8 as u64].to_vec();
s2

[2, 3, 5, 8]

s2.binary_search(&(2 as u64))

Ok(0)

Sort a Vector¶

Vec::sort and Vec::sort_unstable¶

Sort an vector using the nature order.

let mut vec = vec![1, 5, 10, 2, 15];
vec.sort();
vec

[1, 2, 5, 10, 15]

let mut vec = vec![1, 5, 10, 2, 15];
vec.sort_unstable();
vec

[1, 2, 5, 10, 15]

Vec::sort_by_key and Vec::sort_unstable_by_key¶

let mut vec = vec![1, 5, 10, 2, 15];
vec.sort_by_key(|x| -x);
vec

[15, 10, 5, 2, 1]

let mut vec = vec![1, 5, 10, 2, 15];
vec.sort_unstable_by_key(|x| -x);
vec

[15, 10, 5, 2, 1]

Vec::sort_by and Vec::sort_unstable_by¶

let mut vec = vec!["bb", "a", "dddd", "ccc"];
vec.sort_by(|s1, s2| s1.len().cmp(&s2.len()));
vec

["a", "bb", "ccc", "dddd"]

let mut vec = vec!["bb", "a", "dddd", "ccc"];
vec.sort_unstable_by(|s1, s2| s1.len().cmp(&s2.len()));
vec

["a", "bb", "ccc", "dddd"]

let mut vec = vec!["bb", "a", "dddd", "ccc"];
vec.sort_by(|s1, s2| s1.len().cmp(&s2.len()).reverse());
vec

["dddd", "ccc", "bb", "a"]

let mut vec = vec!["bb", "a", "dddd", "ccc"];
vec.sort_unstable_by(|s1, s2| s1.len().cmp(&s2.len()).reverse());
vec

["dddd", "ccc", "bb", "a"]

sort_by_cached_key¶

Return a New Sorted Copy¶

:dep itertools = "0.10.1"

use itertools::Itertools;

let v = vec![1, 5, 10, 2, 15];
v

[1, 5, 10, 2, 15]

v.iter().sorted()

IntoIter([1, 2, 5, 10, 15])

v.iter().sorted().collect_vec()

[1, 2, 5, 10, 15]

Sorted/Ordered Data Structures¶

https://doc.rust-lang.org/stable/std/collections/struct.BTreeMap.html sorted map

https://doc.rust-lang.org/stable/std/collections/struct.BTreeSet.html# sort set

https://github.com/bluss/indexmap ordered (insertion order) hashmap similar to dict in Python 3.7+

Vector of Vector¶

let data: Vec<Vec<i32>> = Vec::new();
data

[]

data.push

References¶

Module std::collections

https://doc.rust-lang.org/std/vec/struct.Vec.html

Improving SmallVec’s speed by 60% and why that shouldn’t matter to you