Vec and Dynamic Arrays

A Vec is three words — a pointer to a heap buffer, a length, and a capacity — and everything interesting happens in the gap between the last two. Watch a vector fill up:

let mut v: Vec<i32> = Vec::new();   // len 0, cap 0 — no allocation yet
v.push(1);   // len 1, cap 1  (first allocation)
v.push(2);   // len 2, cap 2  (realloc: 1 -> 2 slots)
v.push(3);   // len 3, cap 4  (realloc: 2 -> 4 slots)
v.push(4);   // len 4, cap 4
v.push(5);   // len 5, cap 8  (realloc: 4 -> 8 slots)

The pattern is doubling: a full buffer allocates twice its current size and copies everything over. That gives push an amortized O(1) cost — n pushes perform at most n copies total (each element is copied at most ~2 times on average), even though a single unlucky push is O(n). This is the number to quote in an interview: "pushing into a Vec is O(1) amortized because capacity doubles; the worst case for one push is O(n) at reallocation."

Three consequences follow, and all three show up in production:

1. Growth does not require Copy or Clone. Reallocation moves the bits of each T into the new buffer and drops the old allocation — a String, Box, or nested Vec is moved without touching its own heap data. Ownership rules make the move safe: after reallocation there is exactly one valid location for each element.
2. You cannot hold a reference across a push. This is where Rust beats C++ outright:

let mut v = vec![1, 2, 3];
let first = &v[0];
v.push(4);              // error[E0502]: cannot borrow `v` as mutable...
println!("{first}");     // ...because `first` might dangle after reallocation

The borrow checker refuses because a reallocation would silently invalidate first. In C++ that is undefined behavior; in Rust it does not compile. Every "is a reference into a Vec safe?" question reduces to this rule.
3. If you know the size, say so. Vec::with_capacity(n) or v.reserve(n - v.len()) performs one allocation instead of log₂(n) of them, and avoids the copying churn entirely:

let mut rows: Vec<Row> = Vec::with_capacity(records.len());
for r in records { rows.push(r); }   // zero reallocations

Measured on a bench of 100k elements, growth-from-zero copies roughly 200k items of work; with_capacity copies 100k and allocates once. Small numbers for integers, real numbers when T is a 200-byte struct.

The vec! macro covers the literal and fill cases in one expression: vec![1, 2, 3] builds from elements, vec![0; 10] builds ten zeros (requires Clone), and vec![] is Vec::new() with no allocation. When the vector shrinks logically but not physically — clear() and truncate(0) keep the allocation for reuse — call shrink_to_fit() if you truly want the memory back, accepting a full move. Capacity is a performance property, never a correctness one: read it with v.capacity(), and never index up to it.

Concrete numbers help when someone asks "how big is this buffer?" — a Vec<i32> of 1,000,000 elements is 4 MB of payload plus whatever slack doubling left behind, and a Vec<String> of the same length stores 24 bytes per element on the buffer while each string's text lives in its own allocation. Reallocation copies the buffer only — for Vec<String> that means moving pointers and lengths, never the text — which is why doubling feels cheap even with heavy element types.

A few methods complete the daily-use picture:

v.pop();                 // Option<T> — remove from the end, keep the allocation
v.extend([a, b, c]);     // bulk append; can size the growth in one step
v.truncate(2);           // drop elements past index 2, capacity unchanged
v.clear();               // len = 0, allocation kept for reuse
v.shrink_to_fit();       // reallocate down to len — when memory beats speed

extend deserves special mention: pushing one at a time inside a loop over a known source performs repeated growth, while extend reads the source's size_hint, reserves once, and appends. In a hot import path, v.extend(iter) versus a push loop is measurable — the "say the size up front" lesson from with_capacity, delivered by the method itself.

Indexing a vector is deliberately loud:

let v = vec![10, 20, 30];
println!("{}", v[1]);      // 20
println!("{}", v[3]);      // thread 'main' panicked: index out of bounds: the len is 3 but the index is 3

v[3] goes through impl Index<usize> for Vec<T>, which returns &T and has no failure mode in its signature — the only way to report an out-of-range index is to panic. Under the hood the slice performs a bounds check (the unsafe indexing is guarded by it), so the panic message includes both the length and the offending index. v.get(3) takes the same path with a different answer: Option<&T>, so None becomes part of your control flow.

The decision rule is about who produced the index, not about style: an index derived from the vector's own length (for i in 0..v.len(), a loop counter bounded by v.len(), a constant you can see in range) cannot be out of bounds, so indexing is honest and keeps the code free of unwrap. An index from outside — a parsed CLI argument, a line number from a file, a cache slot computed from a hash — is exactly the input Rust's Option exists for:

fn nth_port(args: &[String], n: usize) -> Option<u16> {
    args.get(n)?.strip_prefix("--port=").ok()?.parse().ok()
}

