iterator - 在 Rust 中实现自定义迭代器时的无限循环

Question

我正在尝试实现一个列表 zipper .到目前为止，我有:

#[derive(RustcDecodable, RustcEncodable, Debug, Clone)]
pub struct ListZipper {
    pub focus: Option<Tile>,
    pub left: VecDeque<Tile>,
    pub right: VecDeque<Tile>,
}

impl PartialEq for ListZipper {
    fn eq(&self, other: &ListZipper) -> bool {
        self.left == other.left && self.focus == other.focus && self.right == other.right
    }
}

我现在正在尝试实现一个迭代器

impl Iterator for ListZipper {
    type Item = Tile;

    fn next(&mut self) -> Option<Tile> {
        self.left.iter().chain(self.focus.iter()).chain(self.right.iter()).next().map(|w| *w)                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
    }
}

在我看来，这是有道理的。遍历 ListZipper 时，我想遍历 left，然后是 focus，然后是 right。所以我将这些迭代器链接起来，然后返回 next()。

如果 ListZipper 中的所有字段都是空的，这会很好地工作。一旦一个不为空，迭代 ListZipper 就会导致无限循环。

问题不在于链。如果我用例如替换它self.left.iter()，并且left不为空，问题是一样的。 focus 和 right 也是如此。

我尝试打印迭代器中的所有元素，它似乎从前到后通过 VecDeque，然后卡住了。 IE。 next() 光标到达后面时不会前进。

为什么？

我意识到我可能不希望 ListZipper 本身成为一个迭代器，但那是另一个讨论。

Answer 1

如评论中所述，您的迭代器缺少一个关键的状态:它在迭代中进行了多远。每次调用 next 时，它都会从头开始构建另一个迭代器并获取第一个元素。

这是一个简化的例子:

struct ListZipper {
    focus: Option<u8>,
}

impl Iterator for ListZipper {
    type Item = u8;

    fn next(&mut self) -> Option<Self::Item> {
        self.focus.iter().next().cloned()
    }
}

fn main() {
    let lz = ListZipper { focus: Some(42) };
    let head: Vec<_> = lz.take(5).collect();
    println!("{:?}", head); // [42, 42, 42, 42, 42]
}

I realize I may not want ListZipper itself to be an iterator, but that is another discussion.

不，真的不是^_^。您需要以某种方式改变正在迭代的事物，以便它可以更改并为每个后续调用具有不同的值。

如果要返回现有迭代器和迭代器适配器的组合，请参阅 Correct way to return an Iterator?获取说明。

否则，您需要在调用 next 期间以某种方式更改 ListZipper:

impl Iterator for ListZipper {
    type Item = Tile;

    fn next(&mut self) -> Option<Self::Item> {
        if let Some(v) = self.left.pop_front() {
            return Some(v);
        }

        if let Some(v) = self.focus.take() {
            return Some(v);
        }

        if let Some(v) = self.right.pop_front() {
            return Some(v);
        }

        None
    }
}

更简洁:

impl Iterator for ListZipper {
    type Item = Tile;

    fn next(&mut self) -> Option<Self::Item> {
        self.left.pop_front()
            .or_else(|| self.focus.take())
            .or_else(|| self.right.pop_front())
    }
}

---

请注意，您的 PartialEq 实现似乎与自动派生的相同...

use std::collections::VecDeque;

type Tile = u8;

#[derive(Debug, Clone, PartialEq)]
pub struct ListZipper {
    pub focus: Option<Tile>,
    pub left: VecDeque<Tile>,
    pub right: VecDeque<Tile>,
}

impl Iterator for ListZipper {
    type Item = Tile;

    fn next(&mut self) -> Option<Self::Item> {
        self.left.pop_front()
            .or_else(|| self.focus.take())
            .or_else(|| self.right.pop_front())
    }
}

fn main() {
    let lz = ListZipper {
        focus: Some(42),
        left: vec![1, 2, 3].into(),
        right: vec![97, 98, 99].into(),
    };

    let head: Vec<_> = lz.take(5).collect();

    println!("{:?}", head);
}