Итерация вперед и назад

Question

У нас есть двойной список структур, например. LinkedList.

Мне нужно перебирать вперед и назад элементы (например, 4 раза вперед, затем 2 раза назад, затем 5 раз вперед).

В C++ это будет:

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

В Руст, я вижу только .next() и .rev() что неудобно (так как после нескольких итераций я уже не знаю, в каком направлении я отменил итерации).

Answer 1

Iterator аналогичен ForwardIterator C++. То, что вы хотите, это BidirectionalIterator, но Rust не дает подобной ему черты из-за ограничения в системе типов.

В Matthieu M, как указано в комментариях, способ определения итератора позволяет ссылаться на уступленный элемент. И это проблема, если итератор создает изменчивые ссылки, потому что перемещение вперед и назад позволило бы мультипликационным изменяемым ссылкам на один и тот же элемент. Одним из способов решения этой проблемы было бы связать время жизни уступаемого элемента с &mut self, поэтому звонок в next (или prev) займется self, но нет никакого способа сделать это в общем виде (есть добавьте такую ​​возможность).

Глядя определение 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)