iterator - 如何编写返回对自身的引用的迭代器？

Question

我无法表达Iterator 实现的返回值的生命周期。如何在不更改迭代器返回值的情况下编译此代码？我希望它返回一个引用向量。

很明显，我没有正确使用生命周期参数，但在尝试了各种方法后我放弃了，我不知道该怎么做。

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

Answer 1

据我了解，您希望迭代器将引用向量返回到自身中，对吗？不幸的是，这在 Rust 中是不可能的。

这是修剪下来的 Iterator特点:

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

请注意，&mut self 之间没有生命周期连接和 Option<Item> .这意味着 next()方法不能返回对迭代器本身的引用。您只是无法表达返回的引用的生命周期。这基本上就是您找不到指定正确生命周期的方法的原因 - 它看起来像这样:

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

除了这不是一个有效的 next() Iterator 的方法特质。

这样的迭代器(可以将引用返回到自身的迭代器)称为流式迭代器。您可以找到更多 here , here和 here , 如果你愿意的话。

更新。但是，您可以从迭代器返回对某些其他结构的引用 - 这就是大多数集合迭代器的工作方式。它可能看起来像这样:

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>> {
        ...
    }
}

注意生命周期'a现在在 impl 上宣布堵塞。这样做是可以的(实际上是必需的)，因为您需要在结构上指定生命周期参数。然后你可以使用相同的'a都在 Item在next()返回类型。同样，这就是大多数集合迭代器的工作方式。