list - 向前和向后迭代

标签 list iterator rust

我们有一个双端结构列表,例如链表

我需要向前和向后遍历元素(例如,向前 4 次,然后向后 2 次,然后向前 5 次)。

在 C++ 中它将是:

iter++; iter++; ... iter--; ...

在 Rust 中,我只看到 .next().rev() 这很不方便(因为经过几次迭代后我已经不知道我在哪个方向了'反向迭代)。

最佳答案

Iterator类似于 ForwardIterator C++的。你想要的是 BidirectionalIterator , 但由于类型系统的限制,Rust 没有提供类似的特性。

作为Matthieu M在评论中说,定义迭代器的方式允许保留对所产生元素的引用。如果迭代器产生可变引用,那将是一个问题,因为向前和向后移动将允许对同一元素的多个可变引用。解决此问题的一种方法是将生成的元素的生命周期与 &mut self 联系起来,因此调用 next(或 prev)会借用 self,但没有办法以通用方式执行此操作(有一个 RFC 来添加这种功能)。

查看 Iterator 特征定义:

pub trait Iterator {
    type Item;
    fn next<'a>(&'a mut self) -> Option<Self::Item>;
    // ...
}

我们可以看到Self::Item的生​​命周期是独立于'a的。解决问题的必要条件是:

pub trait Iterator {
    type Item<'a>; // hypothetical syntax
    fn next<'a>(&'a mut self) -> Option<Self::Item<'a>>;
    // ...
}

但这还不支持。


也就是说,一种选择是使用使用特定迭代器的外部 crate (即不实现特征)。 linked_list crate 提供了一个链表实现 Cursor , 允许向前和向后迭代:

use linked_list::LinkedList;
use std::iter::FromIterator;

fn main() {
    // LinkedList::cursor takes &mut self, so lst must be mutable
    let mut lst = LinkedList::from_iter(0..10);
    let mut c = lst.cursor();

    c.next();
    c.next();
    c.next();
    c.prev();

    assert_eq!(1, *c.prev().unwrap());
}

Cursor 不允许保留对已生成元素的引用。文档说:

A Cursor is like an iterator, except that it can freely seek back-and-forth, and can safely mutate the list during iteration. This is because the lifetime of its yielded references is tied to its own lifetime, instead of just the underlying list. This means cursors cannot yield multiple elements at once.

下面的例子:

let a = c.next();
let b = c.next();

生成此错误:

error: cannot borrow `c` as mutable more than once at a time [E0499]
    let b = c.next();

发生这种情况是因为next(和prev)借用了self,即:

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

关于list - 向前和向后迭代,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38227722/

相关文章:

python - 从Python中的字典中获取键值

java - ArrayList 矩阵的自定义集合可迭代

c++ - 找不到子类的成员

rust - 为什么需要导入特征以使用它为类型定义的方法?

python - 列表列表更改意外地反射(reflect)在子列表中

arrays - 使用outer生成列表数组

rust - 为什么 "one type is more general than the other"在包含闭包的选项中?

rust - 枚举中的条件编译

python - 如何设置计时器来控制循环内的函数调用?

Python:如何在不先创建整个列表的情况下计算列表的总和?