How can I dedupe an immutable list of Cloneable objects with only a single clone of each item?

Question

Thanks to another SO answer, I successfully wrote a function that deduplicates a Vec. However, it does two clones of each item. I want to be able to do this with a single clone.

Here is the gist of what I am doing.

The incoming Vec is not mutable.
The output list must preserve order of retained items.
The type of item is Clone, not Copy.


use std::collections::HashSet;

pub fn distinct_values<T: Clone + Hash + Eq>(list: &Vec<T>) -> Vec<T> {
    let mut set: HashSet<T> = HashSet::with_capacity(list.len());
    let deduped: Vec<T> = list
        .iter()
        .cloned()
        .filter(|item| set.insert(item.clone()))
        .collect();
    deduped
}

The other question that I studied was: Vec::dedup does not work — how do I deduplicate a vector of strings?

Denys Séguret Denys Séguret · Accepted Answer · 2021-04-13T13:53:02

You don't need the items in the hashset: references would be enough.

Note also that you should prefer passing &[T] instead of &Vec<T> as argument as it covers more cases. So I'd change your code to

pub fn distinct_values<T: Clone + Hash + Eq>(list: &[T]) -> Vec<T> {
    let mut set: HashSet<&T> = HashSet::with_capacity(list.len());
    list
        .iter()
        .filter(|item| set.insert(item))
        .cloned()
        .collect()
}

Not only do you avoid to clone all items twice, you don't clone at all the items you don't keep.

How can I dedupe an immutable list of Cloneable objects with only a single clone of each item?

1 Answers