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.

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,
        }
    }
}