Vector of iterators

help
1

As I get deeper into Rust, I find that I'm having trouble understanding the borrow checker when I combine vecs, mutation, and iterators.

In this example, I'm trying to build a vector of iterators. (The idea is that I can combine them together during the 'merge' phase of a merge sort.)

This code fails to compile, giving the error "borrowed value does not live long enough".

From my POV, the base vectors of i32 live just as long as the iterators created from them. Clearly that's not actually true!

Would any kind soul give me a hint of how I might understand this better?

2

Your problem has nothing to do with iterators at all.

To quote the error verbatim:

<anon>:17:36: 17:49 error: borrowed value does not live long enough
<anon>:17                 foo.vecs.push(&mut s.into_iter());
                                             ^~~~~~~~~~~~~
<anon>:10:7: 21:2 note: reference must be valid for the block suffix following statement 1 at 10:6...
<anon>:10     };
<anon>:11     
<anon>:12     let mut it = seq.iter();
<anon>:13     loop {
<anon>:14         match it.next() {
<anon>:15             None => break,
          ...
<anon>:17:17: 17:51 note: ...but borrowed value is only valid for the statement at 17:16
<anon>:17                 foo.vecs.push(&mut s.into_iter());
                          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
<anon>:17:17: 17:51 help: consider using a `let` binding to increase its lifetime
<anon>:17                 foo.vecs.push(&mut s.into_iter());
                          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

"borrowed value does not live long enough"—the thing you're trying to borrow does not continue to exist for long enough. s.into_iter() results in a temporary value that, because you don't store it anywhere, disappears at the end of the statement. You are trying to store a pointer to this temporary value in a vector which will almost certainly outlive said value. This would be very bad.

You can't just store the temporary, though, because you need to make all the iterators outlive the vector you're storing them in. The simplest solution is to just Box them:

struct Foo<T> {
    vecs: Vec<Box<Iterator<Item=T>>>,
}

fn main() {
    let seq: Vec<Vec<i32>> = vec![vec![0,1], vec![2,3]];
    
    let mut foo = Foo {
        vecs: Vec::new(),
    };
    
    let mut it = seq.into_iter();
    loop {
        match it.next() {
            None => break,
            Some(s) => {
                foo.vecs.push(Box::new(s.into_iter()));
            },
        };
    }
}

Allocating them on the heap avoids the problem entirely. That said, I also had to change seq.iter() to seq.into_iter() because the first was iterating over &Vec<i32>s, which meant the subsequent s.into_iter() was also producing borrowed iterators, which aren't hugely useful in this context. Well, not unless you change it to do this instead:

struct Foo<'a, T> {
    vecs: Vec<Box<Iterator<Item=T>+'a>>,
}

fn main() {
    let seq: Vec<Vec<i32>> = vec![vec![0,1], vec![2,3]];
    
    let mut foo = Foo {
        vecs: Vec::new(),
    };
    
    let mut it = (&seq).into_iter();
    loop {
        match it.next() {
            None => break,
            Some(s) => {
                foo.vecs.push(Box::new(s.into_iter()));
            },
        };
    }
}

Note the explicit lifetime for tracking how long the boxed iterators are valid.

1 Like
3

Cheers! Great explanation, I appreciate it.

4

You should also be able to avoid boxing the iterators, if you only plan to put the same type of iterators into the Vec. For example, if all of your iterators result from calling into_iter() on a Vec<i32>, then they'll all have the same type, std::vec::IntoIter<i32>, and no boxing would be needed.

The main reason you might want to do this is that if you are indeed doing a merge sort, you would probably want the next() calls to be inlined rather than a virtual call, as it should be pretty hot in your code. On the other hand, you lose the ability to merge multiple different types of iterators.

1 Like