Borrowing Slices and Parts of a Value

By the end you can lend a function just part of a Vec or String, swap and recurse inside a slice, split a mutable borrow on purpose, and take a value out from behind a reference. In Rust Fundamentals (Ownership and Borrowing) you moved Strings and lent them with & and &mut; this lesson borrows only a part of a value.

Slices: a borrow of a range

A slice borrows a run of consecutive elements. &temps[1..4] has type &[i64]: a pointer plus a length, no copy. 1..4 means positions 1, 2 and 3; ..2 and 4.. leave one end open.

let temps = vec![12, -4, 7, -9, 3, 8];
let mid = &temps[1..4];
println!("{:?} len {}", mid, mid.len()); // [-4, 7, -9] len 3

On a String a slice counts bytes, and é takes two: "café" is 5 bytes, so &word[..4] stops inside é and panics ("not a char boundary").

Take &[T], not &Vec<T>, when a function only reads. The compiler converts &Vec<i64> to &[i64] automatically (a deref coercion) but never the reverse, so one &[i64] signature accepts a whole Vec, part of one, or an array:

fn average(xs: &[i64]) -> i64 {
    let mut total = 0;
    for x in xs { total += *x; }
    total / xs.len() as i64
}
average(&temps[1..4]);  // (-4 + 7 - 9) / 3 = -2
// with `xs: &Vec<i64>` that call is error[E0308]: mismatched types

&mut [T] can change elements but never the length, so there is no push. A slice also locks its whole owner: while let head = &v[..2]; is still used later, v.push(8) is error[E0502], because the compiler tracks v, not the range.

Working inside a &mut [T]

s.swap(i, j) exchanges two positions; s.swap(2, 2) is legal and does nothing. And re-slicing shrinks a slice, so recursion needs no index bookkeeping. This function numbers positions by depth in a halving tree, leaving the middle of each range behind:

fn depths(xs: &mut [i64], d: i64, calls: &mut u32) {
    *calls += 1;
    if xs.is_empty() { return; }
    let m = xs.len() / 2;
    xs[m] = d;                               // the middle is finished
    depths(&mut xs[..m], d + 1, calls);      // before it
    depths(&mut xs[m + 1..], d + 1, calls);  // after it
}

On [0; 7], depths(&mut data, 0, &mut n) leaves [2, 1, 2, 0, 2, 1, 2] and n == 15. Both halves stop short of position m, so m + 1.. is how you skip a finished element. Passing calls on is a reborrow: a short &mut made from the one you hold, ended when the call returns.

Check for empty first: xs.len() - 1 on an empty slice is 0 - 1 on a usize, which panics ("attempt to subtract with overflow").

Two &mut into one Vec: split on purpose

Holding both halves at once is rejected though they do not overlap, as is std::mem::swap(&mut v[0], &mut v[3]):

let a = &mut v[..2];
let b = &mut v[2..];
a[0] = b[0];
// error[E0499]: cannot borrow `v` as mutable more than once at a time

The compiler cannot see the ranges are disjoint; split_at_mut returns both at once:

let mut v = vec![1, 2, 3, 4];
let (a, b) = v.split_at_mut(2);
a[0] = b[1];                // v is now [4, 2, 3, 4]

You cannot move out from behind a reference

With struct Job { name: String }, a &mut Job lends the Job; returning its String would leave a hole:

fn take_name(j: &mut Job) -> String { j.name }
// error[E0507]: cannot move out of `j.name` which is behind a mutable reference

std::mem::take(&mut j.name) returns the value and leaves Default::default() behind (an empty String), so it needs a type with a default. Option::take leaves None; mem::replace(&mut x, new) leaves a value you choose.

let mut slot = Some(5);
let got = slot.take();  // got == Some(5), slot == None

Common mistakes

• Skipping the swap of an element with itself. It still counts: a sorted 1 2 3 4 5 6 must report swaps: 20, not swaps: 0.
• Sending only strictly smaller elements left. Equal values pile up on the right: 7 7 7 7 7 reports swaps: 4 instead of swaps: 14.
• Recursing on a range that includes the pivot (..=p, or p..). It can be as long as the input, so the recursion never ends.
• No empty-slice check. An empty input line reaches quicksort with length 0 and len() - 1 panics.

Your exercise

Implement quicksort in the starter: it sorts a slice in place and counts swaps through a &mut u64. Recurse on the two sides of the pivot, never on the pivot itself.