Standard Collections

Overview of std.collections

The std::collections module (backed by alloc::collections plus hash tables in std) provides Rust's eight foundational heap-allocated data structures, organized into four functional families: sequences, maps, sets, and priority queues.

The Four Collection Families

std::collections (+ prelude Vec / String)
  ├── Sequences       ──> Vec<T>, VecDeque<T>, LinkedList<T>  ( + String )
  ├── Maps            ──> HashMap<K, V>, BTreeMap<K, V>
  ├── Sets            ──> HashSet<T>,    BTreeSet<T>
  └── Priority Queue  ──> BinaryHeap<T>
Collection Category Backing Memory Structure In Prelude? Required Element Bounds
Vec<T> Sequence Contiguous growable heap array Yes None (T: Sized)
String Sequence (UTF-8) Vec<u8> guaranteed valid UTF-8 Yes Fixed (u8 / char)
VecDeque<T> Double-ended queue Growable ring buffer No None (T: Sized)
LinkedList<T> Doubly linked list Heap-allocated prev/next nodes No None (T: Sized)
HashMap<K, V> Key-value map SwissTable flat hash table No K: Eq + Hash
BTreeMap<K, V> Ordered key-value map Multi-element B-Tree nodes ($B=6$) No K: Ord
HashSet<T> Unordered set HashMap<T, ()> wrapper No T: Eq + Hash
BTreeSet<T> Ordered set BTreeMap<T, ()> wrapper No T: Ord
BinaryHeap<T> Max-priority queue Binary max-heap inside Vec<T> No T: Ord

Shared Design Principles Across All Standard Collections

  1. Single ownership and RAII: Every collection owns its elements and frees both the elements and its backing heap buffer automatically when dropped.
  2. No per-element boxing: Unlike languages that box every collection item behind an object pointer, Rust collections store T inline by value inside their backing arrays, ring buffers, hash buckets, or B-Tree nodes—minimizing pointer chasing and maximizing CPU cache locality.
  3. Zero-allocation empty constructors: Vec::new(), VecDeque::new(), BTreeMap::new(), HashMap::new(), and BinaryHeap::new() do not allocate any heap memory until the first element is inserted.
  4. Uniform array-literal construction via From<[T; N]>: Every standard collection implements From<[T; N]> (or From<[(K, V); N]> for maps), allowing uniform initialization with Collection::from([...]):
use std::collections::{BTreeSet, HashMap, VecDeque};

fn main() {
    let queue = VecDeque::from([10, 20, 30]);
    let set = BTreeSet::from(["rust", "zig", "c", "rust"]);
    let ports = HashMap::from([("http", 80_u16), ("https", 443)]);

    println!("VecDeque: {queue:?}");
    println!("BTreeSet: {set:?}");
    println!("HashMap:  {ports:?}");
}

VecDeque: [10, 20, 30]
BTreeSet: {"c", "rust", "zig"}
HashMap:  {"http": 80, "https": 443}