By elszben


2015-05-24 09:54:03 8 Comments

I am having trouble expressing the lifetime of the return value of an Iterator implementation. How can I compile this code without changing the return value of the iterator? I'd like it to return a vector of references.

It is obvious that I am not using the lifetime parameter correctly but after trying various ways I just gave up, I have no idea what to do with it.

use std::iter::Iterator;

struct PermutationIterator<T> {
    vs: Vec<Vec<T>>,
    is: Vec<usize>,
}

impl<T> PermutationIterator<T> {
    fn new() -> PermutationIterator<T> {
        PermutationIterator {
            vs: vec![],
            is: vec![],
        }
    }

    fn add(&mut self, v: Vec<T>) {
        self.vs.push(v);
        self.is.push(0);
    }
}

impl<T> Iterator for PermutationIterator<T> {
    type Item = Vec<&'a T>;
    fn next(&mut self) -> Option<Vec<&T>> {
        'outer: loop {
            for i in 0..self.vs.len() {
                if self.is[i] >= self.vs[i].len() {
                    if i == 0 {
                        return None; // we are done
                    }
                    self.is[i] = 0;
                    self.is[i - 1] += 1;
                    continue 'outer;
                }
            }

            let mut result = vec![];

            for i in 0..self.vs.len() {
                let index = self.is[i];
                result.push(self.vs[i].get(index).unwrap());
            }

            *self.is.last_mut().unwrap() += 1;

            return Some(result);
        }
    }
}

fn main() {
    let v1: Vec<_> = (1..3).collect();
    let v2: Vec<_> = (3..5).collect();
    let v3: Vec<_> = (1..6).collect();

    let mut i = PermutationIterator::new();
    i.add(v1);
    i.add(v2);
    i.add(v3);

    loop {
        match i.next() {
            Some(v) => {
                println!("{:?}", v);
            }
            None => {
                break;
            }
        }
    }
}

(Playground link)

error[E0261]: use of undeclared lifetime name `'a`
  --> src/main.rs:23:22
   |
23 |     type Item = Vec<&'a T>;
   |                      ^^ undeclared lifetime

3 comments

@Shepmaster 2018-04-06 02:46:15

As mentioned in other answers, this is called a streaming iterator and it requires different guarantees from Rust's Iterator. One crate that provides such functionality is aptly called streaming-iterator and it provides the StreamingIterator trait.

Here is one example of implementing the trait:

extern crate streaming_iterator;

use streaming_iterator::StreamingIterator;

struct Demonstration {
    scores: Vec<i32>,
    position: usize,
}

// Since `StreamingIterator` requires that we be able to call
// `advance` before `get`, we have to start "before" the first
// element. We assume that there will never be the maximum number of
// entries in the `Vec`, so we use `usize::MAX` as our sentinel value.
impl Demonstration {
    fn new() -> Self {
        Demonstration {
            scores: vec![1, 2, 3],
            position: std::usize::MAX,
        }
    }

    fn reset(&mut self) {
        self.position = std::usize::MAX;
    }
}

impl StreamingIterator for Demonstration {
    type Item = i32;

    fn advance(&mut self) {
        self.position = self.position.wrapping_add(1);
    }

    fn get(&self) -> Option<&Self::Item> {
        self.scores.get(self.position)
    }
}

fn main() {
    let mut example = Demonstration::new();

    loop {
        example.advance();
        match example.get() {
            Some(v) => {
                println!("v: {}", v);
            }
            None => break,
        }
    }

    example.reset();

    loop {
        example.advance();
        match example.get() {
            Some(v) => {
                println!("v: {}", v);
            }
            None => break,
        }
    }
}

Unfortunately, streaming iterators will be limited until generic associated types (GATs) from RFC 1598 are implemented.

@mdup 2015-05-24 11:43:15

@VladimirMatveev's answer is correct in how it explains why your code cannot compile. In a nutshell, it says that an Iterator cannot yield borrowed values from within itself.

However, it can yield borrowed values from something else. This is what is achieved with Vec and Iter: the Vec owns the values, and the the Iter is just a wrapper able to yield references within the Vec.

Here is a design which achieves what you want. The iterator is, like with Vec and Iter, just a wrapper over other containers who actually own the values.

use std::iter::Iterator;

struct PermutationIterator<'a, T: 'a> {
    vs : Vec<&'a [T]>,
    is : Vec<usize>
}

impl<'a, T> PermutationIterator<'a, T> {
    fn new() -> PermutationIterator<'a, T> { ... }

