Standard Collections

Capacity and Memory Allocation

Growable collections (Vec<T>, VecDeque<T>, String, HashMap<K, V>, HashSet<T>, BinaryHeap<T>) separate their logical length (.len(), the number of active elements) from their allocated capacity (.capacity(), the number of elements that fit before the next heap reallocation).

How Geometric Growth Achieves Amortized $O(1)$ Insertion

When a Vec<T> or HashMap<K, V> runs out of capacity (len == capacity), it allocates a new buffer (typically doubling its current capacity), moves the existing elements into the new buffer, and frees the old buffer:

Push 1..=5 into Vec::new():
  len=0, cap=0  (no heap allocation)
  push(1) ──> allocates cap=4: [ 1, _, _, _ ]
  push(2) ──> in-place:        [ 1, 2, _, _ ]
  push(3) ──> in-place:        [ 1, 2, 3, _ ]
  push(4) ──> in-place:        [ 1, 2, 3, 4 ]
  push(5) ──> reallocates cap=8, copies 4 items: [ 1, 2, 3, 4, 5, _, _, _ ]

Because reallocations happen at exponentially spaced intervals ($4, 8, 16, 32, \dots$), the total number of element copies across $n$ pushes is bounded by $2n$, making each .push() amortized $O(1)$.

Capacity Management Methods

Method Supported Collections Behavior
WithCapacity::with_capacity(n) Vec, VecDeque, String, HashMap, HashSet, BinaryHeap Pre-allocates space for at least n elements upfront
c.capacity() Same as above Returns the number of elements c can hold without reallocating
c.reserve(additional) Same as above Reserves space for at least additional more elements (may over-allocate geometrically)
c.reserve_exact(additional) Vec, VecDeque, String, BinaryHeap Reserves the exact minimum capacity for len + additional elements
c.try_reserve(additional) Same as above Fallible allocation returning Result<(), TryReserveError> instead of aborting on OOM
c.shrink_to_fit() Same as above Shrinks excess heap capacity down as close to len() as the allocator allows
c.shrink_to(min_capacity) Same as above Shrinks capacity down to max(len(), min_capacity) 
fn main() {
    let mut buf: Vec<u64> = Vec::with_capacity(100);
    buf.extend(0..10);
    println!("Before shrink: len={}, cap={}", buf.len(), buf.capacity());

    // Keep room for at least 16 items, releasing the remaining unused memory:
    buf.shrink_to(16);
    println!("After shrink_to(16): len={}, cap={}", buf.len(), buf.capacity());

    buf.shrink_to_fit();
    println!("After shrink_to_fit: len={}, cap={}", buf.len(), buf.capacity());
}

Before shrink: len=10, cap=100
After shrink_to(16): len=10, cap=16
After shrink_to_fit: len=10, cap=10

Important Caveat: .clear() and .remove() Do Not Free Heap Capacity

Calling vec.clear() or map.clear() drops all elements and sets len = 0, but retains the entire allocated capacity for future reuse. If a temporary collection briefly grew to millions of elements and will remain small for the rest of its lifetime, call .shrink_to_fit() (or .shrink_to(target)) after .clear() to return the excess memory to the allocator.