Rust Reference ยท Iterators
The DoubleEndedIterator trait
Reference for the Rust DoubleEndedIterator trait: next_back, rev, nth_back, rfind and rfold, which iterators support it, and how to implement it.
A DoubleEndedIterator can be consumed from the back as well as from the front. It adds one required method, next_back, which takes the last remaining item. The two ends move toward each other and share the same items: once they meet, both return None.
The main reason to care is rev(), which is only available when the iterator is double-ended. Ranges, slices, vectors, chars(), map over a double-ended iterator, enumerate over an exact-size one and many others support it. Iterators that cannot know where the end is, such as from_fn or a filter on a stream, do not.
pub trait DoubleEndedIterator: Iterator { fn next_back(&mut self) -> Option<Self::Item>; }
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.
Syntax
pub trait DoubleEndedIterator: Iterator { fn next_back(&mut self) -> Option<Self::Item>; fn nth_back(&mut self, n: usize) -> Option<Self::Item>; fn rfold<B, F>(self, init: B, f: F) -> B where F: FnMut(B, Self::Item) -> B; fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item> where P: FnMut(&Self::Item) -> bool; fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R; }
| Name | Description |
|---|---|
next_back |
Removes and returns the last remaining item, or None if the iterator is exhausted. Required. |
nth_back(n) |
Returns the n-th item from the back (0 is the last) and discards the ones after it. |
rfold |
Like fold, but processes items from the back. |
rfind |
Like find, but searches from the back. |
Edge cases: next and next_back must never return the same item twice. After they cross, both must return None.
Usage notes
rev()requires this trait (Self: DoubleEndedIterator).v.iter().rev()is free: it does not allocate or copy, it just flips which endnextreads.- Adapters inherit the capability when they can.
map,filter,enumerate(withExactSizeIterator),zip(both exact-size and double-ended),skip,take,chainandrevitself all stay double-ended.scan,take_while,skip_while,step_byon arbitrary iterators andcycledo not offer it in general. enumerate().rev()keeps the original indexes (so the last item arrives first with the highest index).rev().enumerate()numbers from 0 in the reversed order. They are different.- Implementing it is optional but cheap when your data lives in a slice, vector or range. Implement
ExactSizeIteratoras well when the length is exact. rpositionneeds bothExactSizeIteratorandDoubleEndedIterator;last()on a double-ended iterator still walks the whole iterator unless the type overrides it, so prefernext_back()when you only want the last item.- Chars versus bytes:
str::chars()is double-ended, so.chars().rev()reverses bychar. It does not reverse grapheme clusters; combining marks end up in the wrong place.
Related
Iterator,ExactSizeIterator,revandlast- Lessons: Iterators, Custom iterators