Nugget 17

Home

Vec Capacity: new() vs with_capacity()

Vec::new() looks harmless — and it is, for three elements. But push a million items one by one and that innocent new() triggers ~20 reallocations. Here's when and why to pre-allocate.

The Rule

// ❌ Potentially multiple allocations
let mut v = Vec::new();
for i in 0..1_000_000 {
    v.push(i);  // May reallocate ~20 times
}

// ✅ Single allocation — exact size known
let mut v = Vec::with_capacity(1_000_000);
for i in 0..1_000_000 {
    v.push(i);  // One allocation, no reallocations
}

When you know the size ahead of time, with_capacity() is always preferable to new(). The difference grows with every element.

How Vec Grows: Doubling Strategy

When a Vec runs out of capacity, it doubles its allocation. For 1 million elements pushed via Vec::new(): 

// Capacity after each reallocation:
0 → push → allocate 4    (some platforms allocate differently)
4 → push → 8
8 → push → 16
16 → push → 32
32 → push → 64
64 → push → 128
128 → push → 256
256 → push → 512
512 → push → 1024
...
524288 → push → 1048576  // ~20 reallocations total

Each reallocation allocates a new chunk of memory and copies every existing element over. By the end, some elements have been copied ~20 times. With with_capacity(1_000_000), every element is written exactly once.

Vec::new() Doesn't Allocate at All

This surprises most beginners: 

let mut v = Vec::new();   // ✅ No heap allocation (capacity = 0)
v.push(1);                 // First allocation: capacity → 4 (or similar)
v.push(2);                 // Room already, no allocation
v.push(3);                 // Room already
v.push(4);                 // Room already
v.push(5);                 // No room! Reallocation: capacity → 8

Empty Vec is free — it's just a pointer, a length, and a capacity on the stack. No heap memory is used until the first push.

Five Patterns, Ranked

1. Values known at compile time → vec! macro

let v = vec![1, 2, 3];  // Pre-allocates exact capacity

2. Size known exactly at runtime → with_capacity(n)

let n = calculate_size();
let mut v = Vec::with_capacity(n);

3. Building from an iterator → collect()

let v: Vec<_> = (0..n).map(|x| x * 2).collect();
// collect() uses size_hint() to pre-allocate optimally

4. Lower bound known → with_capacity(min)

let mut v = Vec::with_capacity(100);  // At least 100
while let Some(x) = get_next() {      // Will grow if needed
    v.push(x);
}

5. Size truly unpredictable → Vec::new()

let mut v = Vec::new();
while some_condition() {
    v.push(get_next_value());
}

Real-World: Reading a File

use std::fs::File;
use std::io::{BufRead, BufReader};

let file = File::open("data.txt").unwrap();
let reader = BufReader::new(file);

// ❌ Unknown number of reallocations
let mut lines = Vec::new();
for line in reader.lines() {
    lines.push(line.unwrap());
}

// ✅ collect() uses Iterator::size_hint() — often good enough
let lines: Vec<String> = reader.lines()
    .map(|l| l.unwrap())
    .collect();

// ✅ Even better: estimate from file size
let metadata = std::fs::metadata("data.txt").unwrap();
let estimated_lines = metadata.len() / 80;  // rough average line length
let mut lines = Vec::with_capacity(estimated_lines as usize);
// At most one reallocation if estimate is low

When It Doesn't Matter

For small collections, the difference is microscopic: 

// Three pushes — negligible difference
let mut v = Vec::new();
v.push(1);
v.push(2);
v.push(3);  // Maybe 1-2 reallocations, invisible to the user

// 10,000 pushes — starts to matter
let mut v = Vec::new();
for i in 0..10_000 { v.push(i); }
// ~13 reallocations, each copying existing elements

The habit of with_capacity matters at scale. For a hot loop processing millions of items, it's the difference between O(n) and O(n log n) memory operations.

Quick Reference

Method Allocates now? When to use
Vec::new() No (capacity = 0) Size truly unpredictable
Vec::with_capacity(n) Yes, exactly n slots Size known or bounded
vec![val; n] Yes, exactly n slots Repeated value at compile time
iter.collect() Uses size hint Building from an iterator

Key Takeaways