迭代向前和向后

Question

我们有一个结束的双端列表，例如， LinkedList。我需要向前和向后遍历元素（例如，前进4次，后2次，然后5次）。

在C++是：

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

生锈，我只看到.next()和.rev()这是不方便（因为经过几次反复，我已经不知道在哪个方向我已经逆转迭代）。

Answer 1

Iterator类似于C++的ForwardIterator。你想要的是一个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不允许的产生元素的引用来保持。该文档说：

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> 

Answer 2

你需要实现你自己的迭代器来做到这一点。这里有一个对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)