在Rust中实现自定义迭代器时的无限循环(Infinite loop when implementing custom iterator in Rust)

我正在尝试实现列表拉链。到目前为止我有：

#[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 ，然后卡住了。即next()在光标到达后面时不会前进。

为什么？

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

I am trying to implement a list zipper. So far I have:

I am now trying to implement an iterator

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

In my head this makes sense. When iterating over ListZipper, I want to iterate over left, then focus and then right. So I chain those iterators and just return next().

This works fine if all fields in ListZipper are empty. As soon as one is not empty iterating over ListZipper results in an infinite loop.

The problem is not the chain. If I replace that by e.g. self.left.iter(), and left is not empty, the problem is the same. Likewise for focus and right.

I tried printing all elements in the iterator and it appears to go through the VecDeque from front to back, and then gets stuck. I.e. next() does not advance the cursor when it reaches the back.

Why?

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

最满意答案

正如评论中所提到的，你的迭代器缺少一个关键的状态： 它在迭代中有多远 。每次调用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本身成为迭代器，但这是另一个讨论。

不，它真的不是^ _ ^。你需要以某种方式改变被迭代的东西，以便它可以改变，并为每个后续的调用有不同的值。

如果要返回现有迭代器和迭代器适配器的组合，请参阅返回迭代器的正确方法？为说明。

否则，你需要以某种方式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); }

As mentioned in the comments, your iterator is lacking a crucial piece of state: how far along in the iteration it is. Every time you call next, it constructs another iterator completely from scratch and gets the first element.

Here's a reduced example:

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

No, it's really not ^_^. You need to somehow mutate the thing being iterated on so that it can change and have different values for each subsequent call.

If you want to return a combination of existing iterators and iterator adapters, refer to Correct way to return an Iterator? for instructions.

Otherwise, you need to somehow change ListZipper during the call to next:

More succinctly:

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

Note that your PartialEq implementation seems to be the same as the automatically-derived one...

更多推荐