0

So here I wrote the iterator for generating permutations:

pub struct Permutations {
    size: usize,
    arr: Vec<usize>,
}

impl Permutations {
    pub fn new(size: usize) -> Permutations {
        Permutations{
            size: size,
            arr: (0..size).collect::<Vec<_>>(),
        }
    }
}

impl Iterator for Permutations {
    type Item = Vec<usize>;

    fn next(&mut self) -> Option<Self::Item> {
        // some complex code here
        if ok { Some(self.arr.clone()) } else { None }
    }
}

Now, what I want is to not clone the vector each time, and return a constant reference. So I write:

impl Iterator for Permutations {
    type Item = &Vec<usize>;

    fn next(&mut self) -> Option<Self::Item> {
        // some complex code here
        if ok { Some(self.arr.clone()) } else { None }
    }
}

And of course this does not compile, because I need to specify the lifetime. Ok, let's give it a try:

impl<'a> Iterator for Permutations {
    type Item = &'a Vec<usize>;

    fn next(&mut self) -> Option<Self::Item> {
        // some complex code here
        if ok { Some(&self.arr) } else { None }
    }
}

Now I get an error:

error: the lifetime parameter `'a` is not constrained by the impl trait, self type, or predicates

So, I have no idea, what that means, but okay, I guess we need to bind that 'a lifetime to self somehow. After some poking around and fighting with hard-to-understand errors this came out:

use std::marker::PhantomData;

pub struct Permutations<'a> {
    size: usize,
    arr: Vec<usize>,
    p: PhantomData<&'a Vec<usize>>,
}

impl<'a> Permutations<'a> {
    pub fn new(size: usize) -> Permutations<'a> {
        Permutations{
            size: size,
            arr: (0..size).collect::<Vec<_>>(),
            p: PhantomData,
        }
    }
}

impl<'a> Iterator for Permutations<'a> {
    type Item = &'a Vec<usize>;

    fn next(&mut self) -> Option<Self::Item> {
        // some complex code here
        if ok { Some(&self.arr) } else { None }
    }
}

But again there's an error, though kinda understandable one:

error: cannot infer an appropriate lifetime for borrow expression due to conflicting requirements
    return Some(&self.arr);
help: consider using an explicit lifetime parameter as shown: fn next(&'a mut self) -> Option<Self::Item>

Okay! That is surprisingly actually useful! Let's add the explicit lifetime:

impl<'a> Iterator for Permutations<'a> {
    type Item = &'a Vec<usize>;

    fn next(&'a mut self) -> Option<Self::Item> {
        // some complex code here
        if ok { Some(&self.arr) } else { None }
    }
}

Bam! Just as I thought: not useful at all.

error: method `next` has an incompatible type for trait: expected bound lifetime parameter , found concrete lifetime

Sooo... yeah. How do I do this simpliest thing in the world?

monnoroch
  • 390
  • 1
  • 10
  • It is a well known limitation that you cannot usefully yield iterator elements that borrow from the iterator itself. Standard solutions: 1) Split iterator's data from the iterator itself. 2) Use a custom `next()` method that is not tied to the iterator trait. – bluss Jun 30 '15 at 11:36
  • This is a standard problem people experience—the design of `Iterator` is for separate iterator objects, not to mutate the source object. – Chris Morgan Jun 30 '15 at 11:36
  • @ChrisMorgan But I dont mutate the source object! I only mutate the iterator object. I do not even have the source object. – monnoroch Jun 30 '15 at 11:38
  • @bluss If I move array out of the iterator, than, since iterator has to mutate it, I will need a mutable reference. Therefore, I cannot return an immutable reference to that array. And this is the problem ChrisMorgan has addressed, I think. – monnoroch Jun 30 '15 at 11:40
  • 1
    @monnoroch: rather, you are mutating the source object and do not have an iterator object. When returning references, the source object is what you return references to the contents of. – Chris Morgan Jun 30 '15 at 11:53
  • 1
    If you accept a generic iterator, then you can expect, for a sufficiently-long iterator, `let foo = iterator.next(); let bar = iterator.next()` to work (needed for eg. `iterator.peek()`). Thus, multiple results must be able to be referenced at once. You can circumvent this with interior mutability, but that's not particularly user-friendly. I suggest using a different trait. – Veedrac Jul 01 '15 at 00:41

0 Answers0