How to write an iterator that returns references to itself?

I'm implementing Iterator for an custom type, which returns references to itself:

struct Iter<'a, T> {
    buf: Vec<&'a T>,
    // ...
}

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

    fn next(&mut self) -> Option<Self::Item> {
        if true /* predict */ {
            // ...
            Some(&self.buf)
        } else {
            None
        }
    }
}

But I got an error:

error[E0495]: cannot infer an appropriate lifetime for borrow expression due to conflicting requirements

   |
8  |       fn next(&mut self) -> Option<Self::Item> {
   |  ______________________________________________^
9  | |         if true /* predict */ {
10 | |             Some(&self.buf)
11 | |         } else {
12 | |             None
13 | |         }
14 | |     }
   | |_____^
note: expected `<Iter<'a, T> as Iterator>`
              found `<Iter<'_, T> as Iterator>`

How to implement correctly?

You can't. The signature of Iterator::next() doesn't allow that.


Your immediate problem in the above code snippet is that you claim to be returning a &'a Vec<&'a T>, but your struct itself stores the Vec. This means that in order for the returned reference to have lifetime 'a, the reference to the struct itself would have to have that lifetime, i.e. &'a mut self. However, that can't be the case, because the lifetime of the struct is what it is, and no amount of lifetime annotations can change that – it will never be the same as 'a for an arbitrary, caller-specified lifetime 'a.

Generally, a borrowing iterator should not try to own the buffer it is borrowing from. You should store a &'a [T] instead of a Vec<&'a T>.

1 Like

What I'm intending to do is to create an iterator that iterates all fixed-length-subset of a vector.

It iterates over &Vec other than owned data Vec to avoid extra memory allocation. So, the Iter has a buffer to store data and the buffer (Vec<T>) should be owned by Iter, I think.

Is there any way to achieve this?

By "subset", do you mean chunks() or windows()?

2 Likes

One unconventional option is to use Item=Rc<Vec<&'a T>>, and call Rc::make_mut() inside your next() function. This will avoid allocations in the common case that the caller drops one result before getting the next one, but will allocate and clone the buffer if they do.

6 Likes

You remind me to use Rc, but I think changing the type of buf to Rc<Vec<&'a T>> in addition could be better :grinning:

No. Both chunks() and windows() return only a part of all fixed-length-subsets.

For example, given a set [1, 2, 3, 4], its all possible subsets of length 2 are:

[1, 2]
[1, 3],
[1, 4],
[2, 3],
[2, 4],
[3, 4],

But by using chunks() you will get collections like

[1, 2], [3, 4]

and by using windows() you will get collections like

[1, 2], [2, 3] [3, 4]

It's impossible to return a reference to something that's not stored. In particular, it's impossible to return a reference to disjoint part of slice, since, e.g., there's no [1, 4] in [1, 2, 3, 4].

1 Like

In that case, you will need to return an owned array or Vec of references to the given elements, since, as @Cerber-Ursi pointed out, there is no way to return a non-contiguous subslice directly.

Here is a Playground that demonstrates both techniques

  • an iterator that supports dynamically-sized subsets at the cost of allocating a vector; and
  • an iterator that knows the cardinality of the subset at compile time, and returns an array without any heap allocation.
6 Likes