Solutions: 3 - The Vec is a table

Exercise 1 - Layout

use std::mem::size_of;
fn main() {
    println!("Vec<u32> = {}", size_of::<Vec<u32>>());  // 24
    println!("Vec<u64> = {}", size_of::<Vec<u64>>());  // 24
    println!("Vec<u8>  = {}", size_of::<Vec<u8>>());   // 24
}

A Vec<T> is always 24 bytes on a 64-bit machine (three 8-byte fields: ptr, len, cap), regardless of T. The element data lives elsewhere on the heap.

Exercise 2 - Capacity growth

#![allow(unused)]
fn main() {
let mut v: Vec<u32> = Vec::new();
for i in 0..100 {
    v.push(i);
    if v.len().is_power_of_two() || v.len() < 5 {
        println!("len={}, cap={}", v.len(), v.capacity());
    }
}
}

Output (Rust’s current strategy roughly doubles, but starts at 4):

len=1, cap=4
len=2, cap=4
len=4, cap=4
len=8, cap=8
len=16, cap=16
len=32, cap=32
len=64, cap=64

Each transition is a reallocation: a new heap region is allocated, all elements are memcpy’d across, the old one is freed.

Exercise 3 - Pre-size

#![allow(unused)]
fn main() {
let mut v = Vec::with_capacity(100);
for i in 0..100 { v.push(i); }
println!("len={}, cap={}", v.len(), v.capacity()); // len=100, cap=100
}

No reallocations happened. This is the right pattern when you know the upper bound - and most simulations do.

Exercise 4 - Indexing cost

Indexing a Vec<u32> runs ~1 ns/elem. A HashMap<usize, u32> lookup costs ~50-100 ns each (hash, probe, compare). Multiple orders of magnitude.

Iterate the map by index - map[&i] for each i - not into_values(). The cost being measured is the per-key hash-and-probe that an indexed lookup pays; draining the map in bucket order is a cheap sequential walk that hides exactly that cost, so it reports the wrong ratio.

Exercise 5 - swap_remove vs remove

100 calls to vec.remove(500_000) on a 1M Vec<u32> move ~50 million elements (each remove shifts ~half the vector). At ~1 ns per move that is ~50 ms total.

100 calls to vec.swap_remove(500_000) on the same vector move 100 elements total - under a microsecond.

The factor is roughly N / 2. For 1 million entries, that is half a million times faster.

Exercise 6 - Slices in function signatures

#![allow(unused)]
fn main() {
fn sum(xs: &[u32]) -> u64 {
    xs.iter().map(|&x| x as u64).sum()
}

let v: Vec<u32> = (0..1000).collect();
let total = sum(&v);  // &Vec<u32> auto-derefs to &[u32]
}

The function takes a slice; the caller passes &v. The conversion (Deref) is automatic. This is why almost every system in the book has signatures over &[T] and &mut [T], not &Vec<T>.

Exercise 7 - A from-scratch MyVec<u32>

The full implementation is in the Rustonomicon; about 200 lines including tests. The key shape:

#![allow(unused)]
fn main() {
struct MyVec<T> {
    ptr: NonNull<T>,
    len: usize,
    cap: usize,
}
}

new starts with cap = 0 and a dangling pointer. push allocates on first push (grow), then doubles capacity when full. get returns Option<&T> with bounds check. Drop frees both elements (running their destructors) and the heap allocation.

Working through this once is the cheapest way to convince yourself a Vec<T> is a small piece of careful work - and to internalise §42 - You can only fix what you wrote.