David Chen

Software Engineer
San Francisco Bay Area

Remove duplicates while preserving order in Rust

Suppose we have a vector in Rust:

vec![1, 3, 1, 2, 2]

We want to remove all duplicates while preserving the order, like this:

vec![1, 3, 2]

One typical solution is to keep a set of encountered items as we move or copy items into a new vector:

let items = vec![1, 3, 1, 2, 2];

let mut uniq = Vec::new();
let mut seen = HashSet::new();

for item in items {
    if !seen.contains(&item) {
        seen.insert(item);
        uniq.push(item);
    }
}

assert_eq!(uniq, vec![1, 3, 2]);

But I recently learned a nifty idiom from Programming Rust:

let mut items = vec![1, 3, 1, 2, 2];

let mut seen = HashSet::new();
items.retain(|item| seen.insert(*item));

assert_eq!(items, vec![1, 3, 2]);

This works because retain only keeps items for which the predicate returns true, and insert only returns true if the item was not previously present in the set. Since the vector is traversed in order, we end up keeping just the first occurrence of each item. Neat!