Vec<T>: the growable one

Remove duplicates while keeping the first occurrence of each value in place.

pub fn dedup_preserve_order(values: &[i32]) -> Vec<i32>

[1, 2, 1, 3, 2] gives [1, 2, 3]. [] gives []. [7, 7, 7] gives [7].

The starter is correct and trips three default-on clippy lints, one after another. Each one is a habit worth breaking, and this problem exists to break all three at once.

What a Vec<T> is

Three machine words — a pointer to a heap buffer, a length, and a capacity — totalling 24 bytes on a 64-bit machine, regardless of what T is or how many elements there are. size_of::<Vec<i32>>() == 24. The elements live in the buffer; the Vec value itself is small and cheap to move.

Pushing past capacity reallocates: a new, larger buffer is obtained, the elements are moved into it, the old one is freed. Growth is amortised — the capacity roughly doubles — so a thousand pushes cost about nine allocations rather than a thousand. Vec::with_capacity(n) gets you down to one when you know the size in advance. You will measure exactly this in Track 13.

Lint one: ptr_arg — take &[T], not &Vec<T>

The starter’s parameter is &Vec<i32>. Clippy’s ptr_arg says: take &[i32].

This is one of the highest-value habits in Rust, so here is the actual argument rather than an appeal to style. A &Vec<i32> is a reference to the three-word header, from which you follow a pointer to reach the data. A &[i32] is the pointer and the length. Everything you can do through the shared reference — read, iterate, index, slice, len — is available on the slice.

But the slice accepts strictly more callers. A caller with a Vec can pass &v. A caller with an array can pass &arr. A caller with a sub-range can pass &v[2..7]. A caller with a &Vec<i32> cannot pass it to a function that wants &Vec<i32> unless they own a whole Vec in exactly that shape. You lose nothing and gain every caller.

The same argument, structurally identical, gives you “take &str, not &String“ — which is item 1.23, and which is much easier to accept once you have seen this one.

Lint two: needless_range_loop

for i in 0..values.len() { … values[i] … } should be for &v in values. You met this in item 1.15. Indexing adds a bounds check per access, invites indexing the wrong collection, and cannot be off by one if you never write it.

Lint three: len_zero

out.len() == 0 should be out.is_empty(). It reads better, and for some types it is genuinely faster — computing a length can be O(n) where knowing emptiness is O(1). (In this particular starter the check is not merely unidiomatic, it is redundant: contains on an empty vector is already false.)

A fourth to know about: vec_init_then_push, which fires on let mut v = Vec::new(); v.push(1); v.push(2); and suggests the vec![1, 2] macro.

&v versus v when iterating

Worth noticing now, because it is the first practical brush with ownership:

for x in &vec  { }   // x: &T   — borrows; `vec` still usable afterwards
for x in &mut vec { } // x: &mut T — borrows mutably
for x in vec   { }   // x: T    — CONSUMES `vec`; it is gone afterwards

The third form moves the vector into the loop. For Vec<i32> in Track 1 you can mostly ignore the difference, because i32 is Copy and the vectors here are small. From Track 2 onward it will be the difference between compiling and E0382: use of moved value.

The algorithm

Scan the input, keeping the output vector as the record of what you have already emitted, and push only what is not already there. That is O(n²), which is fine at this size and is not fine at scale — a HashSet of what you have seen turns it into O(n) and measures about 15× faster on a few thousand elements. Track 5 introduces the set; the quadratic version is the right answer today.