Lifetime issue in iterator

I am trying to implement an iterator for one of my structs. This works until I return references.

Here is a MWE illustrating the problem:

struct Foo {
    n: usize,
}

impl Foo {
    pub fn new(n: usize) -> Self {
        Self { n, }
    }
}

struct FooIter<'a> {
    foo: &'a Foo,
    data: usize,
}

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

    fn next(&mut self) -> Option<Self::Item> {
        if self.data == self.foo.n {
            return None;
        }
        self.data += 1;
        return Some(&self.data);    // <== lifetime problem here
    }
}

impl<'a> IntoIterator for &'a Foo {
    type Item = &'a usize;
    type IntoIter = FooIter<'a>;
    fn into_iter(self) -> Self::IntoIter {
        FooIter {
            foo: self,
            data: 0,
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test() {
        for n in Foo::new(5).into_iter() {
            println!("{:?}", n);
        }
    }
}

The error I get is:

error: lifetime may not live long enough
   --> src/xxxxx.rs:154:16
    |
144 | impl<'a> Iterator for FooIter<'a> {
    |      -- lifetime `'a` defined here
...
147 |     fn next(&mut self) -> Option<Self::Item> {
    |             - let's call the lifetime of this reference `'1`
...
154 |         return Some(&self.data);
    |                ^^^^^^^^^^^^^^^^ method was supposed to return data with lifetime `'a` but it is returning data with lifetime `'1`

I then tried to specify a lifetime for &mut self, but that did not work either.

How can I solve this issue?

Is your iterator returning &usize in the wild too or just in your example? Because copying your usize is almost certainly a better idea than returning &usize.

1 Like

What you trying to implement looks like a lending iterator (your iterator owns data field and tries to lend it) it's not possible with Iterator trait.

https://rust-lang.github.io/generic-associated-types-initiative/design_patterns/iterable.html

To solve it - you need to move the ownership for data out of the iterator.

This is just a simple example. What I have in reality is a vector of a more complex structure. My iterator works when I return data.clone(), but since I use it read-only I would like to avoid the costs of copying and allocating, in particular since I will iterate over very long sequences.

I tried moving 'data' into 'Foo', but then I need to store a mutable reference in FooIterator, and this does not work either.

RefCell might help with that...

Generally there are two options:

  • you yield copies/clones of the data
  • you yield references that you aren't going to mutate/have mutable access to

In this case you are mutating self.data (and you'll also have mutable access to it through the &mut self parameter the next time next is called), so you must copy it.

In your real case with a vector we don't have enough information to say for certain if you satisfy the conditions to avoid copying/cloning.

You also have the option to not implement Iterator, and instead just provide your own next method where the returned reference does borrow from the &mut self parameter.

RefCell works when the borrowing does respect the rules, but there's no way to tell that to the compiler. Here the borrowing doesn't seem to respect the rules, so it won't work.

To be more specific, what I am trying to implement is a method that delivers all k-subsets of an n-set.

Basically, I have e.g. a call to CombN::new(6,3) which then, using an iterator, allows me to iterate over all subsets of size 3 of a set of size 6. In the example, it would generate the following sequence:

[0,1,2]
[0,1,3]
[0,1,4]
[0,1,5]
[0,2,3]
[0,2,4]
[0,2,5]
...
[3.4.5]

In this case, there are just 20 combinations. But with larger numbers, there easily are very long sequences, potentially with millions of combinations. This is the reason I want to avoid allocating short vectors that I use only very briefly.

Of course there are other solutions to this, like updating a vector argument (the subset) which passed as mutable reference, but somehow I liked the iterator pattern and tried to implement it.

Then what I said stands, you cannot implement Iterator. Just to give yet another example, with an Iterator you must be able to collect all the items in a Vec, but of course you can't do that if you reuse the same Vec for the items.

Just to finish this thread, I ended up with the solution below. There is a non-iterator variant that returns refs (next_as_ref), and an iterator that building on this function and clones the refs. With that I have both options.

Comments on improvements are welcome!

(The algorithm is an adaptation of some Fortran code I found... I really hate array indices that start at 1 :wink: )


pub struct CombN {
    n: usize,
    k: usize,
    val: usize,       // value to start counting upwards
    pos: usize,       // data, from right, starting at 1
    data: Vec<usize>
}

impl CombN {
    pub fn new(n: usize, k: usize) -> Self {
        assert!(n >= k && k > 0);
        Self {
            n,
            k,
            val: 0,
            pos: n,
            data: vec![n; k]
        }
    }

    pub fn next_as_ref(&mut self) -> Option<&Vec<usize>> {

        // constants, less typing...
        let n = self.n;
        let k = self.k;

        // check for end flag
        if self.pos == 0 {
            return None;
        }
        // check for end flag
        if self.pos == n {
            self.val = 0;
            self.pos = k;
        } else {
            if self.val < n - self.pos {
                // stay at very right
                self.pos = 1;
            } else {
                // otherwise move one position leftwards
                self.pos += 1;
            }
            // next value is one higher than current one
            self.val = self.data[k - self.pos] + 1;
        }
        // fill sequence to the right (just one value if at right)
        for j in 1..=self.pos {
            self.data[k + j - 1 - self.pos] = self.val + j - 1;
        }
        // check if this was tha last value, if yes, set flag
        if self.data[0] == n - k {
            self.pos = 0; // last iteration !
        }
        Some(&self.data)
    }
}

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

    fn next(&mut self) -> Option<Self::Item> {
        if self.next_as_ref().is_some() {
            Some(self.data.clone())
        } else {
            None
        }
    }
}


#[cfg(test)]
mod tests {
    use super::*;
    use std::assert_eq;
    use rstest::rstest;
    use regex::Regex;

    // helper to pass vec of vec into rstest
    fn string_to_vecvec_usize(arg: &String) -> Vec<Vec<usize>> {
        let subvecs = Regex::new(r"\[(.+?)\]").unwrap();
        subvecs.captures_iter(arg).map(
            |x| {
                x.get(1).unwrap().as_str()
                    .split(",")
                    .map(|x| x.trim().parse::<usize>().unwrap()).collect()
            }).collect()
    }

    #[rstest]
    #[case((5, 3), "[0, 1, 2], [0, 1, 3], [0, 1, 4], [0, 2, 3], [0, 2, 4],
                    [0, 3, 4], [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]")]
    #[case((4, 1), "[0], [1], [2], [3]")]
    #[case((4, 4), "[0, 1, 2, 3]")]
    fn test1(#[case] input: (usize, usize),#[case] expected: String ) {
        let expected = string_to_vecvec_usize(&expected);
        let (n, k) = input;
        let c = CombN::new(n, k);
        let series : Vec<_> = c.into_iter().collect();
        assert_eq!(series, expected);
    }
}

2 Likes