Iterator in struct Pointing to Vec in Same Struct

help
#1

I'm looking to create an iterator that iterates over all the sub-vecs in a vec. My actual code is a bit more complex than this, but the below is a small repro of my issue:

struct MyIt {
    items: Vec<Vec<u64>>,
    cur_item: usize,
    it: Box<dyn Iterator<Item=u64>>
}

impl Iterator for MyIt {
    type Item = u64;
    
    fn next(&mut self) -> Option<Self::Item> {
        let mut next = self.it.next();
        
        while next.is_none() {
            self.cur_item += 1;
            
            if self.cur_item >= self.items.len() {
                return None;
            }
            
            let sub_items = self.items[self.cur_item].clone();

            self.it = Box::new(sub_items.iter().cloned());
            next = self.it.next();
        }
        
        next
    }
}

it "points" into the same struct, but when I try to compile this, I get the following error:

error[E0597]: `sub_items` does not live long enough
  --> src/lib.rs:24:32
   |
24 |             self.it = Box::new(sub_items.iter().cloned());
   |                       ---------^^^^^^^^^^^^^^^^----------
   |                       |        |
   |                       |        borrowed value does not live long enough
   |                       cast requires that `sub_items` is borrowed for `'static`
25 |             next = self.it.next();
26 |         }
   |         - `sub_items` dropped here while still borrowed

I'm unsure how to convince the compiler that what that iterator points to won't ever go away, as it's contained in the same struct. I think I need to do something with lifetimes, but am unsure exactly what.

Playground can be found here: Rust Playground

#2

Remember that iterators are lazy, so this iterator:

self.it = Box::new(sub_items.iter().cloned());

Borrows sub_items (check the signature of iter), and thus the iterator as a whole can only live for as long as sub_items. But that's a local variable -- it will drop at the end of next.

The error is somewhat indirect (see below), but the upshot is that you need an iterator that owns the items it is returning. Fortunately there is one readily available:

-            self.it = Box::new(sub_items.iter().cloned());
+            self.it = Box::new(sub_items.into_iter());

Playground.

Further notes:

  • If your field is private like in the example, it wouldn't be a publicly breaking change to alter its type, and you could avoid the Box by storing the owning iterator directly.
  • The full type of the Box, incidentally, is
    Box<dyn Iterator<Item=u64> + 'static>
    But the borrowing iterator's type is std::slice::Iter<'a, u64>, which can't meet the static bound. The type erasure of dyn and implicit lifetime it has in the Box are what made the error so indirect.
  • You may want to consider a struct that borrows a &[Vec<u64>] and iterates over the contents without cloning.
#3

Incidentally, if this was true -- if it contained references into items, say -- then MyIt would be a self-referential data structure, which is almost always something to avoid in Rust. You can't make a useful one without unsafe or perhaps some weak pointer shenanigans (or a crate to do it for you, hopefully soundly). You've avoided this by cloning each inner Vec. A borrowing iterator (where the Vecs are held by something else) would be another way. Just using indices to track your location would be a third. Modifying the data as you go to implicitly track your location would be a fourth.

#4

@quinedot thanks for the thorough reply! As I mentioned, my exact code is more complex. I'm not actually iterating over Vec<Vec<u64>>... it's Vec<MyStruct>. I have an iterator for MyStruct that produces u64; however, for very similar reason, I have not implemented IntoIterator for MyStruct. In looking at how Vec does this, it seems non-trivial: mod.rs - source

I understand that sub_items drops while .iter() is borrowing it... so then why doesn't this work?

            self.it = Box::new(self.items[self.cur_item].iter().cloned());

I'm not creating a temp that will drop, just borrowing from my struct... yet I still get:

error[E0759]: `self` has an anonymous lifetime `'_` but it needs to satisfy a `'static` lifetime requirement
  --> src/lib.rs:22:32
   |
12 |     fn next(&mut self) -> Option<Self::Item> {
   |             --------- this data with an anonymous lifetime `'_`...
...
22 |             self.it = Box::new(self.items[self.cur_item].iter().cloned());
   |                                ----------^^^^^^^^^^^^^^^
   |                                |
   |                                ...is used and required to live as long as `'static` here

Complete playground here: Rust Playground

Why is self.items[self.cur_item] required to live as long as 'static?

#5

Yea, so this gets at the heart of it... I think I need a self-referential structure for my actual type... much like how Vec does it for .into_iter() :frowning:

#6

Well, your Box still has that implicit 'static bound, but making it non-'static won't actually help...

...because yeah, now your iterator is trying to be self-referential.

Probably more details are needed to make headway here. As a start,

  • Is it okay for MyIt to consume the contents, or do you need the contents to persist after the iteration is complete?
  • Is your iterator for MyStruct owning or borrowing?

Or just share a more complete example if possible.

Note that even in the case of Vec and IntoIter (which is highly optimized), the iterator is a different type than Vec itself. Just throwing that out there in case you're trying to implement Iterator on your type directly.

#7

Thanks!

#8

Here's how I'd turn that into a borrowing iterator.

I'll walk through it some.

The only thing SortedSet is offering is a borrowing iterator:

    pub fn iter(&self) -> Box<(dyn Iterator<Item=u64> + '_)> {

The '_ in there means that the more explicit signature is:

    pub fn iter<'a>(&'a self) -> Box<(dyn Iterator<Item=u64> + 'a)> {

So, if we want to make use of that, we need to be able to store the borrowed iterator in MyIt too, which means keeping track of the lifetime:

struct MyIt<'borrowed> {
//         ^^^^^^^^^^^
    items: Vec<SortedSet>,
    cur_item: usize,
    it: Box<dyn Iterator<Item=u64> + 'borrowed>
    //                             ^^^^^^^^^^^
}

And because of the self-referencials-are-problematic bit, it can't be pointing to something we own, so MyIt is going to have to be a borrowing iterator too -- it's going to need to borrow what actually owns the data:

struct MyIt<'borrowed> {
    items: &'borrowed [SortedSet],
    //     ^^^^^^^^^^ ^         ^
    cur_item: usize,
    it: Box<dyn Iterator<Item=u64> + 'borrowed>
}

And then I just proceeded from there. I happened to throw out your cur_item tracker and I used a slice instead of a &Vec<SortedSet>, but you could do it with indicies and &Vec<SortedSet> too.

An owning iterator would also be possible if SortedSet can also produce owning iterators.

#9

Oops, I just spotted one more thing:

             // Make an iterator out of `next_set`
-            Box::new(self.it = next_set.iter());
+            self.it = next_set.iter();

SortedSet::iter already returns a Box<dyn ...> so there's no need to box it up in another Box.

1 Like
#10

That did it... thank you very much!!!

Also learned a few cool things:

  • Didn't know ? worked on functions that returned Option as well as Result... super-handy!
  • The split_first is a nice touch...
  • ... and of course specifying the lifetimes all the way through! I knew there had to be a way to inform the compiler that the lifetime of my iterator (Box<dyn Iterator<Item=u64> + '_>) was valid as it pointed to the same struct.

Not sure I could have gotten there on my own, so very much appreciated!!!

1 Like