Vector Reallocation

When an operation on a Vec<T> (such as .push(), .insert(), .extend(), or .reserve()) requires more space than v.capacity(), the vector performs a reallocation: it requests a larger block of memory from the global allocator, moves existing elements to the new address via a bitwise copy (memcpy), frees the old block, and updates its ptr and capacity fields.

Step-by-Step Mechanics of a Reallocation

1. Before `v.push(50)` (len = 4, capacity = 4 — FULL):
   Stack: (ptr = 0x1000, len = 4, cap = 4)
   Old Heap @ 0x1000: [ 10, 20, 30, 40 ]

2. Reallocation Triggered:
   a) Allocates new buffer of capacity 8 at 0x2000 (or extends in-place via `realloc`)
   b) Copies 4 elements (`memcpy` 16 bytes) from 0x1000 -> 0x2000 (no `Clone` or `Drop` run!)
   c) Deallocates old buffer at 0x1000
   d) Writes 50 at index 4 and updates Stack: (ptr = 0x2000, len = 5, cap = 8)

   New Heap @ 0x2000: [ 10, 20, 30, 40, 50, --, --, -- ]

Crucially, because moving a value in Rust is always a shallow bitwise memcpy (and types stored in Vec<T> cannot be self-referential without Pin), reallocating a Vec<String> copies only the 24-byte String headers into the new buffer—it never clones or reallocates the inner heap strings themselves!

Observing Pointer Changes Across Reallocations

fn main() {
    let mut v: Vec<i32> = Vec::with_capacity(2);
    v.push(10);
    v.push(20);
    println!(
        "At cap=2: len={}, cap={}, ptr={:p}",
        v.len(),
        v.capacity(),
        v.as_ptr()
    );

    // Pushing a 3rd element exceeds capacity=2 and triggers reallocation:
    v.push(30);
    println!(
        "At cap=4: len={}, cap={}, ptr={:p}",
        v.len(),
        v.capacity(),
        v.as_ptr()
    );
}

At cap=2: len=2, cap=2, ptr=0x600000c04010
At cap=4: len=3, cap=4, ptr=0x600000c08020

(Note: If the system allocator finds free contiguous pages immediately following the existing block during realloc, it may expand the allocation in place without changing v.as_ptr(), though callers must never rely on the pointer remaining stable across growth.)

Why Reallocation Is Amortized $O(1)$

If a vector grew by a fixed constant (e.g., $+4$ slots each time), inserting $n$ elements would copy $4 + 8 + 12 + \dots + n = O(n^2)$ elements. Because Vec<T> grows geometrically (doubling its capacity: $4, 8, 16, 32, \dots, 2^k$), the total number of element copies across $n$ pushes is:

$$4 + 8 + 16 + \dots + \frac{n}{2} + n < 2n = O(n)$$

Dividing $O(n)$ total copy work across $n$ .push() operations yields an amortized $O(1)$ cost per push.