We have a double ended list of structs, e.g. LinkedList.
I need to iterate forward and backward through the elements (like, 4 times forward then 2 times backward then 5 times forward).
In C++ it would be:
iter++; iter++; ... iter--; ... In Rust, I only see .next() and .rev() which is inconvenient (since after a few iterations I already do not know in which direction I've reversed iteration).
Iterator is similar to ForwardIterator of C++. What you want is a BidirectionalIterator, but Rust does not provide a trait similar to it because of a limitation in the type system.
As Matthieu M said in comments, the way an iterator is defined allows a reference to the yielded element to be kept. And that's a problem if the iterator produces mutable references, because moving forward and backward would allow multiples mutable references to the same element. One way to solve this problem would be to tie the lifetime of the yielded element with &mut self, so a call to next (or prev) would borrow self, but there is no way of doing it in a generic way (there is a RFC to add such capability).
Looking the Iterator trait definition:
pub trait Iterator { type Item; fn next<'a>(&'a mut self) -> Option<Self::Item>; // ... } we can see that the lifetime of Self::Item is independent of 'a. What is necessary to solve the problem is:
pub trait Iterator { type Item<'a>; // hypothetical syntax fn next<'a>(&'a mut self) -> Option<Self::Item<'a>>; // ... } but that is not supported yet.
That said, one option is to use a external crate that use a specific iterator (that is, do not implement a trait). The linked_list crate provides a linked list implementation with Cursor, that allows forward and backward iteration:
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 does not allow a reference to the yielded element to be kept. The docs says:
A
Cursoris 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.
The following example:
let a = c.next(); let b = c.next(); generates this error:
error: cannot borrow `c` as mutable more than once at a time [E0499] let b = c.next(); This happens because next (and prev) borrows from self, that is:
fn next<'a>(&'a mut self) -> Option<&'a mut T> 
Iterator is designed so that you can retain references to the elements that it yielded, so that if you can go back and forth you would be able to have multiple references to the same element (aka: aliasing). Now, imagine that the references in question are mutable: you now have multiple mutable references to the same element, BOOM. So, since yielding mutable references is desirable, the Iterator trait has given up aliasing.You'll need to implement your own iterator to do this. Here's a sample implementation of one for Vecs:
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()); } This prints out
Some(0) Some(1) Some(2) Some(1) Some(0) 
.rev()probably does not what you expect. It reverses the iterator, so you are now taking elements from the back.