Vec<T> in Depth

Time Complexity and Practical Applications

Because Vec<T> stores elements contiguously in a single heap allocation with zero per-element metadata overhead, it serves as the building block for stacks, queues, arena allocators, flat matrices, and adjacency-list graphs.

Complete Vec<T> Time Complexity Reference

Operation Method / Syntax Time Complexity Notes
Index read / write v[i], v.get(i), v.get_mut(i) $O(1)$ Direct pointer offset ptr + i
Push at back v.push(x) Amortized $O(1)$ $O(n)$ only when len == capacity
Pop from back v.pop(), v.pop_if(p) $O(1)$ Never reallocates
Unordered remove at i v.swap_remove(i) $O(1)$ Overwrites v[i] with last element
Ordered insert / remove at i v.insert(i, x), v.remove(i) $O(n - i)$ Shifts trailing elements
Filter / deduplicate in place v.retain(p), v.dedup() $O(n)$ Single linear pass, 0 allocations
Linear search v.contains(&x), v.iter().position(p) $O(n)$ Cache-friendly sequential scan
Binary search (sorted Vec) v.binary_search(&x), v.partition_point(p) $O(\log n)$ Requires sorted slice
Sort v.sort(), v.sort_unstable() $O(n \log n)$ sort_unstable uses $O(1)$ space
Select $k$-th element v.select_nth_unstable(k) $O(n)$ average In-place Quickselect
Clear elements v.clear() $O(n)$ (or $O(1)$ if !needs_drop::<T>()) Retains heap capacity

Practical Application 1: Contiguous 2D Matrix (row * width + col)

Avoid Vec<Vec<T>> for dense 2D grids: a Vec<Vec<T>> with $R$ rows performs $R + 1$ separate heap allocations and requires two pointer dereferences per cell access. Storing all $R \times C$ cells in a single flat Vec<T> indexed by row * width + col uses 1 heap allocation and maximizes cache locality:

struct Matrix<T> {
    rows: usize,
    cols: usize,
    data: Vec<T>,
}

impl<T: Copy> Matrix<T> {
    fn filled(rows: usize, cols: usize, val: T) -> Self {
        Self {
            rows,
            cols,
            data: vec![val; rows * cols],
        }
    }

    fn get(&self, row: usize, col: usize) -> T {
        assert!(row < self.rows && col < self.cols);
        self.data[row * self.cols + col]
    }

    fn set(&mut self, row: usize, col: usize, val: T) {
        assert!(row < self.rows && col < self.cols);
        self.data[row * self.cols + col] = val;
    }

    fn row_slice(&self, row: usize) -> &[T] {
        let start = row * self.cols;
        &self.data[start..start + self.cols]
    }
}

fn main() {
    let mut mat = Matrix::filled(2, 3, 0_i32);
    mat.set(0, 2, 7);
    mat.set(1, 1, 42);

    println!("Row 0: {:?}, cell (1, 1) = {}", mat.row_slice(0), mat.get(1, 1));
}

Row 0: [0, 0, 7], cell (1, 1) = 42

Practical Application 2: Index-Based Arena / Graph (Avoiding Self-Referential Pointers)

In Rust, cyclic graphs and doubly linked trees cannot be built easily with raw &mut Node references because of exclusive aliasing rules. Instead, store all nodes inside a Vec<Node> (an index arena) and refer to nodes by their usize (or u32) index rather than by memory pointers:

#[derive(Debug)]
struct GraphNode {
    label: &'static str,
    edges: Vec<usize>, // Indices into `Graph::nodes`
}

struct Graph {
    nodes: Vec<GraphNode>,
}

impl Graph {
    fn new() -> Self {
        Self { nodes: Vec::new() }
    }

    fn add_node(&mut self, label: &'static str) -> usize {
        let id = self.nodes.len();
        self.nodes.push(GraphNode {
            label,
            edges: Vec::new(),
        });
        id
    }

    fn add_edge(&mut self, from: usize, to: usize) {
        self.nodes[from].edges.push(to);
    }
}

fn main() {
    let mut g = Graph::new();
    let a = g.add_node("Auth");
    let b = g.add_node("Billing");
    let c = g.add_node("Cache");

    // Supports cycles (`a -> b -> c -> a`) cleanly without Rc/RefCell:
    g.add_edge(a, b);
    g.add_edge(b, c);
    g.add_edge(c, a);

    for (id, node) in g.nodes.iter().enumerate() {
        println!("Node {id} ({}) -> neighbors: {:?}", node.label, node.edges);
    }
}

Node 0 (Auth) -> neighbors: [1]
Node 1 (Billing) -> neighbors: [2]
Node 2 (Cache) -> neighbors: [0]