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

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;
            }
        }
    }
}

(游乐场链接)

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 selfOption<Item>next()

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

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

这些迭代器(可以将引用返回到它们自己的迭代器)称为流迭代器.如果你愿意,你可以在这里,这里和这里找到更多.

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

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块上声明生命周期.可以这样做(事实上是必需的)因为你需要在结构上指定生命周期参数.然后你可以使用相同的'ain Item和next()return类型.同样,这就是大多数集合迭代器的工作方式.

Answer 2

@ VladimirMatveev的答案是正确的,它解释了为什么你的代码无法编译.简而言之,它表示迭代器不能从内部产生借来的值.

但是,它可以从其他东西中产生借来的价值.这是与实现Vec和Iter:在Vec拥有值,并且在Iter刚能中产生的引用的包装Vec.

这是一个实现您想要的设计.迭代器就像Vec和Iter,和实际拥有值的其他容器一样.

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;}
        }
    }
}

(操场)

与您的初始问题无关.如果这只是我,我会确保所有借来的载体都是一次性的.我们的想法是删除重复调用add并直接传递构造中所有借用的向量:

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);
}

(操场)

(编辑:将迭代器设计改为采用Vec<&'a [T]>而不是a Vec<Vec<&'a T>>.使用ref容器比构建refs容器更容易.)

Answer 3

正如其他答案中提到的，这称为流式迭代器，它需要与 Rust 不同的保证Iterator。提供此类功能的一个箱子被恰当地称为流迭代器，它提供了这一StreamingIterator特征。

这是实现该特征的一个示例：

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,
        }
    }
}

不幸的是，在实现 RFC 1598 中的通用关联类型(GAT)之前，流式迭代器将受到限制。