In this lesson, you will learn how Rust’s Vec<T> manages memory behind the scenes to balance efficient storage with the performance costs of dynamic resizing.
When you push elements into a Vec, it doesn’t just grab a new block of memory for every single item. Doing so would be catastrophic for performance, as every push would involve a system call to allocate memory on the heap. Instead, Vec uses a strategy called geometric growth.
The Growth Strategy
A Vec maintains a capacity, which represents the number of elements it could hold without needing to allocate more memory. When you push an element that exceeds the current capacity, the Vec allocates a new, larger block of memory—typically doubling its previous size.
Consider this behavior:
let mut v = Vec::new();
// 1. Capacity 0: push -> reallocates to 1
// 2. Capacity 1: push -> reallocates to 2
// 3. Capacity 2: push -> reallocates to 4
// 4. Capacity 4: push -> reallocates to 8
Amortized Complexity
Because the Vec doubles its size, the number of expensive reallocation events grows logarithmically relative to the number of elements. Most push operations are O(1) because they simply involve writing a value into an already allocated slot.
While the occasional "reallocation" step is O(n)—because the system must allocate a new buffer and copy existing elements into it—the amortized cost per operation remains O(1). Essentially, the cost of the rare, expensive resize is spread out over so many cheap, constant-time insertions that the average overhead becomes negligible.
Why this matters
Understanding this allows you to predict performance overhead. If you know your application will handle thousands of items, the constant reallocation during the growth phase can cause CPU spikes and memory fragmentation. You can mitigate this by using Vec::with_capacity(n) to pre-allocate the required memory upfront, effectively reducing the number of costly heap migrations to zero.
Key Takeaway: Rust’s Vec uses geometric expansion to ensure that while individual resizes are expensive, the amortized cost of inserting elements into a collection remains constant-time, O(1).