Skip to content
Tutorials Center
My learning

Topics

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.

Rust
pub trait DoubleEndedIterator: Iterator {
    fn next_back(&mut self) -> Option<Self::Item>;
}

Try it

Rust Taking items from both ends

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.

Rust Implementing next_back

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

Rust
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 end next reads.
  • Adapters inherit the capability when they can. map, filter, enumerate (with ExactSizeIterator), zip (both exact-size and double-ended), skip, take, chain and rev itself all stay double-ended. scan, take_while, skip_while, step_by on arbitrary iterators and cycle do 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 ExactSizeIterator as well when the length is exact.
  • rposition needs both ExactSizeIterator and DoubleEndedIterator; last() on a double-ended iterator still walks the whole iterator unless the type overrides it, so prefer next_back() when you only want the last item.
  • Chars versus bytes: str::chars() is double-ended, so .chars().rev() reverses by char. It does not reverse grapheme clusters; combining marks end up in the wrong place.