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

Question

我正在尝试实现列表拉链.到目前为止,我有:

#[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结果就会产生无限循环.

问题不在于链条.如果我用eg替换它self.left.iter(),并且left不是空的,问题是一样的.同样的focus和right.

我尝试在迭代器中打印所有元素,它似乎VecDeque从前到后穿过,然后卡住了.即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]
}

我意识到我可能不希望ListZipper自己成为迭代器,但这是另一个讨论.

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

如果要返回现有迭代器和迭代器适配器的组合,请参阅返回迭代器的正确方法？作为指示.

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

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