Rust and Data Structures

Vectors

Vec<T> is Rust's dynamically sized, heap-allocated contiguous array. Because it stores all elements back-to-back in a single allocation and grows its capacity geometrically ($2\times$), Vec<T> is the default workhorse collection in Rust—frequently outperforming pointer-based structures even for workloads that involve mid-array insertions or removals up to thousands of elements.

Stack Header (24 Bytes on 64-bit):          Heap Allocation (`cap * size_of::<T>()`):
+--------------+---------+---------+        +-------+-------+-------+-------+-------+
| ptr: NonNull | len: 3  | cap: 5  | -----> |  T_0  |  T_1  |  T_2  | uninit| uninit|
+--------------+---------+---------+        +-------+-------+-------+-------+-------+
                                            |<--- Initialized ----->|<-- Spare Cap ->|

Asymptotic Complexity and Hidden Constant Factors of Vec<T>

Operation Method Time Complexity Memory & Cache Behavior
Index Access vec[i] / vec.get(i) $O(1)$ Single pointer offset (base + i * sizeof(T)).
Push to Back vec.push(val) $O(1)$ amortized Writes to ptr.add(len) and increments len; reallocates $2\times$ only when len == cap.
Pop from Back vec.pop() $O(1)$ Decrements len and reads ptr.add(len).
Order-Preserving Remove vec.remove(i) $O(n - i)$ Shifts elements i + 1..len left by 1 via fast ptr::copy (memmove).
Unordered Remove vec.swap_remove(i) $O(1)$ Replaces vec[i] with the last element (vec.pop()) in $O(1)$ time!
Batch Filtering vec.retain(|x| ...) $O(n)$ Compacts matching elements in-place in a single linear pass (unlike repeated remove(i) which is $O(n^2)$!).

Turning $O(n)$ Removal into $O(1)$ with swap_remove

Whenever element ordering inside a Vec<T> does not matter (such as an active connection pool, a bag of particles, or an unordered set of tasks), vec.swap_remove(index) removes an element from the middle of a 1,000,000-element vector in $O(1)$ constant time by swapping it with the last element:

pub fn remove_unordered_demo() {
    let mut pool = vec!["conn_a", "conn_b", "conn_c", "conn_d"];

    // Remove index 1 ("conn_b") in O(1) time by moving "conn_d" into index 1:
    let removed = pool.swap_remove(1);
    assert_eq!(removed, "conn_b");
    assert_eq!(pool, vec!["conn_a", "conn_d", "conn_c"]);

    println!("Removed {removed} in O(1); remaining pool: {pool:?}");
}

/// Deduplicates and compacts a vector in O(n log n) time with zero extra allocations!
pub fn sort_and_dedup(values: &mut Vec<u32>) {
    values.sort_unstable();
    values.dedup();
}

fn main() {
    remove_unordered_demo();

    let mut ids = vec![42, 10, 42, 7, 10, 99, 7];
    sort_and_dedup(&mut ids);
    assert_eq!(ids, vec![7, 10, 42, 99]);
    println!("Sorted & deduplicated in-place: {ids:?}");
}

Removed conn_b in O(1); remaining pool: ["conn_a", "conn_d", "conn_c"]
Sorted & deduplicated in-place: [7, 10, 42, 99]

Zero-Copy Splicing and Draining (drain and splice)

  • vec.drain(range): Returns an iterator that moves elements out of range by value and shifts any trailing elements left only once when the Drain iterator is dropped!
  • vec.spare_capacity_mut(): Returns &mut [MaybeUninit<T>] over the uninitialized tail len..cap, allowing low-level I/O readers to populate spare buffer capacity directly before calling unsafe { vec.set_len(new_len) }.