Standard Collections

Vec<T>

Vec<T> (std::vec::Vec<T>) is a contiguous, growable, heap-allocated array and the default sequential collection in Rust.

Memory Layout

On a 64-bit platform, a Vec<T> header occupies 24 bytes on the stack (ptr, len, capacity) pointing to a single contiguous block of capacity * size_of::<T>() bytes on the heap:

Stack (`Vec<i32>`, 24 bytes)         Heap Allocation (`capacity = 4`)
+----------------+                   +----+----+----+----+
| ptr      (8 B) +-----------------> | 10 | 20 | 30 | -- |
| len      = 3   |                   +----+----+----+----+
| capacity = 4   |                     [0]  [1]  [2]  (uninitialized)
+----------------+

Because all len elements are stored contiguously with no per-element pointer overhead:

  • Random indexing (vec[i] and vec.get(i)) is $O(1)$.
  • Appending and removing at the end (push and pop) are amortized $O(1)$.
  • &Vec<T> coerces to &[T] via Deref<Target = [T]>, exposing all slice methods (.sort(), .binary_search(), .windows(), .chunks()).

Essential Vec<T> Operations

Operation Method / Syntax Time Complexity
Create with initial items vec![a, b, c] or Vec::from([a, b, c]) $O(n)$
Pre-allocate capacity Vec::with_capacity(n) $O(1)$ allocation
Append / pop at back v.push(x) / v.pop() -> Option<T> Amortized $O(1)$
Index (panicking vs. checked) v[i] / v.get(i) -> Option<&T> $O(1)$
Insert / remove at index i v.insert(i, x) / v.remove(i) -> T $O(n - i)$ (shifts tail)
Remove at i without preserving order v.swap_remove(i) -> T $O(1)$ (swaps with last item) 
fn main() {
    let mut stack = vec![10, 20, 30, 40];

    stack.push(50);
    println!("Popped back:   {:?}", stack.pop());

    // O(1) removal when order does not matter (`swap_remove` swaps index 1 with last):
    let removed = stack.swap_remove(1);
    println!("swap_remove(1) returned {removed}, remaining: {stack:?}");
}

Popped back:   Some(50)
swap_remove(1) returned 20, remaining: [10, 40, 30]