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.

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. — HTNW
– HTNW, Commented Aug 1, 2021 at 0:49
Does this answer your question? Iterator lifetime issue when returning references to inner collection — Kevin Reid
– Kevin Reid, Commented Aug 1, 2021 at 1:16

Peter Hall · Accepted Answer · 2023-05-29 20:56:34Z

19

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

edited May 29, 2023 at 20:56

answered Aug 1, 2021 at 2:49

Peter Hall

59.7k17 gold badges168 silver badges229 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

avi Over a year ago

how would we do this now that GATs have stabilized?

Peter Hall Over a year ago

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

Jon Forhan Over a year ago

This was an amazingly helpful response thank you very much!

RedGlyph Over a year ago

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.

Collectives™ on Stack Overflow

How to return a reference when implementing an iterator?

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related