Arrays and Vec in Rust

An array is a row of values of the same type, stored side by side in memory. Because the slots are the same size and touch each other, the computer can jump straight to slot number i without looking at the ones before it. That is why reading by position is quick.

Reach for an array-like structure when you need fast access by position, or when you just have a list of things and no special reason to pick anything fancier. Most of the time, in Rust, that means Vec.

Rust gives you three related types, and it helps to separate them now:

• An array, written [i32; 5], holds exactly five i32 values. The length is part of its type and is fixed when the program is compiled.
• A Vec<i32> (say "vec", short for vector) is a growable list. It can add and remove items while the program runs.
• A slice, written &[i32], is a borrowed view of a run of items. It can look at part of an array or part of a Vec without copying anything.

Two numbers describe a growable list. The length is how many slots hold a value. The capacity is how many slots have been set aside. In the picture, five slots are used out of eight, so the length is 5 and the capacity is 8.

Reading slot i takes one step: the computer takes the address where the row starts and adds i times the size of one slot. Adding to the end, when there's room, is one step too: write into slot len, then add one to len.

Putting something in the middle is different. To insert at slot 1, everything from slot 1 onwards has to shuffle one place to the right to make a gap. The longer the list, the more shuffling. Removing from the middle shuffles the other way.

What happens when the row is full? A Vec asks for a bigger block of memory (usually about double), copies everything across, and gives the old block back. That copy is slow, but it happens rarely, so the average cost of a push stays tiny. Computer scientists call this amortised O(1): occasionally expensive, cheap when you average it over many pushes.

Before using Vec, build the idea yourself. This list sits on an array of exactly eight slots, and a field called len says how many are in use.

/// A growable-looking list that sits on a fixed array of eight slots.
/// `len` says how many of the slots are in use.
pub struct FixedArray {
    data: [i32; 8],
    len: usize,
}

impl FixedArray {
    pub fn new() -> Self {
        FixedArray { data: [0; 8], len: 0 }
    }

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

    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Adds to the end. If every slot is taken, the value is handed back.
    pub fn push(&mut self, value: i32) -> Result<(), i32> {
        if self.len == self.data.len() {
            return Err(value);
        }
        self.data[self.len] = value;
        self.len += 1;
        Ok(())
    }

    /// Reads one slot. Asking past `len` gives `None`, not a crash.
    pub fn get(&self, index: usize) -> Option<i32> {
        if index < self.len {
            Some(self.data[index])
        } else {
            None
        }
    }
}

impl Default for FixedArray {
    fn default() -> Self {
        Self::new()
    }
}

Go through it in order.

• data: [i32; 8] is the array, and len: usize is the count of used slots. A usize is the number type Rust uses for sizes and positions. It can't be negative.
• FixedArray { data: [0; 8], len: 0 } fills all eight slots with 0 and says none of them are used yet. The 0s are just placeholders. The list only believes the first len slots.
• push writes into slot len and then adds one to len. If the array is already full it refuses, and hands the value back inside Err. That Result<(), i32> type means "either Ok with nothing, or Err with an i32". Making the caller deal with that is better than silently losing the number.
• get returns an Option<i32>. Asking for a slot at or past len gives None instead of crashing, even though the array physically has a slot there. That slot is not part of the list yet.

Now the two moves that cost something. This is a second impl block for the same type, and Rust lets you split a type's methods this way.

impl FixedArray {
    /// Puts `value` at `index` and shifts everything after it one slot right.
    pub fn insert(&mut self, index: usize, value: i32) -> Result<(), i32> {
        if index > self.len || self.len == self.data.len() {
            return Err(value);
        }
        let mut i = self.len;
        while i > index {
            self.data[i] = self.data[i - 1];
            i -= 1;
        }
        self.data[index] = value;
        self.len += 1;
        Ok(())
    }

    /// Takes out the value at `index` and shifts everything after it left.
    pub fn remove(&mut self, index: usize) -> Option<i32> {
        if index >= self.len {
            return None;
        }
        let removed = self.data[index];
        for i in index..self.len - 1 {
            self.data[i] = self.data[i + 1];
        }
        self.len -= 1;
        Some(removed)
    }
}

insert starts at the end and copies each item one slot to the right, working backwards until it reaches the gap, then writes the new value in. It goes backwards so it doesn't overwrite an item before copying it. remove does the reverse, copying each later item one slot to the left. In both, the number of items copied can be as large as len. That is where the O(n) in the cost table comes from.

Try the whole thing in the Playground. The first block above has a main ready.

Vec is the same idea with the limits removed. It grows when it is full, it can hold any type, and it is heavily tested. In real code, you reach for it first.

let mut v = Vec::new();
v.push(10);
v.push(20);
v.push(30);

