Arrays and Vec

A Rust array is a parking lot with a fixed number of numbered spots painted on the asphalt. You decide at construction time that the lot holds 4 cars, and it holds 4 cars forever. Spot 0 is the leftmost, spot 3 is the rightmost, and the compiler refuses to let a fifth car drive in. The whole lot sits in one continuous block of pavement, which is the only reason you can find spot 17 instantly — you walk 17 spot-widths from the start. No searching, no asking around.

fn fixed_lot_demo() {
    let lot: [i32; 4] = [10, 20, 30, 40];
    println!("fixed lot of {} spots:", lot.len());
    for (slot, car) in lot.iter().enumerate() {
        println!("  spot {slot}: car {car}");
    }
    println!("trying to park a 5th car would not even compile.");
}

The fixed lot is fast but useless the moment you do not know in advance how many cars are coming. Which is most of the time. In 1979 a Danish researcher named Bjarne Stroustrup hit this exact wall while building what would become C++. C arrays were the fixed lot — declare a size, live with it. Stroustrup wanted a container that grew when you handed it more data, kept the random-access speed of an array, and freed its own memory. He shipped that idea as std::vector and the world spent the next 30 years copying the design. Alexander Stepanov pinned down the growth rule at SGI in 1994 with the Standard Template Library: when the lot fills, double its size. Rust's Vec<T> is the same idea, written in a language that refuses to let you forget to free the memory.

Here is the trick to growing a paved lot without stopping traffic. You cannot extend the pavement — the next building is already there. So when car number 5 shows up at a 4-spot lot, the city does this: it leases an empty plot across the street, pours a fresh lot with 8 spots, walks every parked car over to the new lot, hands the old lot back to the original owner, and parks car 5 in its new spot. From the cars' point of view, nothing changed — spot 0 is still spot 0, just at a new address. From the city's point of view, it just paid for one giant move so it would not have to pay again for a while.

A Vec is a pointer to that lot plus two numbers: len, how many cars are parked, and cap, how many spots exist. When len hits cap, the move happens. Build the struct yourself and the shape is obvious.

struct MyVec {
    buf: Box<[i32]>,
    len: usize,
}

impl MyVec {
    fn new() -> Self {
        MyVec {
            buf: Box::new([]),
            len: 0,
        }
    }

    fn capacity(&self) -> usize {
        self.buf.len()
    }
}

The Box<[i32]> is the lot. It is a chunk of memory on the heap with a known size, owned by this MyVec and freed automatically when the MyVec goes out of scope. len tracks how far into that lot we have actually parked cars. capacity() is just the length of the box — that is the lot's size in spots, not the number of cars in it.

The push method is the whole story.

impl MyVec {
    fn push(&mut self, car: i32) {
        if self.len == self.capacity() {
            let new_cap = if self.capacity() == 0 {
                1
            } else {
                self.capacity() * 2
            };
            println!(
                "  grow: cap {} -> {} (copying {} cars)",
                self.capacity(),
                new_cap,
                self.len
            );
            let mut bigger: Vec<i32> = vec![0; new_cap];
            for i in 0..self.len {
                bigger[i] = self.buf[i];
            }
            self.buf = bigger.into_boxed_slice();
        }
        self.buf[self.len] = car;
        self.len += 1;
    }

    fn print_state(&self, label: &str) {
        println!(
            "  after {label}: len={} cap={} cars={:?}",
            self.len,
            self.capacity(),
            &self.buf[..self.len]
        );
    }
}

When len == capacity, the lot is full. We compute a new capacity that is double the old one — or 1 if the old lot was empty, since doubling zero gets you nowhere. We allocate a fresh Vec<i32> of that new size, copy every existing car into the new lot, convert it to a Box<[i32]>, and drop the old buffer. Then we park the new car in slot self.len and bump len. The old lot's memory is freed the moment we reassign self.buf, because Rust runs the destructor on the old box right then.

Run the program. The fixed lot prints first, then MyVec parks 8 cars and announces every reallocation as it happens.

fixed lot of 4 spots:
  spot 0: car 10
  spot 1: car 20
  spot 2: car 30
  spot 3: car 40
trying to park a 5th car would not even compile.

MyVec starts empty. We park 8 cars, one at a time:
  grow: cap 0 -> 1 (copying 0 cars)
  after push(10): len=1 cap=1 cars=[10]
  grow: cap 1 -> 2 (copying 1 cars)
  after push(20): len=2 cap=2 cars=[10, 20]
  grow: cap 2 -> 4 (copying 2 cars)
  after push(30): len=3 cap=4 cars=[10, 20, 30]
  after push(40): len=4 cap=4 cars=[10, 20, 30, 40]
  grow: cap 4 -> 8 (copying 4 cars)
  after push(50): len=5 cap=8 cars=[10, 20, 30, 40, 50]
  after push(60): len=6 cap=8 cars=[10, 20, 30, 40, 50, 60]
  after push(70): len=7 cap=8 cars=[10, 20, 30, 40, 50, 60, 70]
  after push(80): len=8 cap=8 cars=[10, 20, 30, 40, 50, 60, 70, 80]

8 pushes, but only 4 reallocations. That is the trick.

Read the middle block top to bottom and you can see the doubling. 0 grows to 1, then 1 to 2, then 2 to 4, then 4 to 8. Four moves to park eight cars. The fifth, sixth, seventh, and eighth pushes all happen for free — the lot already had room. That is what Stepanov proved: if you double, then on average each push costs constant time, even though some pushes are expensive. The expensive ones happen rarely enough that they amortize away.

One question to sit with. What if you knew up front you were going to park exactly 100 cars? You would skip every reallocation by asking for a 100-spot lot from the start. The real Vec lets you do that with Vec::with_capacity(100), which pours the lot the right size on day one and never reallocates. Same idea as MyVec::new followed by an immediate buffer swap. The reason it matters is that copying a million elements four or five times to grow a Vec is slow even with doubling, and the difference shows up in real programs.

Next lesson — what happens when the cars do not want to live in one continuous lot, and you would rather scatter them across the city with each car holding a slip of paper that points to the next one.