Chained get plus ? reads like a list of preconditions and returns None at the first violation, with no panic path at all.

Related idioms you should recognize: v.first() and v.last() are v.get(0) / v.get(len-1) in spirit and return Option<&T>; split_first() gives Option<(&T, &[T])> and is the clean way to write recursive or head/tail algorithms on slices. Range indexing panics the same way plain indexing does — &v[1..9] on a 3-element vector aborts with range end index 9 out of range for slice of length 3 — so untrusted ranges go through v.get(1..9).

One trap that surprises people: Vec<bool> is a specialization that stores one bit per element instead of one byte, so indexing it produces a proxy reference (BitRef) rather than &bool. let b = &v[0]; fails to compile with expected &bool, found &BitRef`` — use v[0] by value (it derefs to bool) or v.get(0).copied(). It is a rare case where the element type changes the API surface.

One performance question interviewers like to pose: "aren't bounds checks expensive?" In practice the optimizer removes them whenever it can prove the index range — a for i in 0..v.len() loop over v[i] compiles with the check hoisted or eliminated entirely, because the bound is the length itself. Checks that survive are the ones on data-derived indices, and they are precisely the checks you want. unsafe code may call get_unchecked, but only after performing an equivalent validation, and the unsafe block becomes a correctness liability for a few percent at most — the standard advice is to measure before reaching for it.

When the access pattern itself is the problem — repeated remove(0) on a long Vec is O(n) because every survivor shifts down — the fix is a different container, not unchecked indexing: VecDeque gives O(1) push_front/pop_front, and its indexing costs the same as Vec's. The panic-vs-Option decision stays the same on either type.

Interview framing: "how do you index a vector safely?" Answer with the source-of-the-index rule, name get/first/split_first, and mention that the bounds check on the panicking path is what makes the unsafe inner indexing sound.

The three ways to walk a Vec differ in exactly one axis — who owns the elements afterwards — and choosing wrong is either a compile error or a silent clone:

let names = vec!["ada".to_string(), "grace".to_string()];

for n in &names {          // iter():      borrows,  n: &String
    println!("{n}");
}
for n in &mut names {      // iter_mut():  borrows mutably, n: &mut String
    n.push_str("!");
}
for n in names {           // into_iter(): MOVES, n: String — `names` is gone afterwards
    store.insert(n);       // zero-copy transfer of ownership
}

iter and iter_mut let the vector outlive the loop; into_iter is the destructor-free way to hand every element to another data structure — no clone(), no double allocation, just the pointer moves. (On arrays, into_iter yields owned values since edition 2021; on &array it yields references, exactly like a vector.)

The rule that saves you a debugging session: you cannot push while iterating.

for x in &v {
    v.push(*x);   // error[E0499]: cannot borrow `v` as mutable more than once
}

The loop holds an iterator that borrows v immutably for its whole lifetime, so any mutation — including growth that would invalidate the iterator — is rejected. The three standard escapes, in order of preference: collect the work first (for i in indices_to_add { v.push(i) } where indices_to_add is a Vec built before the loop), use the purpose-built method, or iterate over v.clone() when you genuinely need the old snapshot:

v.retain(|x| *x % 2 == 0);        // remove in place, no intermediate vector
v.drain(2..);                     // consuming iterator over a range; allocation kept
v.iter().filter(|x| **x > 0).count();   // non-owning pipeline

retain is the canonical "filter a vector in place" — it compiles to one pass, shifts survivors, and never allocates. drain(..) gives you an iterator that moves elements out while leaving the vector empty but still allocated, useful for handing contents to a worker without paying for a new buffer.

Ownership shows up most visibly in the consuming loop: for line in lines { handle(line)?; } moves each String out, so lines cannot be used after the loop — which is exactly the guarantee you wanted when the vector was only a staging area. When you need the data and the vector afterwards, iterate by reference and clone only the pieces you store.

Four patterns that cover most real code, with their ownership spelled out:

// 1. Drain the vector completely, reusing it afterwards
while let Some(job) = jobs.pop() { run(job); }        // jobs is empty but still allocated

// 2. Read + mutate values in one pass
for user in &mut users { user.logins += 1; }           // &mut User, no clones

// 3. Compute with indices while keeping the source intact
for (i, row) in rows.iter().enumerate() { report(i, row); }

// 4. Move elements out into another container by value
let owners: Vec<String> = records.into_iter().map(|r| r.owner).collect();

Pattern 4 deserves a second look: into_iter() on the vector gives owned records, and .map(|r| r.owner) moves the field out — legal because the record itself is owned by the iterator, so partial moves are fine. Try the same on &records and the compiler asks for r.owner.clone(), which is the ownership axis deciding your allocation budget in one keyword.

Getting this axis straight is half of what interviewers mean by "explain the difference between iter and into_iter" — the other half is the cost: borrow-only loops do zero allocations, consuming loops move ownership for free.