assert_eq!(v.len(), 3);
assert_eq!(v[0], 10); // panics if the index is out of range
assert_eq!(v.get(7), None); // never panics
assert_eq!(v.pop(), Some(30));
assert_eq!(v, [10, 20]);

Notice the difference between v[0] and v.get(7). Indexing with square brackets is bounds checked: Rust compares the index to the length every time, and if the index is out of range the program panics, which means it stops with an error message. It never reads memory that doesn't belong to the list. get does the same check but gives you an Option instead, so you decide what happens. Use v[i] when an out-of-range index would be a bug in your program, and get when the input might really be out of range.

The capacity is something you can see and set:

let mut v: Vec<i32> = Vec::with_capacity(4);
assert_eq!(v.len(), 0); // nothing stored yet
assert!(v.capacity() >= 4); // room for at least four

for n in 0..4 {
    v.push(n); // no reallocation: the room is already there
}
assert_eq!(v.len(), 4);

Vec::with_capacity(4) reserves room for at least four items without storing any, so the length is 0 and the capacity is 4 or more. The next four pushes never need to grow the block. If you know roughly how many items are coming, this saves repeated copying.

A slice looks at part of a list without copying it:

let v = vec![1, 2, 3, 4, 5];
let middle: &[i32] = &v[1..4]; // a view of v, not a copy

assert_eq!(middle, [2, 3, 4]);
assert_eq!(middle.len(), 3);
assert_eq!(v.first(), Some(&1));
assert_eq!(v.last(), Some(&5));

&v[1..4] means "items from position 1 up to, but not including, position 4". A function that takes &[i32] accepts a slice, a whole Vec (as &v) or a whole array, so it's the best type for a parameter that only reads.

Last, the part of Rust that catches people out first:

let mut scores = vec![50, 60, 70];
let first = &scores[0]; // a shared borrow of `scores`
// scores.push(80); // error: `first` is still in use on the next line
println!("{first}");
scores.push(80); // fine: `first` is not used after this point
assert_eq!(scores.len(), 4);

Remove the // from the first push and the code stops compiling. first is a borrow of scores: it points inside the Vec's block of memory. push might need to grow the Vec, which moves everything to a new block, and then first would point at memory that has been given back. In many languages that is a crash or a silent wrong answer. Rust refuses to compile it. The code as written is fine, because first is not used after the second push, so its borrow has already ended by then.

The pattern to remember: anything that works at the end of a Vec is cheap, and anything that works at the front or middle has to shuffle. If you find yourself inserting at the front over and over, a different structure (a queue, in lesson 5) will suit you better.

All three change the list in place, meaning they reuse the memory they were given instead of building a new list. That is why the parameters are &mut: the caller lends the list for changing, and gets it back changed.

pub fn reverse_in_place(nums: &mut [i32]) {
    todo!("swap the ends and walk inwards")
}

pub fn reverse_in_place(nums: &mut [i32]) {
    if nums.is_empty() {
        return;
    }
    let mut left = 0;
    let mut right = nums.len() - 1;
    while left < right {
        nums.swap(left, right);
        left += 1;
        right -= 1;
    }
}

pub fn remove_duplicates(nums: &mut Vec<i32>) {
    todo!("keep one of each value; the input is sorted")
}

pub fn remove_duplicates(nums: &mut Vec<i32>) {
    if nums.is_empty() {
        return;
    }
    let mut write = 1; // the next slot to fill
    for read in 1..nums.len() {
        if nums[read] != nums[write - 1] {
            nums[write] = nums[read];
            write += 1;
        }
    }
    nums.truncate(write);
}

pub fn rotate_right(nums: &mut [i32], k: usize) {
    todo!("move the last k numbers to the front")
}

pub fn rotate_right(nums: &mut [i32], k: usize) {
    let n = nums.len();
    if n == 0 {
        return;
    }
    let k = k % n;
    nums.reverse();
    nums[..k].reverse();
    nums[k..].reverse();
}

Array and list problems are a common place to start in coding tests and interviews, because they show whether you can handle indexes carefully. A few things are worth building as habits.

• Know the patterns. Two indexes moving towards each other (problem 1) and a read index with a write index (problem 2) turn up again and again. Seeing them in a new problem is most of the work.
• Check the edges before you start. Ask what happens for an empty list, a list of one item, and a list where every item is the same. Many wrong answers fail on exactly these.
• Ask what you are allowed to change. Can you change the input, or must you leave it alone? Is it sorted? Can numbers repeat? These questions are normal in an interview, and they change the best answer.
• Say the cost. After you write a solution, say its time and extra space out loud, such as "one pass, so O(n) time, and O(1) extra space". It shows you know what your code does.
• In Rust, say what is borrowed. Explaining that a function takes &mut [i32] because it changes the list but doesn't own it shows you understand the design, not just the syntax.

Made by VeraStack Labs