Vec surgery: retain, dedup and extract_if

Split a vector in two — the elements that survive a threshold and the elements that do not — without rebuilding either one from scratch, then collapse adjacent duplicates in the survivors.

pub fn compact(items: Vec<i64>, drop_below: i64) -> (Vec<i64>, Vec<i64>)

Return (kept, dropped). kept holds every element >= drop_below, dropped holds every element < drop_below, and relative order is preserved in both. After the split, adjacent equal elements in kept collapse to one.

The error you will meet first

The starter contains the loop almost everyone writes first — walk the vector, and when an element is too small, record it and remove it. It does not compile:

error[E0502]: cannot borrow `items` as mutable because it is also
              borrowed as immutable

This is the borrow checker earning its keep. items.iter() hands out a shared borrow of the whole vector, and that borrow is alive for the entire for loop because the iterator holds it. items.remove(i) wants a unique borrow at the same time. In C++ this compiles and then does something worse than crash: remove shifts every later element down one, the iterator’s internal pointer keeps advancing, and you silently skip elements — or, if the vector reallocates, you read freed memory. Rust turns that class of bug into a message.

Notice what the message is not telling you: it is not saying “add a clone” or “use indices”. It is saying the shape of the loop is wrong. The fix is a different operation, not a workaround.

The operations that exist for exactly this

Rust’s Vec gives you in-place surgery so you never have to iterate-and-mutate:

• retain(|x| ...) keeps the elements where the predicate is true, in place, in one pass, shifting survivors down as it goes. The ones it removes are dropped — you do not get them back.
• extract_if(range, |x| ...) is retain‘s greedier sibling: it removes the elements where the predicate is true and yields them to you as an iterator, leaving the rest in place and in order. Most standard libraries have no equivalent, so it is easy to miss. It takes a range as its first argument — pass .. for the whole vector.
• dedup() collapses adjacent runs of equal elements to a single copy. It does not sort first, and it is not a set operation.
• drain(range) removes a range and yields it. split_off(i) cuts the tail into a new Vec. swap_remove(i) is O(1) but moves the last element into the hole, destroying order; remove(i) is O(n) but stable.

The reflex this problem is trying to break is rebuild-by-collect: writing items = items.into_iter().filter(..).collect(). That is correct, and it allocates a whole second vector to produce a result the first vector could have held. clippy has a lint for one spelling of it (manual_retain), but be honest with yourself: the lint is narrower than the mistake. It fires on v = v.into_iter().filter(..).collect() and stays quiet on *v = v.iter().filter(..).copied().collect(). The gate will not catch every rebuild for you — you have to want the in-place operation.

The dedup trap

dedup is adjacent-only, and the two test cases that look redundant are not:

• [1, 2, 1] with nothing dropped stays [1, 2, 1]. The two 1s are never neighbours, so nothing collapses. If you expected [1, 2] you were thinking of a set.
• [3, 3, 3, 1, 3, 3] with drop_below = 2 becomes [3]. Removing the 1 makes the two runs of 3 adjacent, and then they collapse. Order of operations matters: dedup after the split, never before.

::: question Why does extract_if take a range when retain does not? Because extract_if returns a borrowing iterator that you might stop consuming early, so it has to define precisely which part of the vector it is responsible for. retain always runs to completion over everything and has no such question to answer. Pass .. when you mean the whole thing. :::

Remember the grade is compile + tests + clippy -D warnings.