Standard Collections

Vec vs. VecDeque

Both Vec<T> and VecDeque<T> store elements in a growable heap-allocated array and support $O(1)$ random indexing, but they optimize for different insertion/removal ends and slice guarantees.

Architectural Comparison

Vec<T> (Contiguous from index 0; grows only to the right):
+----+----+----+----+----+----+
| e0 | e1 | e2 | e3 | -- | -- |   push/pop at back = O(1)
+----+----+----+----+----+----+   insert/remove(0) = O(n) shift!

VecDeque<T> (Circular ring buffer; grows in both directions):
+----+----+----+----+----+----+
| e2 | e3 | -- | -- | e0 | e1 |   push/pop at front OR back = O(1)
+----+----+----+----+----+----+   not a single &[T] slice when wrapped!
Dimension Vec<T> VecDeque<T>
Stack size (64-bit) 24 bytes (ptr, len, capacity) 32 bytes (ptr, capacity, head, len)
Push / pop at back Amortized $O(1)$ (push, pop) Amortized $O(1)$ (push_back, pop_back)
Push / pop at front (index 0) $O(n)$ (insert(0, x), remove(0)) Amortized $O(1)$ (push_front, pop_front)
Random indexing (c[i]) $O(1)$ (ptr + i) $O(1)$ (ptr + (head + i) % cap, slightly more arithmetic)
Coerces to &[T] slice? Yes (Deref<Target = [T]>) No — split across two slices (as_slices()) unless make_contiguous() is called

Why Vec::remove(0) Is a Performance Bug on Queues

Using vec.remove(0) to dequeue from the front of a Vec<T> shifts all remaining $n - 1$ elements left by one slot on every dequeue. Draining $n$ items from the front of a Vec<T> takes $O(n^2)$ time, whereas draining $n$ items from the front of a VecDeque<T> with .pop_front() takes $O(n)$ time:

use std::collections::VecDeque;

fn main() {
    // 1. LIFO Stack -> use `Vec<T>`:
    let mut lifo_stack = Vec::new();
    lifo_stack.push(1);
    lifo_stack.push(2);
    println!("LIFO pop (Vec):      {:?}", lifo_stack.pop());

    // 2. FIFO Queue -> use `VecDeque<T>`:
    let mut fifo_queue = VecDeque::new();
    fifo_queue.push_back(1);
    fifo_queue.push_back(2);
    println!("FIFO pop (VecDeque): {:?}", fifo_queue.pop_front());
}

LIFO pop (Vec):      Some(2)
FIFO pop (VecDeque): Some(1)

Converting Between Vec<T> and VecDeque<T>

From<Vec<T>> is implemented for VecDeque<T> and From<VecDeque<T>> is implemented for Vec<T>. Converting a Vec<T> into a VecDeque<T> via VecDeque::from(vec) is an $O(1)$ zero-copy operation that reuses the existing heap allocation directly.