Vec in Depth

Why this matters

Vec<T> is the collection you will use most: a growable list of values of one type, stored contiguously on the heap. You have used it casually since module 2. Now that you know ownership and borrowing, it is worth understanding properly: how it is laid out, what push costs, why references into it are restricted, and the methods that make common list operations one-liners.

Creating and filling

fn main() {
    let mut a: Vec<i32> = Vec::new();
    a.push(10);
    a.push(20);
    let b = vec![1, 2, 3];
    let zeros = vec![0u8; 5];
    let words: Vec<&str> = "the quick fox".split(' ').collect();
    let squares: Vec<u32> = (1..=5).map(|x| x * x).collect();
    println!("{:?} {:?} {:?} {:?} {:?}", a, b, zeros, words, squares);
}

[10, 20] [1, 2, 3] [0, 0, 0, 0, 0] ["the", "quick", "fox"] [1, 4, 9, 16, 25]

Vec::new() starts empty (and allocates nothing until the first push), vec![...] builds from a list or a repeated value, and collect() gathers any iterator into a Vec.

The layout: pointer, length, capacity

A Vec<T> is the same shape as a String (which is in fact a Vec<u8> with a UTF-8 guarantee):

 stack                          heap
 +-------------+               +----+----+----+----+----+----+
 | ptr  ----------------------> | 10 | 20 | 30 | 40 |    |    |
 | len  4      |               +----+----+----+----+----+----+
 | cap  6      |                 in use (len)        spare
 +-------------+

len is how many elements exist; capacity is how many fit before the buffer must grow. When a push finds no room, the Vec allocates a bigger buffer (roughly double), moves the elements over and frees the old one:

fn main() {
    let mut v: Vec<u64> = Vec::new();
    let mut last_cap = v.capacity();
    for i in 0..20 {
        v.push(i);
        if v.capacity() != last_cap {
            println!("len {:2} -> capacity {:2}, buffer at {:p}", v.len(), v.capacity(), v.as_ptr());
            last_cap = v.capacity();
        }
    }
}

len  1 -> capacity  4, buffer at 0x56153fb3bae0
len  5 -> capacity  8, buffer at 0x56153fb3bae0
len  9 -> capacity 16, buffer at 0x56153fb3bae0
len 17 -> capacity 32, buffer at 0x56153fb3bae0

(Addresses differ between runs. Here the allocator happened to find room to extend the buffer in place; with other allocations around, it moves to a new address. Your code can never rely on either.) Doubling means that although an individual push may copy everything, the average cost per push stays constant ("amortized O(1)"). If you know the final size, Vec::with_capacity(n) allocates once up front.

This is also exactly why the borrow checker forbids holding a reference into a Vec across a push (module 5): the elements may move.

Reading elements

fn main() {
    let v = vec![10, 20, 30];
    let second = v[1];
    let maybe = v.get(5);
    println!("{second} {:?} {:?} {:?}", maybe, v.first(), v.last());
    println!("{} {}", v.contains(&20), v.len());
    if let Some(i) = v.iter().position(|&x| x == 30) {
        println!("30 is at index {i}");
    }
}

20 None Some(10) Some(30)
true 3
30 is at index 2

v[i] panics when out of range; v.get(i) returns Option<&T>. Use indexing when an out-of-range index would be a bug, get when it is an expected possibility (user-supplied index, optional neighbor).

Indexing a Vec of non-Copy values gives you a place, not a value you can move out:

fn main() {
    let names = vec![String::from("Ada"), String::from("Bob")];
    let first = names[0];
    println!("{first}");
}

error[E0507]: cannot move out of index of `Vec<String>`
 --> main.rs:3:17
  |
3 |     let first = names[0];
  |                 ^^^^^^^^ move occurs because value has type `String`, which does not implement the `Copy` trait
  |
help: consider borrowing here
  |
3 |     let first = &names[0];
  |                 +
help: consider cloning the value if the performance cost is acceptable
  |
