Two solutions, why one of them does not require Clone trait

Question

I solve on codewars katas and one of them told

Your goal in this kata is to implement a difference function, which subtracts one list from another and returns the result.

Here are two implementations. One of then requires Clone traits and another does not. Why second (shortest solution) does NOT need Clone trait?

First:

fn array_diff<T: PartialEq + Clone>(a: Vec<T>, b: Vec<T>) -> Vec<T> {
    let mut res: Vec<T> = Vec::new();
    for av in a.iter() {
        let mut found = false;
        for bv in b.iter() {
            if *av == *bv {
                found = true;
                break;
            }
        }
        if !found {
            res.push(av.clone());
        }
    }

    return res;
}

And second

fn array_diff<T: PartialEq>(a: Vec<T>, b: Vec<T>) -> Vec<T> {
    a.into_iter().filter(|x| !b.contains(x)).collect()
}

Hint: research the difference between `Vec::iter` and `Vec::into_iter`. — Colonel Thirty Two, Sep 24 '21 at 17:01
First guess would be the difference between `into_iter()` which consumes the Vec, vs `iter()` which merely borrows -- you're moving the elements from a in the second case, and in the previous case you're copying them., but I'm not confident enough to suggest as an answer :) — John Ledbetter, Sep 24 '21 at 17:01

Rob Napier · Accepted Answer · 2021-09-25T13:50:17.450

In your second example, a.into_iter() consumes the values in a, and then collects them as owned values in the returned Vec.

In your first example, the values are not consumed. Instead, they're cloned (so you need the Clone trait).

You can get the same requirements on the first version by consuming a in the same way:

// Get rid of Clone requirement
fn array_diff<T: PartialEq>(a: Vec<T>, b: Vec<T>) -> Vec<T> {
    let mut res: Vec<T> = Vec::new();
    for av in a {  // <--- remove the `.iter()`. Now `av` is owned.
        let mut found = false;
        for bv in b.iter() { // <-- Can't consume b; it's searched multiple times
            if av == *bv { // <-- No `*` on the av because it's owned.
                found = true;
                break;
            }
        }
        if !found {
            res.push(av);  // <-- push the owned value, not a clone
        }
    }

    return res;
}

for loops call .into_iter() implicitly (that's how a for loop works).

iter() creates a immutable, borrowing Iterator by convention.

Note that both of these functions take ownership of their parameters, which is a little strange IMO for a diffing function. Another way to build this is to apply the Clone requirement to the second example and pass references rather than owned values (this is my preferred solution because it's probably the simplest to use):

fn array_diff<T: PartialEq + Clone>(a: &[T], b: &[T]) -> Vec<T> {
    a.iter()
        .filter(|x| !b.contains(x))
        .cloned()
        .collect()
}

(For the switch from Vec to [], see Cerberus's comments below.)

Or the results can be references to the first slice (iter() rather than iter_into()) to avoid any copying, but now you need to worry about the lifetime of a, which can make usage more complicated:

fn array_diff<'a, T: PartialEq>(a: &'a [T], b: &[T]) -> Vec<&'a T> {
    a.iter().filter(|x| !b.contains(x)).collect()
}

Small fix - `&Vec` is generally considered bad practice: https://stackoverflow.com/questions/40006219/why-is-it-discouraged-to-accept-a-reference-to-a-string-string-vec-vec-o — Cerberus, Sep 25 '21 at 04:14

Two solutions, why one of them does not require Clone trait

1 Answers1