Iterator invalidation, and the bug class that stopped existing

pub fn compact(xs: &mut Vec<i64>, target: i64) -> Vec<i64>

Remove every element equal to target from xs, in place, keeping the order of the survivors. Return the removed values, in the order they appeared.

[1,2,3],   target 9 -> xs [1,2,3], removed []
[5,5,5],   target 5 -> xs [],      removed [5,5,5]
[1,7,7,2], target 7 -> xs [1,2],   removed [7,7]     <- read this one twice
[4,1,2,4], target 4 -> xs [1,2],   removed [4,4]

The returned vector is checked, not just the survivors. That is deliberate: a buggy implementation that removes one of two adjacent 7s still leaves the right-looking survivors on some inputs, and the removed-count catches it.

The starter is a bug you have written before

for (i, x) in xs.iter().enumerate() {
    if *x == target {
        removed.push(xs.remove(i));   // error[E0502]
    }
}

Look at it without the Rust. It is: iterate over a container, and mutate the container while iterating. You have written this. Everyone has written this. It is one of the oldest bugs in programming, and it goes by the name iterator invalidation.

Here is what the other languages do with it.

C++. for (auto it = v.begin(); it != v.end(); ++it) if (*it == t) v.erase(it); — erase invalidates it and every iterator after it. Continuing to use it is undefined behaviour. Not “an exception”. Not “wrong answer”. UB: the optimiser is entitled to assume it does not happen, so the program may work in debug, fail in release, or corrupt unrelated memory eighteen frames away. This is a genuine, common, hard-to-find production bug.

Java. ConcurrentModificationException, if you are lucky. The modCount check is explicitly documented as best-effort — it “cannot be guaranteed” and the docs say you must not depend on it for correctness. Skip the right number of elements and it silently does the wrong thing.

Python. Two behaviours, neither of them good. Mutating a dict during iteration raises RuntimeError: dictionary changed size during iteration. Mutating a list during iteration raises nothing at all — the loop is index-based under the hood, so deleting element i shifts everything down and the loop silently skips the element that moved into slot i. This is why [1,7,7,2] is a mandatory test case: the naive fix produces [1,7,2].

Rust. error[E0502]: cannot borrow*xsas mutable because it is also borrowed as immutable. At compile time. Every time. With no runtime cost.

That is the argument for the whole track, and it is the moment the borrow checker converts from tax into feature. xs.iter() holds a shared borrow of the vector for as long as the loop runs; remove needs an exclusive one; the rule from item 3.3 forbids the overlap. The compiler is not being pedantic. It is refusing to compile a use-after-free.

Do not “fix” it by switching to indices

The first thing everyone tries next:

let mut i = 0;
while i < xs.len() {
    if xs[i] == target { removed.push(xs.remove(i)); }
    i += 1;
}

This compiles — no iterator, no loan, no error — and it is the Python bug, faithfully reproduced. After removing index i, the next element slides into slot i, and then i += 1 steps straight over it. [1,7,7,2] gives you [1,7,2].

Worth sitting with for a moment: the borrow checker protects you from memory unsafety, not from being wrong. Silencing it by restructuring into indices removes the safety net and keeps the bug. That is a real hazard of getting good at satisfying the compiler.

The catalogue

The standard library has the operation. Several, in fact, and knowing which is which is the practical half of this item.

• retain(|x| ...) — keep the elements matching the predicate, drop the rest, one pass, order preserved. The default answer. If you write the loop by hand, clippy’s manual_retain will name it for you.
• retain_mut(|x| ...) — same, but the closure gets &mut T, so you can edit survivors as you filter.
• drain(range) — remove a contiguous range and yield the removed elements as an iterator. Great when the thing you want to remove is a slice of positions.
• extract_if(range, pred) — remove the elements matching a predicate and yield those. This is retain‘s mirror image: retain keeps and discards, extract_if discards and hands back. Stabilised in Rust 1.87. Note the argument order: it takes a range first, then the predicate — that changed during stabilisation, so older examples show a one-argument form. .. is the whole vector.
• dedup_by — collapse runs of equal elements. Not what you want here, but the same family.
• swap_remove(i) — O(1) removal that moves the last element into the hole. Destroys order. Excellent when order does not matter, wrong here.

This problem asks for both the survivors and the removals, which points at exactly one of those.

Beware while let Some(x) = it.next() shapes — clippy’s while_let_on_iterator will send you back to a for. And if you write a for i in 0..n loop and then change n inside it, mut_range_bound will point out that the range was already evaluated and your change does nothing.

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