    fn add(&mut self, v : &'a [T]) { ... }
}

impl<'a, T> Iterator for PermutationIterator<'a, T> {
    type Item = Vec<&'a T>;
    fn next(&mut self) -> Option<Vec<&'a T>> { ... }
}

fn main() {
    let v1 : Vec<i32> = (1..3).collect();
    let v2 : Vec<i32> = (3..5).collect();
    let v3 : Vec<i32> = (1..6).collect();

    let mut i = PermutationIterator::new();
    i.add(&v1);
    i.add(&v2);
    i.add(&v3);

    loop {
        match i.next() {
            Some(v) => { println!("{:?}", v); }
            None => {break;}
        }
    }
}

(Playground)


Unrelated to your initial problem. If this were just me, I would ensure that all borrowed vectors are taken at once. The idea is to remove the repeated calls to add and to pass directly all borrowed vectors at construction:

use std::iter::{Iterator, repeat};

struct PermutationIterator<'a, T: 'a> {
    ...
}

impl<'a, T> PermutationIterator<'a, T> {
    fn new(vs: Vec<&'a [T]>) -> PermutationIterator<'a, T> {
        let n = vs.len();
        PermutationIterator {
            vs: vs,
            is: repeat(0).take(n).collect(),
        }
    }
}

impl<'a, T> Iterator for PermutationIterator<'a, T> {
    ...
}

fn main() {
    let v1 : Vec<i32> = (1..3).collect();
    let v2 : Vec<i32> = (3..5).collect();
    let v3 : Vec<i32> = (1..6).collect();
    let vall: Vec<&[i32]> = vec![&v1, &v2, &v3];

    let mut i = PermutationIterator::new(vall);
}

(Playground)

(EDIT: Changed the iterator design to take a Vec<&'a [T]> rather than a Vec<Vec<&'a T>>. It's easier to take a ref to container than to build a container of refs.)

@elszben 2015-05-24 14:52:29

I want the Permutation object to own the vectors that hold the values, so I'll use values instead of refs there. I don't fully understand your motivation to limit that a specific vector can only be added once. Why is that useful? Anyway, thanks for the effort. It really helped me that so many versions got implemented:)

@mdup 2015-05-24 15:02:33

The motivation for my suggestion was to behave like other iterators in Rust's stdlib: the iterator is created all at once over the container, not in several steps. (e.g myvec.iter()). After one use, the iterator becomes consumed, i.e. unusable. Your add() design suggests the opposite. But that's not necessarily a bad thing :)

@Vladimir Matveev 2015-05-24 10:56:26

As far as I understand, you want want the iterator to return a vector of references into itself, right? Unfortunately, it is not possible in Rust.

This is the trimmed down Iterator trait:

trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Item>;
}

Note that there is no lifetime connection between &mut self and Option<Item>. This means that next() method can't return references into the iterator itself. You just can't express a lifetime of the returned references. This is basically the reason that you couldn't find a way to specify the correct lifetime - it would've looked like this:

fn next<'a>(&'a mut self) -> Option<Vec<&'a T>>

except that this is not a valid next() method for Iterator trait.

Such iterators (the ones which can return references into themselves) are called streaming iterators. You can find more here, here and here, if you want.

Update. However, you can return a reference to some other structure from your iterator - that's how most of collection iterators work. It could look like this:

pub struct PermutationIterator<'a, T> {
    vs: &'a [Vec<T>],
    is: Vec<usize>
}

impl<'a, T> Iterator for PermutationIterator<'a, T> {
    type Item = Vec<&'a T>;

    fn next(&mut self) -> Option<Vec<&'a T>> {
        ...
    }
}

Note how lifetime 'a is now declared on impl block. It is OK to do so (required, in fact) because you need to specify the lifetime parameter on the structure. Then you can use the same 'a both in Item and in next() return type. Again, that's how most of collection iterators work.

@elszben 2015-05-24 11:19:28

Does this mean that the iterator cannot return references, at all? I am not sure I fully understand the implications. You said that the iterator cannot return a reference into itself. What if I have another object storing the state and the iterator has to return reference into that object? How do I express the lifetime in that case?

@Vladimir Matveev 2015-05-24 12:03:15

@elszben, yes, it is possible to do the thing with a separate object for state. Please see my update on how to write lifetimes out in this case.

@Vladimir Matveev 2015-05-24 12:05:23

Unfortunately I'm now in a hurry and can't fix your code in this manner entirely, but hopefully the above example would give you some hints. I'll update the answer later if needed.

@elszben 2015-05-24 14:53:45

Thank you! I cut the thing into two pieces, now the Permutation object holds the vectors and the iterator has the mutable indices vector and a ref to the permutation and everything works as expected:)

Related Questions

Sponsored Content

12 Answered Questions

[SOLVED] What exactly are iterator, iterable, and iteration?

5 Answered Questions

[SOLVED] How to iterate through two lists in parallel?

10 Answered Questions

[SOLVED] Difference between Python's Generators and Iterators

6 Answered Questions

[SOLVED] How to convert an iterator to a stream?

  • 2014-07-01 13:05:15
  • gontard
  • 190253 View
  • 436 Score
  • 6 Answer
  • Tags:   java iterator java-8

9 Answered Questions

[SOLVED] Build a Basic Python Iterator

5 Answered Questions

[SOLVED] Iterator invalidation rules

1 Answered Questions

[SOLVED] Mutable borrow in a loop

2 Answered Questions

[SOLVED] Iterator returning a reference to itself

Sponsored Content