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!