Capacity, amortisation, and reusing Rust buffers

A Vec<T> stores a pointer, a length, and a capacity. Length counts the initialized elements you can use. Capacity tells you how many elements fit before a push needs to grow the backing allocation.

let mut values: Vec<i32> = Vec::new();
assert_eq!(values.len(), 0);
assert_eq!(values.capacity(), 0);
// A non-zero-sized element needs backing storage.
values.push(1);

An empty vector still occupies space for its metadata, but Vec::new() does not allocate a heap buffer. Zero-sized types are a special case: a Vec<()> can hold elements without allocating storage for them.

Growth: a guarantee and an observation

For push, a vector with spare capacity does not reallocate. When its buffer is full, growing it may move the elements to a new allocation. An allocator can also grow the existing allocation in place, so growth does not mean every element was necessarily copied.

Rust guarantees amortised O(1) push, but does not promise a particular growth factor. Here is a small experiment you can repeat:

let mut values: Vec<i32> = Vec::new();
let mut capacities = Vec::new();
for value in 0..1_000 {
    let before = values.capacity();
    values.push(value);
    if values.capacity() != before {
        capacities.push(values.capacity());
    }
}
println!("{capacities:?}");

For example, running this on macOS with Rust 1.98.1 produced:

[4, 8, 16, 32, 64, 128, 256, 512, 1024]

That is nine observed capacity changes, not a portable promise of nine heap allocations or nine copies. You may see a different sequence with another implementation or element type. Test the capacity guarantees your program needs, rather than asserting this exact sequence.

Why amortised O(1) still allows a slow push

Imagine starting with room for one element and doubling whenever the vector fills up. If growth moves the existing elements, the numbers moved are 1, 2, 4, 8, and so on. Across n pushes, that sum is less than 2n. Adding the n new elements also takes O(n) work, so the total is O(n).

Amortised O(1) means constant work per push when spread across the whole sequence. It does not mean every push is equally fast: one growth can move O(n) elements. This model counts element moves for a fixed element type; it is not a bound on allocator latency or elapsed time.

If you know the size in advance, reserve enough room:

let mut values: Vec<i32> = Vec::with_capacity(1_000);
for value in 0..1_000 {
    values.push(value);
}
assert_eq!(values.len(), 1_000);
assert!(values.capacity() >= 1_000);

These pushes do not need to grow the buffer. That can reduce allocator work and avoid growth pauses, but it does not guarantee a particular speedup. Timing depends on the allocator, element size, loop body, compiler and machine. Measure the workload you care about with optimized code and repeated runs.

For an existing vector, reserve(additional) reserves space for that many more elements beyond its length, not beyond its current capacity. For example, a vector with length 3 calling reserve(10) must have capacity for at least 13 elements afterward. It may already have enough room, and it may reserve more than requested.

Reserving a guessed upper bound can waste memory. A large reservation can also fail earlier than incremental growth. with_capacity is useful when the size estimate and memory trade-off make sense, not a universal rule.

Iterator size hints help plan capacity

Every iterator provides:

fn size_hint(&self) -> (usize, Option<usize>)

The pair is a lower bound and an optional upper bound on the number of items remaining. A slice iterator knows its exact remaining length. A string split generally cannot know its item count without scanning the string.

collect::<Vec<_>>() can use size information and specialized implementations to plan capacity. That often avoids repeated growth for a slice iterator, but neither the iterator contract nor collect promises one allocation for every pipeline. Some consuming iterators can even reuse an existing buffer.

A size hint must be correct, but unsafe code cannot trust an ordinary iterator's hint for memory safety. ExactSizeIterator adds an exact-count contract; it is also a safe trait, not permission to skip safety checks.

Clearing keeps the vector's buffer

Vec does not automatically shrink when you remove elements. clear() drops the elements and sets the length to zero while retaining capacity:

let mut v = vec![1, 2, 3];
let capacity = v.capacity();
v.clear();
assert!(v.is_empty());
assert_eq!(v.capacity(), capacity);
v.shrink_to_fit();

clear() can still release resources owned by the elements. For example, clearing a Vec<String> drops its strings and their buffers while retaining the outer vector's allocation. “Keeps capacity” does not mean “frees nothing.”

shrink_to_fit() asks to discard spare capacity. shrink_to(n) asks to shrink while keeping room for at least n elements and all existing elements. If capacity is already below n, it does nothing: it never grows the buffer. Either method may leave extra capacity, depending on the allocator.

let mut values = Vec::with_capacity(16);
values.extend([1, 2, 3]);
let before = values.capacity();
values.shrink_to(before + 10);
assert_eq!(values.capacity(), before);
values.shrink_to(4);
assert!(values.capacity() >= 4);
assert_eq!(values, [1, 2, 3]);

Shrinking may move elements. Freeing an allocation also does not guarantee that the process's memory usage immediately drops in an operating-system monitor.

Reusing a buffer can be useful for repeated work:

let mut buffer = String::new();
for record in ["first", "second", "third"] {
    buffer.clear();
    buffer.push_str(record);
    println!("{buffer}");
}

String::clear likewise retains its backing capacity. The buffer can grow for a larger record and serve later smaller ones. Replacing it with a new string each iteration would discard that reuse.

A long-lived buffer can retain a one-off large allocation. Consider shrinking after such a spike if it is unlikely to recur; shrinking after every record can undo the reason to reuse the buffer. These are guarantees about the specific collection, not a claim that all Rust collections retain memory: node-based collections have different allocation behavior.

A reservation trap with nested vectors

This expression repeats a value by cloning it:

let nested = vec![Vec::<i32>::with_capacity(64); 3];
assert!(nested.iter().all(Vec::is_empty));

Cloning a vector preserves its elements, not a promise to preserve spare capacity. The clones of this empty vector therefore need not retain the reservation. Clippy's repeat_vec_with_capacity lint calls out this pattern.

let n = 3;
let nested: Vec<Vec<i32>> = (0..n)
    .map(|_| Vec::with_capacity(64))
    .collect();
assert!(nested.iter().all(|v| v.is_empty() && v.capacity() >= 64));

Clippy can also suggest vec![a, b] instead of several immediate pushes, or vec![0; n] instead of reserving then resizing with zeroes. These express your intent directly; they do not promise free initialization or a specific allocator implementation.

Choosing what to do

• Length counts initialized elements; capacity is a documented usable bound.
• Amortised O(1) push is guaranteed. An exact growth sequence is not.
• Reserve when the expected size justifies it, and measure performance claims.
• Clearing a vector drops its elements but retains its own buffer. Shrink deliberately when retaining that space no longer helps.

For the precise contracts, see the standard library's Vec guarantees and shrinking documentation.