Why do I get FromIterator<&T>` is not implemented for Vec?

Question

I'm implementing a collection type that holds a vector of structs. I want to implements a bunch of methods to sort my vector in various ways. It is important that each function returns a collection of values because the call-site will modify the results further, which may imply deleting or changing values and none of these changes should propagate back to the original collection.

The struct is very basic:

#[derive(PartialEq, Debug, Clone)]
pub struct Shoe {
    size: u32,
    style: String,
}

The collection type just wraps the struct into a vector, like so:

#[derive(Debug, PartialEq, Clone)]
pub struct ShoesInventory {
    shoes: Vec<Shoe>
}

I want to filter all existing shoes according to given size, and return the result as a separate vector. Basically, iterate, filter, and collect. However, when I write this,

impl ShoesInventory {
    pub fn new(shoes: Vec<Shoe>) -> ShoesInventory {
        ShoesInventory { shoes }
    }

    pub fn shoes_in_size(&self, shoe_size: u32) -> Vec<Shoe> {
        self.shoes.iter().filter(| s| s.size == shoe_size).collect()
    }
}

I'm getting the following compiler error

error[E0277]: a value of type `Vec<Shoe>` cannot be built from an iterator over elements of type `&Shoe`
    --> src/shoes.rs:18:9
     |
18   |         self.shoes.iter().filter(| s| s.size == shoe_size).collect()
     |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ------- required by a bound introduced by this call
     |         |
     |         value of type `Vec<Shoe>` cannot be built from `std::iter::Iterator<Item=&Shoe>`
     |
     = help: the trait `FromIterator<&Shoe>` is not implemented for `Vec<Shoe>`

If I try to clone the element in the closure, it doesn't fix anything and I still get the same error. It's not so clear what the problem is b/c on another vector this code pattern actually works. For example, when you use another vector with a primitive type, say integer, the iterator, map/filter, collect pattern just works fine.

let v1: Vec<i32> = vec![1, 2, 3];
let v2: Vec<_> = v1.iter().map(|x| x + 1).collect(); // no problem here 

However, when the vector element contains a struct or a string, things get hairy.

I understand the error basically says, that the FromIterator is not implemented, but why? And how do I fix this?

Playground code

Answer 1

You have told Rust that you want to return a Vec<Shoe> - ie. a collection of owned shoe objects. However, you are feeding it a sequence of references to shoes.

Depending on the use case for this function, there are at least a couple of directions you could go.

As long as the callers to this function don't actually need owned shoes, then you can just change the function to this:

pub fn shoes_in_size(&self, shoe_size: u32) -> Vec<&Shoe> {
...

The caller will then receive a vec containing references to the shoes that meet the filter condition. This is often exactly what you want - why make expensive clones of the Shoe struct if you don't need to?

Note that the rust compiler will automatically ensure that the lifetime of the returned references does not exceed the lifetime of the ShoeInventory that they refer to.

Typically the cases where you would want to return owned items is if one of the following will hold:

• The caller to the function will want to modify the items returned by the function
• The lifetime of the returned items may need to outlive the collection that is handing them out

In either of these cases it might be more appropriate to clone them, as you indicated in the comments. In that case, though, I would clone them after filtering, so that you are not cloning items and then immediately discarding them:

pub fn shoes_in_size(&self, shoe_size: u32) -> Vec<Shoe> {
    self.shoes.iter().filter(| s| s.size == shoe_size).cloned().collect()
}