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.
Remember that iterators are lazy, so this iterator:
self.it = Box::new(sub_items.iter().cloned());
Borrowssub_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:
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.
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.
@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?
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
...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.
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:
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 ifSortedSet can also produce owning iterators.
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!!!
