迭代向前和向後

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)