Standard Collections

Collection Complexity

Selecting an algorithm and data structure requires knowing the asymptotic time complexity of common operations across Rust's standard library collections.

Asymptotic Time Complexity Reference Table

($n$ = number of elements currently in the collection; $* = $ amortized over geometric resizing; $\dagger = $ expected average case assuming a good hash function.)

Collection Index / get Insert / Push Front Insert / Push Back Remove / Pop Front Remove / Pop Back Search / contains
Vec<T> $O(1)$ $O(n)$ $O(1)^*$ $O(n)$ $O(1)$ $O(n)$ ($O(\log n)$ if sorted)
VecDeque<T> $O(1)$ $O(1)^*$ $O(1)^*$ $O(1)$ $O(1)$ $O(n)$ ($O(\log n)$ if sorted)
LinkedList<T> $O(n)$ $O(1)$ $O(1)$ $O(1)$ $O(1)$ $O(n)$
HashMap<K, V> $O(1)^\dagger$ (get(&k)) — $O(1)^{*,\dagger}$ (insert) — $O(1)^\dagger$ (remove(&k)) $O(1)^\dagger$ (contains_key)
BTreeMap<K, V> $O(\log n)$ (get(&k)) $O(\log n)$ (first) $O(\log n)$ (insert) $O(\log n)$ (pop_first) $O(\log n)$ (pop_last) $O(\log n)$ (contains_key)
HashSet<T> $O(1)^\dagger$ (get(&x)) — $O(1)^{*,\dagger}$ (insert) — $O(1)^\dagger$ (remove(&x)) $O(1)^\dagger$ (contains)
BTreeSet<T> $O(\log n)$ (get(&x)) $O(\log n)$ (first) $O(\log n)$ (insert) $O(\log n)$ (pop_first) $O(\log n)$ (pop_last) $O(\log n)$ (contains)
BinaryHeap<T> $O(1)$ (peek max) — $O(\log n)^*$ (push) — $O(\log n)$ (pop max) $O(n)$

Bulk Operations Complexity

Several bulk construction and transformation methods have better asymptotic complexity than repeated single-element insertions:

Operation Repeated Single Calls Bulk Method Bulk Complexity
Build BinaryHeap<T> from $n$ items $n \times \text{push}$: $O(n \log n)$ BinaryHeap::from(vec) $O(n)$ (Floyd's algorithm)
Filter a Vec<T> in place Loop of vec.remove(i): $O(n^2)$ vec.retain(pred) $O(n)$
Sort and deduplicate a Vec<T> Insert into HashSet: $O(n)$ allocs vec.sort_unstable(); vec.dedup(); $O(n \log n)$ in-place (0 allocs)
Lookup in a read-only Vec<T> vec.contains(&x): $O(n)$ vec.binary_search(&x) (once sorted) $O(\log n)$ 
fn main() {
    let mut ids = vec![42, 10, 42, 7, 10, 99, 7];

    // Sort in O(n log n) and deduplicate in O(n) in-place with zero extra allocations:
    ids.sort_unstable();
    ids.dedup();

    // O(log n) binary search on the sorted Vec:
    println!("Sorted unique IDs: {ids:?}");
    println!("Binary search 42:  {:?}", ids.binary_search(&42));
}

Sorted unique IDs: [7, 10, 42, 99]
Binary search 42:  Ok(2)