My iterator is returning a reference to a reference

Sometimes you mean it. Other times you really don't. It can be a bit of a headscratcher, but is not a particularly complicated situation, just easy to stumble into on a tired afternoon. In the end it all comes down to the ensuring you're being purposeful about what you're iterating over.

I'll take a relatively brief dive into what can cause this, and how you can get back to iterating over what you want to iterate over.

Here's an example:

let x = &vec!["hello"; 15];
let y: Vec<String> = x.iter()
    .map(|x| String::from(x) + "world")
    .collect();

This will give you some red lines when compiling:

the trait bound `std::string::String: std::convert::From<&&str>` is not satisfied

the trait `std::convert::From<&&str>` is not implemented for `std::string::String`

help: the following implementations were found:
<std::string::String as std::convert::From<&'a str>>
<std::string::String as std::convert::From<std::borrow::Cow<'a, str>>>
<std::string::String as std::convert::From<std::boxed::Box<str>>>
note: required by `std::convert::From::from`rustc(E0277)

The root cause of the issue is that we are iterating over the values of the vector by reference, which can situationally arise as a problem - it's a little bit context dependant, and there are caveats, which we'll get into.

Lets get this compiling successfully.

Making the red lines go away

In many cases, it's sufficient to look at de-referencing the reference at some stage in the pipeline before continuing, which can be done by having a stage that looks like:

let x = &vec!["hello"; 15];
let y: Vec<String> = x
    .iter()
    .map(|&x| String::from(x) + "world")
    .collect();

Alternatively, you can use the built-in method, Iterator<T>::cloned(), which provides a nice shorthand for this:

let x = &vec!["hello"; 15];
let y: Vec<String> = x
    .iter()
    .cloned()
    // .map(|&x| x) also works
    .map(|x| String::from(x) + "world")
    .collect();

If we're working with a Vec<T> instead of a &Vec<T>, we can change how we iterate over the Vector.

let x = vec!["hello"; 15];
let y: Vec<String> = x
    .into_iter()
    .cloned()
    .map(|x| String::from(x) + "world")
    .collect();

If we have a Vec<T> we can say the enclosing scope has ownership over the Vector. Iterating in this way over the vector (i.e into_iter instead of iter) creates a iterator that iterates over the values of the vector by value, rather than by reference. Iteration in this way is a little different though, as it consumes the vector, essentially transferring ownership of the values from the vector, to the iterator. You'd only really want to use this method if you no longer needed the old vector.

Note that into_iter does nothing different when used on something you don't have ownership over in the current scope. It produces an iterator by reference in this case. You can use a tool like clippy to flag redundant code like this:

this .into_iter() call is equivalent to .iter() and will not move the Vec

But how did we get here?

Iterating over slices

Slices implement a trait, IntoIterator allowing them to be iterated over. into_iter and iter can both be used on sliced, though as mentioned above, this is quite redundant as the method call wont attempt to move the value. Iterating over a slice yields references to the elements of the slice.

You might find you're unexpectedly iterating over a slice. Consider the first example:

let x = &vec!["hello"; 15];
let y: Vec<String> = x
    .iter()
    .map(|&x| String::from(x) + "world")
    .collect();

We say that x is automatically de-referenced from &Vec<String> to &[String], i.e a slice. You mgiht run into this situation when passing a vector by reference to a function that iterates over the vector.

Iterating over values by reference

into_iter creates an iterator over the values of the iterable, whereas iter creates an iterator over references to the values of the iterable. The syntax difference is fairly subtle, but the difference is fairly large, with into_iter consuming the iterable, which means you need to take a little bit of care to avoid the borrow checker shouting at you.

Operations that work with references

find is an example of an iterator method that works with references instead of values. We can see that in the type definitions for find from the documentation.

 fn find<P>
 (&mut self, predicate: P) -> Option<Self::Item>
 where
    P: FnMut(&Self::Item) -> bool

Compared to say, map:

fn map<B, F>
(self, f: F) -> Map<Self, F>
where
    F: FnMut(Self::Item) -> B

The key part of the type definition for both is that last line; map works on iterator elements directly (Self::Item), whereas find works with references (&Self::Item). The resolution here is appropriate amounts of de-referencing.

Caveats about Copy types

Types that implement the Copy trait doesnt require the explicit kind of cloning we saw in the post earlier. That is down to the Copy trait communcating to the Compiler that the type can be safely copied in memory automatically. It's not any more efficient per se, but it is automatic. I've seen this mostly with numerical types.

Calling It

There is a fair bit more to this, but this post should cover much of what you need to know to get yourself unstuck. If you wanted to do some further reading, Herman J. Radtke III goes into more detail about using iterators effectively here and has put together a fantastic post on the topic.