How to return a reference when implementing an iterator?

Question

I would like to return a reference to an owned object that is in a collection (viz., a Vec), but I cannot seem to get the lifetimes correct. Here is what I first tried:

struct StringHolder {
    strings: Vec<String>,
    i: usize,
}

impl Iterator for StringHolder {
    type Item<'a> = &'a String;
    fn next(&mut self) -> Option<Self::Item> {
        if self.i >= self.strings.len() {
            None
        } else {
            self.i += 1;
            Some(&self.strings[self.i])
        }
    }
}

fn main() {
    let sh = StringHolder { strings: vec![], i: 0 };
    for string in sh {
        println!("{}", string);
    }
}

I get an error that generic associated types are unstable and lifetimes do not match type in trait. I tried a few other iterations, but nothing seemed to work.

I gather that this may not be possible based on some things I've read, but then I can't seem to figure out how Vec does it itself. For example, I can use the following to simply iterate over the underlying Vec and return a reference on each iteration:

struct StringHolder {
    strings: Vec<String>,
}

impl<'a> IntoIterator for &'a StringHolder {
    type Item = &'a String;
    type IntoIter = ::std::slice::Iter<'a, String>;
    fn into_iter(self) -> Self::IntoIter {
        (&self.strings).into_iter()
    }
}

fn main() {
    let sh = StringHolder { strings: vec!["A".to_owned(), "B".to_owned()] };
    for string in &sh {
        println!("{}", string);
    }
}

So that makes me think it is possible, I just haven't figured out lifetimes yet. Thanks for your help.

Session

Iterator doesn't allow the lifetime of its Items to vary with the lifetime of the self, but in your case the items are stored in the iterator and share its lifetime, so that's just not going to work. Vec does nothing like what you're trying to do. Iterators should be separate from containers. – Spillway

Does this answer your question? Iterator lifetime issue when returning references to inner collection – Tillion

Answer 1

The Iterator trait doesn't include a lifetime for Item, which is one of the errors you are seeing. The other alludes to GATs which was an unstable Rust feature when this question was originally asked. GATs applied to this example would let you bound the lifetime of an item for each individual call to next() instead of all items having the same lifetime. Having said that, the Iterator trait is unlikely to change so this more flexible behaviour would have to be a new trait.

Given the design of the Iterator trait, you can't have an iterator own its data and at the same time have its Item be a reference to it. There just isn't a way to express the lifetime.

The way iterators are usually written, in order to have the items be references, is to make them hold a reference to the underlying data. This provides a named lifetime for the data, which can be used on the associated Item. Vec sort of does this, but it's a bit different because Vec actually gets its iteration from slice.

Your complete example:

struct StringHolder {
    strings: Vec<String>,
}

struct StringHolderIter<'a> {
    string_holder: &'a StringHolder,
    i: usize,
}

impl<'a> Iterator for StringHolderIter<'a> {
    type Item = &'a str;
    fn next(&mut self) -> Option<Self::Item> {
        if self.i >= self.string_holder.strings.len() {
            None
        } else {
            self.i += 1;
            Some(&self.string_holder.strings[self.i - 1])
        }
    }
}

impl<'a> IntoIterator for &'a StringHolder {
    type Item = &'a str;
    type IntoIter = StringHolderIter<'a>;
    fn into_iter(self) -> Self::IntoIter {
        StringHolderIter {
            string_holder: self,
            i: 0,
        }
    }
}

Caesarea

how would we do this now that GATs have stabilized? – Bedspring

@Bedspring I would still do it this way. GATs don't change much here - unless the problem required something like a streaming iterator. – Caesarea

This was an amazingly helpful response thank you very much! – Overcheck

That doesn't work for mutable iterators, though. For that, you need to manually transmute &mut to &'a mut, even though the returned value is technically already a &'a mut. – Antemortem