向前和向后迭代

Question

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

我需要向前和向后迭代元素(例如,向前4次然后向后2次然后向前5次).

在C++中它将是:

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

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

Answer 1

Iterator类似于ForwardIteratorC++。你想要的是 a 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>>;
    // ...
}

但这还不支持。

也就是说，一种选择是使用使用特定迭代器的外部板条箱（即，不实现特征）。该linked_list箱提供了链表的实现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不允许保留对被屈服元素的引用。文档说：

ACursor就像一个迭代器，除了它可以自由地来回寻找，并且可以在迭代过程中安全地改变列表。这是因为其产生的引用的生命周期与其自身的生命周期相关，而不仅仅是底层列表。这意味着游标不能一次产生多个元素。

下面的例子：

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

生成此错误：

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

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

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

Answer 2

您需要实现自己的迭代器才能执行此操作。以下是 s 的示例实现Vec：

pub trait ForwardBackwardIterator : Iterator {
    fn prev(&mut self) -> Option<Self::Item>;
}

pub struct VectorForwardBackwardIterator<'a, Item> where Item : 'a {
    index: Option<usize>,
    vector: &'a Vec<Item>,
}

impl<'a, Item> VectorForwardBackwardIterator<'a, Item> {
    fn new(vector: &'a Vec<Item>) -> VectorForwardBackwardIterator<'a, Item> {
        VectorForwardBackwardIterator { index: None, vector: vector }
    }
}

impl<'a, Item> Iterator for VectorForwardBackwardIterator<'a, Item> {
    type Item = &'a Item;

    fn next(&mut self) -> Option<&'a Item> {
        let index = 
            match self.index {
                Some(i) => i + 1,
                None => 0
            };

        self.index = Some(index);
        self.vector.get(index)
    }
}

impl<'a, Item> ForwardBackwardIterator for VectorForwardBackwardIterator<'a, Item> {
    fn prev(&mut self) -> Option<&'a Item> {
        let index = 
            match self.index {
                Some(0) | None => return None,
                Some(i) => i - 1
            };

        self.index = Some(index);
        self.vector.get(index)
    }
}

fn main() {
    let v = vec![0, 1, 2, 3, 4, 5];
    let mut iterator = VectorForwardBackwardIterator::new(&v);

    println!("{:?}", iterator.next());
    println!("{:?}", iterator.next());
    println!("{:?}", iterator.next());
    println!("{:?}", iterator.prev());
    println!("{:?}", iterator.prev());
}

这打印出来

Some(0)
Some(1)
Some(2)
Some(1)
Some(0)