3 |     let first = names[0].clone();
  |                         ++++++++

Borrow it (&names[0]), clone it, or remove it from the Vec (remove, pop, swap_remove), which transfers ownership out.

Changing a Vec

fn main() {
    let mut v = vec![1, 2, 3, 4, 5];
    v.push(6);
    let last = v.pop();
    v.insert(0, 0);
    let removed = v.remove(2);
    v.swap(0, 1);
    v.truncate(4);
    println!("{:?} popped {:?} removed {removed}", v, last);
    v.extend([7, 8]);
    v.retain(|&x| x % 2 == 0);
    println!("{:?}", v);
    v.clear();
    println!("{:?} empty={}", v, v.is_empty());
}

[1, 0, 3, 4] popped Some(6) removed 2
[0, 4, 8]
[] empty=true

Costs matter: push and pop work at the end and are cheap. insert(0, x) and remove(0) shift every later element, so they are O(n); in a loop over a big Vec that becomes slow. If order does not matter, swap_remove(i) moves the last element into the hole in O(1). If you need cheap pushes and pops at both ends, use VecDeque (lesson 3).

Iterating three ways

fn main() {
    let mut v = vec![String::from("a"), String::from("b")];
    for s in &v {
        print!("{s} ");
    }
    println!();
    for s in &mut v {
        s.push('!');
    }
    println!("{:?}", v);
    for s in v {
        print!("{s} ");
    }
    println!();
}

a b 
["a!", "b!"]
a! b! 

Sorting and searching

fn main() {
    let mut v = vec![5, 3, 9, 1, 3];
    v.sort();
    println!("{:?}", v);
    v.dedup();
    println!("{:?} {:?}", v, v.binary_search(&5));
    v.sort_by(|a, b| b.cmp(a));
    println!("{:?}", v);
    let mut words = vec!["pear", "fig", "banana"];
    words.sort_by_key(|w| w.len());
    println!("{:?}", words);
    let mut fs = vec![2.5, -1.0, 3.75];
    fs.sort_by(|a, b| a.partial_cmp(b).unwrap());
    println!("{:?}", fs);
}

[1, 3, 3, 5, 9]
[1, 3, 5, 9] Ok(2)
[9, 5, 3, 1]
["fig", "pear", "banana"]
[-1.0, 2.5, 3.75]

sort is stable (equal elements keep their order). sort_by takes a comparison and sort_by_key a key function, both written as closures (module 11). Floats have no total order (NaN), so sort does not accept them; use partial_cmp or total_cmp. binary_search requires a sorted Vec and returns Ok(index) or Err(insert_position).

Vec and slices

A &Vec<T> converts automatically to &[T], and almost all the read-only methods (len, contains, iter, binary_search, windows...) are actually slice methods. So: store data in a Vec<T>, pass &[T] to functions that read it, and &mut Vec<T> only to functions that need to add or remove elements (a &mut [T] can change elements but not the length).

Common mistakes

• Moving out by index (E0507): borrow, clone, or remove.
• Holding a reference across push (E0502): copy the value or keep an index.
• remove(0) in a loop: quadratic. Iterate, or use VecDeque, or drain(..).
• Sorting floats with sort: E0277 "the trait Ord is not implemented for f64". Use sort_by with total_cmp.

Recap

• Vec<T> is a (ptr, len, capacity) handle owning a contiguous heap buffer; it grows by reallocating.
• v[i] panics when out of range; v.get(i) returns an Option.
• push/pop are cheap; insert/remove at the front shift elements.
• Iterate with &v, &mut v or v depending on whether you read, modify or consume.
• sort, sort_by_key, dedup, retain, binary_search cover most list chores.
• Pass &[T] to readers, &mut Vec<T> to functions that resize.

Going further: look up drain, split_off, chunks_exact and concat in the Vec and slice docs, and try Vec::with_capacity(1000) followed by 1000 pushes, printing the capacity at the end.