Before you begin
Why this matters
Rust has a fixed-size array and a growable Vec, and it checks every index. Knowing what len and capacity say lets you predict when push copies, where an index out of bounds panic comes from, and why a saved index can name the wrong element.
What this helps you reason about
- Find the last element without an index out of bounds panic.
- Read len and capacity and predict when push copies the elements.
- Spot a saved index that finds a different element after an insert.
At a station, taxis wait in a queue in the order they arrive, and the first taxi in the queue leaves first. This lesson keeps the taxis in a Rust array or Vec, and asks how an index finds a taxi, which of the two can grow, and what push does when the space runs out.
Already know this? The short version
- [T; N] is an array whose length is part of its type (Copy when T is); Vec<T> owns a growable block with a len and a capacity.
- push writes into spare capacity and doubles it when full (first capacity 4 for elements such as i32 in rustc 1.63), so push has a small amortized cost; Vec::with_capacity(n) gives space for n at the start.
- Indexing with [] panics past len (index out of bounds: the len is 3 but the index is 3); get(i) returns None there instead (an Option: Some(element) or None); len() - 1 on an empty Vec panics in a debug build.
- insert and remove move every later element. The compiler refuses a reference kept across the change (E0502), but not a saved usize index.
Words in this lesson (7)
- index
- The position of an element in an ordered collection, counted from 0. The first element has index 0, and the last has index length − 1.
- array
- A fixed-length sequence of values of one type, such as [i32; 3]. The length is part of the type and never changes.
- Vec
- Rust’s growable list, written Vec<T>. It owns a block of memory that holds its elements; push adds an element at the end, and pop removes the last one.
- length and capacity
- A Vec’s length, v.len(), is how many elements it holds. Its capacity, v.capacity(), is how many elements fit in its block before push needs a larger block.
- amortized cost
- The average cost of one operation over a long run of them. Adding to a growable list sometimes copies every element, but those copies become rarer as it grows, so the average cost of one addition stays small.
- panic
- Rust’s way of stopping because of a bug: the current thread stops with a message such as thread 'main' panicked at …. In a program with one thread, the program stops.
- off-by-one error
- A mistake where a loop or a count goes one step too far or stops one step too early, such as a loop that never reaches the last element of an array.
Examples are focused snippets; imports, enclosing functions, or classes may be omitted. C examples use C11; Haskell examples use Haskell 2010. Expand the notes for language-specific depth.
01 / Positions
How does a collection find the element at a position?
A Vec keeps its elements in order. vec![12, 7, 31] makes a Vec with three elements. Each element has a position, its index, counted from 0: taxi 12 is at index 0, taxi 7 at index 1, and taxi 31 at index 2. queue[i] reads the element at index i. An index has the type usize, an integer type that Rust uses for lengths and positions and that is never negative.
rank.len() is the number of elements, 3 here. Because counting starts at 0, the last index is always one less than the length: queue[queue.len() - 1] is the last taxi, however many there are.
Reading an element by its index takes one step, not a search. The elements sit side by side in one block of memory, so the address of element i is the start of the block plus i times the size of one element.
let queue = vec![12, 7, 31];
println!("{}", queue[0]); // 12
println!("{}", queue.len()); // 3
println!("{}", queue[queue.len() - 1]); // 31Indexes run from 0 to len − 1; the last element is at len − 1.
Coming from Python: There are no negative indexes: an index is a usize, which cannot be negative. Write queue[queue.len() - 1].
Experiment
Read the first and the last taxi
The first element is at index 0. The length is 3, so the last index is 3 - 1 = 2. After a fourth taxi is added, the length is 4, and the same expression reads index 3. vec! makes a block with exactly as many places as it has elements, so the capacity starts at 3. The push finds no free place and asks for twice as many, 6.
Why it matters Compute the last index from the length, as length - 1, so it stays right when the number of elements changes.
Predict the three printed numbers. Then change let queue to let mut queue, add the line queue.push(25); after it, and predict again.
fn main() {
let queue = vec![12, 7, 31];
let first = queue[0];
let last = queue[queue.len() - 1];
println!("{} {} {}", queue.len(), first, last);
}
What to look for
queue shows [12, 7, 31], then (len=3, cap=3, data=0x…): its length, its capacity, and the address of the block that holds its elements. first shows 12, last shows 31, and the run prints 3 12 31. After the edit, the push changes queue to [12, 7, 31, 25] (len=4, cap=6, …), and the run prints 4 12 25.
Expected output
3 12 3102 / Fixed or growable
What stays fixed, and what can grow?
Rust has both kinds of indexed collection. An array has a fixed length that is part of its type: [i32; 3] holds exactly three i32 values, and [0; 3] is an array of three zeros. A Vec can grow: push adds an element at the end, and pop removes the last one. To change a Vec, its variable must be declared with let mut.
A Vec does not keep its elements inside the variable. It owns a block of memory elsewhere: the Vec is the one value responsible for that block, and the block is freed when the Vec goes away. The variable holds the block’s address, the length, and the capacity. That is what the stepper shows after the elements: (len=3, cap=3, data=0x…).
let bays = [0; 3]; // an array: always 3 elements
let mut queue = vec![12, 7, 31]; // a Vec: can grow
queue.push(25);
println!("{} {}", bays.len(), queue.len()); // 3 4An array’s length is part of its type; a Vec grows with push and needs let mut.
Coming from Java: Vec<i32> is like ArrayList<Integer>, but it holds the i32 values themselves, side by side, not a reference to an object for each number.
Precisely: arrays, Vecs, and slices
An array of Copy values is Copy, so let b = bays copies every element; a Vec moves, as Arguments, values, and references showed. A slice, &[i32], lends a view of the elements of either one, which is why many functions take &[i32] rather than &Vec<i32>.
03 / Growing
What does it cost to grow?
A Vec’s capacity, queue.capacity(), is how many elements fit in its block. vec![12, 7, 31] makes a block with exactly 3 places, so its capacity is 3. Vec::new() makes an empty Vec with capacity 0: it has no block until the first push, which gives it space for a few elements (4 for i32 values here). While the length is below the capacity, push writes the new element into the unused space. When the length equals the capacity, push asks for space for twice as many elements. That can mean a new block, with every element copied into it and the old block freed.
Doubling makes the copies rarer as the Vec grows. Averaged over many pushes, each push costs a small amount. This average is the amortized cost.
When you know the final size, Vec::with_capacity(5) makes an empty Vec with space for 5. Five pushes then never need a larger block.
let mut queue = Vec::with_capacity(5);
queue.push(12);
println!("{} {}", queue.len(), queue.capacity()); // 1 5push needs a larger block only when the length reaches the capacity; with_capacity avoids that.
Precisely: the growth rule
The documentation promises only that push has amortized constant cost. In this stepper’s rustc 1.63, an empty Vec of elements such as i32 gets space for 4 at the first push, and a full one asks for twice its capacity. The memory allocator can sometimes make a block larger where it is, and then the data address stays the same and nothing is copied.
Experiment
Watch len and capacity while push grows a Vec
While len is below capacity, push writes into the unused space. When len equals capacity, push asks for space for twice as many elements, which can mean copying every element to a new block. Vec::with_capacity(5) asks for space for five at the start. The data=0x4 of the empty Vec is a placeholder, not an address in use. In this run the data address stays the same when cap grows from 4 to 8: the memory allocator made the block larger where it was, so nothing moved. That is an observation of this run, not a promise.
Why it matters Growing happens at 0 and 4 elements here, and becomes rarer as the Vec grows. When you know the final size, start with Vec::with_capacity, and no push needs more space.
Predict the five printed lines. Then change Vec::new() to Vec::with_capacity(5) and predict again.
fn main() {
let mut queue = Vec::new();
for taxi in [12, 7, 31, 25, 40] {
queue.push(taxi);
println!("{} {}", queue.len(), queue.capacity());
}
}
What to look for
Before the first push, queue shows [] (len=0, cap=0): an empty Vec has no block yet. After each push, cap is 4 for the first four pushes, then 8, and the run prints 1 4, 2 4, 3 4, 4 4, and 5 8. After the edit, cap is 5 from the start, and the run prints 1 5 to 5 5.
Expected output
1 4
2 4
3 4
4 4
5 804 / Out of range
What happens at an index past the end?
Rust checks every index. An index at the length or above stops the program with a panic, Rust’s way of stopping because of a bug. The stepper shows thread 'main' panicked at 'index out of bounds: the len is 3 but the index is 3'.
The usual cause is an off-by-one error: a loop that runs one step too far. for i in 0..queue.len() runs the block once for each i from 0 up to queue.len() - 1: the range a..b includes a and stops before b. The range 0..=queue.len() includes the end as well, one step too far. for taxi in &queue avoids indexes altogether.
let queue = vec![12, 7, 31];
for i in 0..queue.len() {
println!("{} {}", i, queue[i]);
}
// with 0..=queue.len(), the last round panicsAn index past the end panics; use a..b ranges, or loop over the elements.
Precisely: get, and an empty Vec
queue.get(i) checks the index and returns an Option instead of panicking. Option is Rust’s type for a value that may be missing: Some(x) holds a value x, and None holds nothing. get gives Some with a reference to the element, or None past the end. On an empty Vec, queue.len() - 1 itself panics in a debug build with attempt to subtract with overflow, because a usize cannot go below 0.
Experiment
Loop one step past the last index
0..queue.len() stops before 3; 0..=queue.len() includes 3. Rust checks every index, and index 3 is outside a Vec of length 3, so the program panics.
Why it matters Loop with i < length, never i <= length. The last index is length - 1.
Predict the printed lines. Then change 0..queue.len() to 0..=queue.len() and predict again.
fn main() {
let queue = vec![12, 7, 31];
for i in 0..queue.len() {
println!("{} {}", i, queue[i]);
}
}
What to look for
The stepper stops on the for line, where i is not listed, and then on the println! line, where i shows the index about to be read. The run prints 0 12, 1 7, and 2 31. After the edit, there is a fourth round with i at 3, and after the three lines the run stops with thread 'main' panicked at 'index out of bounds: the len is 3 but the index is 3', main.rs:4:30.
Expected output
0 12
1 7
2 3105 / Front and end
What changes when you add or remove at the front?
push and pop work at the end and move nothing. queue.insert(0, 40) puts 40 at index 0 and moves every other element one index later. queue.remove(0) takes out the element at index 0 and moves the rest one index earlier. Each costs one move per element that moves.
A saved index does not move with its element. If spot holds 1, the index of taxi 7, then after queue.insert(0, 40), queue[spot] is 12. A reference behaves differently. &queue[1] borrows the element: it reads the element where it is, without taking it, and while the borrow is in use the compiler refuses any change to the Vec. Write let taxi = &queue[1]; before the insert and use taxi after it, and the compiler reports error[E0502]: cannot borrow `queue` as mutable because it is also borrowed as immutable. Rust borrowing and references explains this rule. A saved index is a plain usize, not a borrow, so the compiler cannot catch it.
let mut queue = vec![12, 7, 31];
let spot = 1; // taxi 7
queue.insert(0, 40); // [40, 12, 7, 31]
println!("{}", queue[spot]); // 12, not 7Changes at the front move every element; a saved index then finds a different element.
Coming from C: insert does the move that C code writes as a loop or a memmove, and it checks the index first: queue.insert(9, 40) on a short Vec panics instead of writing past the end.
Precisely: VecDeque
std::collections::VecDeque is a growable ring buffer: push_front and pop_front work at the front without moving the other elements. Rust lifetimes and relationships shows a saved position going stale in a larger program.
Experiment
Save a position, then insert at the front
Adding at the front moves 12, 7, and 31 one index later. spot still holds 1, and index 1 now holds 12. Adding at the end moves nothing, so index 1 still holds 7.
Why it matters A saved index is a place, not an element. After a change at the front or in the middle, find the element again. The compiler refuses a reference kept across the insert, but a saved index is a plain number, so it cannot help.
Predict both printed numbers. Then change queue.insert(0, 40); to queue.push(40); and predict again.
fn main() {
let mut queue = vec![12, 7, 31];
let spot = 1; // taxi 7 is at index 1
queue.insert(0, 40);
println!("{} {}", spot, queue[spot]);
}
What to look for
spot shows 1. After the insert, queue shows [40, 12, 7, 31] (len=4, cap=6, …) while spot still shows 1, and the run prints 1 12. After the edit, queue shows [12, 7, 31, 40], and the run prints 1 7.
Expected output
1 1206 / Try it
Can you predict a fresh example?
Decide which elements move, then read each index. The next lesson, Stack and heap, shows where the blocks that hold elements are stored.
fn main() {
let mut queue = vec![12, 7, 31, 25];
let spot = 2; // taxi 31
queue.remove(0);
println!("{} {} {}", queue.len(), queue[0], queue[spot]);
}
What is printed?
Reveal the reasoning
3 7 25. remove(0) takes taxi 12 out of index 0, so queue is [7, 31, 25] and its length is 3. Every taxi moved one index earlier, so index 2, saved for taxi 31, now holds taxi 25.
Practice tickets
- ARRAY-101 · The van screen shows the stop after the one the driver typed → Free
- ARRAY-102 · A cabin that needs inspection stays in service when the cabin before it also needs one → Sign in · Pro
- ARRAY-103 · New flights stop appearing in the logbook after the fifth → Sign in · Pro