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

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链接)

error[E0261]: use of undeclared lifetime name `'a`
  --> src/main.rs:23:22
   |
23 |     type Item = Vec<&'a T>;
   |                      ^^ undeclared lifetime

- elszben

---

可能是迭代器返回引用项，生命周期问题的重复问题。 - Chris Morgan

FYI，“loop { match i.next() { ... }}”基本上是“for v in i {}”的语法糖。 - Shepmaster

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

这不是Iterator trait 中有效的next()方法。

这种可以返回对自身引用的迭代器称为流式迭代器。如果需要，您可以在此处、此处 和 此处 找到更多信息。

更新。 但是，您可以从迭代器返回对其他结构体的引用 - 大多数集合迭代器就是这样工作的。示例代码如下：

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

注意现在 impl 块上声明了生命周期参数 'a。这样做是可以的（实际上是必需的），因为您需要在结构体上指定生命周期参数。然后，您可以在 Item 和 next() 返回类型中都使用相同的 'a。再次说明，这就是大多数集合迭代器的工作方式。

- Vladimir Matveev

---

这是否意味着迭代器根本不能返回引用？我不确定我完全理解其含义。你说过迭代器不能返回指向自身的引用。如果我有另一个对象存储状态，而迭代器必须返回该对象的引用，那么我该如何表达其生命周期？ - elszben

@elszben，是可以使用单独的对象来处理状态的。请查看我的更新内容，了解如何在这种情况下编写生命周期。 - Vladimir Matveev

谢谢！我把这个东西切成了两半，现在排列对象持有向量，迭代器具有可变索引向量和对排列的引用，一切都按预期工作 :) - elszben

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]> 而不是 Vec<Vec<&'a T>>。获取容器的引用比构建引用的容器更容易。)

- mdup

---

我希望排列对象拥有持有值的向量，因此我将在那里使用值而不是引用。我不完全理解您限制特定向量仅能添加一次的动机。这有什么用处吗？无论如何，感谢您的努力。这真的帮了我很多，因为有这么多版本得到了实现 :) - elszben

我的建议动机是希望像 Rust 标准库中的其他迭代器一样运作：迭代器会在容器中一次性创建，而不是分几步。例如 myvec.iter()。使用一次后，迭代器就会被消耗，也就是无法再使用。您的 add() 设计似乎与此相反。但这并不一定是坏事 :) - mdup

Answer 3

如其他答案所述，此处称为 流迭代器，它需要 Rust 的 Iterator 不同的保证。一个提供此类功能的 crate 被恰当地称为 streaming-iterator 并提供了 StreamingIterator trait。

下面是实现该 trait 的一个例子：

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的通用关联类型（GATs），流迭代器将受到限制。

- Shepmaster

---

同样的概念也被称为“lending-iterators”，尤其是自从Stream出现以后，使得StreamingIterator有些模糊不清。 - undefined

Answer 4

我不久前写了这段代码，然后偶然发现了这个问题。它完全符合问题的要求：展示如何实现一个迭代器，将其回调函数传递给自身的引用。

它为IntoIterator实例添加了一个.iter_map()方法。最初，我认为应该为Iterator本身实现它，但那是一个不太灵活的设计决策。

我为此创建了一个小型的crate，并将我的代码发布到GitHub上，以便您进行实验，您可以在这里找到它。

关于OP在定义项目寿命方面遇到的麻烦，我在实现时没有遇到任何这样的问题，而是依赖于默认省略的生命周期。

以下是使用示例。请注意，回调接收的参数是迭代器本身，期望回调从中提取数据并将其原样传递或执行其他操作。

 use iter_map::IntoIterMap;

 let mut b = true;

 let s = "hello world!".chars().peekable().iter_map(|iter| {
     if let Some(&ch) = iter.peek() {
         if ch == 'o' && b {
             b = false;
             Some('0')
         } else {
             b = true;
             iter.next()
         }
     } else { None }
 }).collect::<String>();

 assert_eq!(&s, "hell0o w0orld!");

由于IntoIterMap泛型特性已经实现了IntoIterator，因此您可以从支持该接口的任何内容中获取“iter map”。例如，可以直接从数组中创建一个“iter map”，如下所示：

use iter_map::*;

fn main() 
{
    let mut i = 0;

    let v = [1, 2, 3, 4, 5, 6].iter_map(move |iter| {
        i += 1;
        if i % 3 == 0 {
            Some(0)
        } else {
            iter.next().copied()
        }
    }).collect::<Vec<_>>();
 
    assert_eq!(v, vec![1, 2, 0, 3, 4, 0, 5, 6, 0]);
}

这是完整的代码 - 令人惊讶的是，只需要很少的代码就可以实现，而且在组合时一切都似乎非常顺利。它让我对 Rust 本身的灵活性和其设计决策有了新的认识。

/// Adds `.iter_map()` method to all IntoIterator classes.
///
impl<F, I, J, R, T> IntoIterMap<F, I, R, T> for J
//
where F: FnMut(&mut I) -> Option<R>,
      I: Iterator<Item = T>,
      J: IntoIterator<Item = T, IntoIter = I>,
{
    /// Returns an iterator that invokes the callback in `.next()`, passing it
    /// the original iterator as an argument. The callback can return any
    /// arbitrary type within an `Option`.
    ///
    fn iter_map(self, callback: F) -> ParamFromFnIter<F, I>
    {
        ParamFromFnIter::new(self.into_iter(), callback)
    }
}

/// A trait to add the `.iter_map()` method to any existing class.
///
pub trait IntoIterMap<F, I, R, T>
//
where F: FnMut(&mut I) -> Option<R>,
      I: Iterator<Item = T>,
{
    /// Returns a `ParamFromFnIter` iterator which wraps the iterator it's 
    /// invoked on.
    ///
    /// # Arguments
    /// * `callback`  - The callback that gets invoked by `.next()`.
    ///                 This callback is passed the original iterator as its
    ///                 parameter.
    ///
    fn iter_map(self, callback: F) -> ParamFromFnIter<F, I>;
}

/// Implements an iterator that can be created from a callback.
/// does pretty much the same thing as `std::iter::from_fn()` except the 
/// callback signature of this class takes a data argument.
pub struct ParamFromFnIter<F, D>
{
    callback: F,
    data: D,
}

impl<F, D, R> ParamFromFnIter<F, D>
//
where F: FnMut(&mut D) -> Option<R>,
{
    /// Creates a new `ParamFromFnIter` iterator instance.
    ///
    /// This provides a flexible and simple way to create new iterators by 
    /// defining a callback. 
    /// # Arguments
    /// * `data`      - Data that will be passed to the callback on each 
    ///                 invocation.
    /// * `callback`  - The callback that gets invoked when `.next()` is invoked
    ///                 on the returned iterator.
    ///    
    pub fn new(data: D, callback: F) -> Self
    {
        ParamFromFnIter { callback, data }
    }
}

/// Implements Iterator for ParamFromFnIter. 
///
impl<F, D, R> Iterator for ParamFromFnIter<F, D>
//
where F: FnMut(&mut D) -> Option<R>,
{
    type Item = R;
    
    /// Iterator method that returns the next item.
    /// Invokes the client code provided iterator, passing it `&mut self.data`.
    ///
    fn next(&mut self) -> Option<Self::Item>
    {
        (self.callback)(&mut self.data)
    }
}

- Todd