5.4 · DoubleEndedIterator, ExactSizeIterator, and FusedIterator

Domain 5 — Iterators and Lazy Computation Duration: ~15 minutes Library components: std::iter::DoubleEndedIterator, std::iter::ExactSizeIterator, std::iter::FusedIterator

Introduction

Iterator makes only one promise: next() yields items until it returns None. Three refinement traits add guarantees to that contract:

• iteration from both ends
• an exact remaining count
• a permanent end

Because of these traits, rev() compiles, len() exists, and collect() allocates exactly one time. Each adapter keeps some of these traits and loses the others. When you know which traits an adapter keeps, you can explain the compile errors that say a method does not exist.

This tutorial shows:

• DoubleEndedIterator and next_back, and the methods that start at the back: rev, rfind, rposition, rfold.
• ExactSizeIterator, len(), and the size_hint contract that each iterator has.
• How collect and extend use the size information to allocate only one time.
• FusedIterator (the guarantee that None is permanent) and the cost of fuse() (usually nothing).
• TrustedLen, the unsafe trait that is one step above and is still unstable.
• How to implement the full trait family on a custom type.

The Trait Family Map

Figure: Iterator refinement traits and what each adds

A slice iterator implements all three stable refinement traits. A std::io::Lines iterator implements none of them. It cannot know the line count in advance, and the text could in principle become longer. Ranges are between these two cases. 0..n implements all three (for example, when n is a usize). The unbounded 0.. is only fused, because it has no back end and no finite length.

DoubleEndedIterator: Two Cursors

A double-ended iterator keeps two cursors on one range of items. next() takes an item from the front, and next_back() takes an item from the back. The cursors move toward each other and never cross. After they meet, next() and next_back() both return None. This does not iterate the items two times. The iterator still yields each item exactly one time, from the end that asks first.

Figure: Front and back cursors converging on a slice iterator

// log: [&str; 6], six log lines from "boot" (first) to "shutdown" (last).
let mut it = log.iter();
assert_eq!(it.next(),      Some(&"boot"));               // front
assert_eq!(it.next_back(), Some(&"shutdown"));           // back
assert_eq!(it.next_back(), Some(&"ERROR timeout"));      // back again
assert_eq!(it.next(),      Some(&"ERROR disk warning")); // front
assert_eq!(it.count(), 2);                               // only the middle two remain

05_12_double_ended.rs uses the methods that come from next_back to analyze a log:

• rev() exchanges the functions of the two cursors, so next() moves the back cursor. It does not buffer and does not allocate. log.iter().rev().take(3).rev() gives the same lines as tail -n 3, in chronological order.
• rfind(p) and rposition(p) search from the back to the front. They find the most recent match, which is usually the match that you want in a log. rposition reports the index from the front. It needs ExactSizeIterator for that calculation, so the two traits operate together.
• rfold(init, f) folds from the right. Use it when the operation is not commutative.
• Algorithms with two cursors: a palindrome check reads chars() from both ends until the cursors meet in the middle.

05_12_double_ended.rs prints:

tail -n 3: ["request b", "ERROR timeout", "shutdown"]
most recent error at index 4: ERROR timeout
rfold nesting: usr(local(bin))
palindrome checks passed

All assertions passed.

size_hint: Every Iterator's Estimate

Each iterator has size_hint() -> (usize, Option<usize>). It returns a lower bound and an optional upper bound on the number of remaining items. It is a contract about bounds, not a promise of an exact count. Consumers may use it only for optimization. A wrong hint may waste memory, but it must never cause unsoundness in safe code.

Adapters change the hint together with the items. 05_13_exact_size_hints.rs verifies each row of this table:

ExactSizeIterator: len() and Its Loss

ExactSizeIterator is the promise that the hint is exact, and it adds one method. len() returns the remaining count. The count decreases as you consume items, so it is not the length of the source. In the usual case, the implementation adds no code. The default len() only reads size_hint().0.

The important point is which adapters keep the promise. map, rev, take, skip, and zip keep the exact count. filter, flat_map, and take_while cannot know their output count. Thus their result does not implement the trait and does not have the method:

// `filter` returns a `Filter`, which does not implement ExactSizeIterator.
// This line does not compile:
//     let n = (0..100).filter(|x| x % 3 == 0).len();
// error[E0599]: the method `len` exists for struct `Filter<...>`,
//               but its trait bounds were not satisfied

That compile error is correct information from the trait system: no one knows the length until the filter runs.

What collect() Does with the Hint

Vec::from_iter reads the hint at the start and reserves capacity for the lower bound. You can see the effect in the capacity:

// The hint is (1000, Some(1000)): collect reserves space for 1000 elements.
let v: Vec<u32> = (0..1000).collect();
assert_eq!(v.capacity(), 1000);        // one allocation, no unused capacity

// The hint is (0, Some(1000)): the Vec starts small and doubles its capacity.
let f: Vec<u32> = (0..1000).filter(|x| x % 2 == 0).collect();
assert_eq!(f.len(), 500);              // capacity: 512 today (implementation detail)

When you know the size better than the hint, give the size to the Vec. Use with_capacity and then extend:

// You know that 500 of the 1000 values are even.
let mut w: Vec<u32> = Vec::with_capacity(500);
w.extend((0..1000).filter(|x| x % 2 == 0));
assert_eq!(w.capacity(), 500);         // no growth steps, no unused capacity

05_13_exact_size_hints.rs prints:

after one next(): len() = 3
size hints verified for map/filter/chain/take/repeat
exact-size collect: len=1000, capacity=1000
filtered collect:  len=500, capacity=512   # (capacity varies by std impl)
with_capacity+extend: len=500, capacity=500

All assertions passed.

TrustedLen is one step above ExactSizeIterator: an unsafe marker trait that is still unstable. It means that unsafe code may rely on an exact hint. With it, collect also skips the capacity check for each item. You cannot implement it on stable 1.99, but the iterators of the standard library implement it for you. It is a large part of the reason why (0..1000).collect() is as fast as a loop in the style of memset.

FusedIterator: None Means None

The base contract permits an unusual behavior: after next() returns None, a later call may yield values again. Most iterators never do this, but generic code cannot assume that. Code that stores an iterator and polls it in more than one round (parsers, schedulers, mergers) would need defensive flags.

Two tools solve this problem:

• fuse() is an adapter that you can put on any iterator. After the first None, the adapter always returns None.
• FusedIterator is a marker trait. It declares that the iterator already behaves that way. Fuse<I> has a specialization for it, so .fuse() on a fused iterator adds almost no overhead. Thus generic code can call .fuse() as a defensive step.

05_03_slicing_adapters.rs showed the Flicker iterator, which yields items again after None. 05_14_fused_trait_family.rs shows that fuse() costs almost nothing for an iterator that is already fused.

Adapters keep the marker when they can. Since Rust 1.99, StepBy<I> implements FusedIterator when I implements it, so a function with a FusedIterator bound accepts a stepped iterator directly:

use std::iter::FusedIterator;

// The bound is the guarantee: after the first None, each poll returns None.
fn count_then_poll_again<I: FusedIterator>(mut iter: I) -> usize {
    let mut count = 0;
    while iter.next().is_some() {
        count += 1;
    }
    assert!(iter.next().is_none());   // an extra poll returns None again
    count
}

// 0, 3, 6, 9. Before Rust 1.99 this call needed `.fuse()` to compile.
assert_eq!(count_then_poll_again((0..10).step_by(3)), 4);

The implementation is conditional. iter::from_fn(..).step_by(2) is not fused, because FromFn is not fused. 05_22_step_by_fused.rs shows the two cases.

Implementing the Family

05_14_fused_trait_family.rs implements all four traits on a Countdown iterator. As a result, each generic method of the trait family becomes available:

// Countdown yields start, start-1, ..., 1. The example file has the method bodies.
impl Iterator for Countdown {
    type Item = u32;
    fn next(&mut self) -> Option<u32> { /* front cursor */ }
    fn size_hint(&self) -> (usize, Option<usize>) { /* exact */ }
}
impl DoubleEndedIterator for Countdown {
    fn next_back(&mut self) -> Option<u32> { /* back cursor */ }
}
impl ExactSizeIterator for Countdown {}   // promise: the hint is exact
impl FusedIterator for Countdown {}       // promise: None is final

// `starting_at(n)` makes a Countdown that yields n, n-1, ..., 1.
let liftoff: Vec<u32> = Countdown::starting_at(3).rev().collect(); // rev: needs DoubleEnded
// liftoff is [1, 2, 3]
assert_eq!(Countdown::starting_at(10).len(), 10);                  // len: needs ExactSize
let v: Vec<u32> = Countdown::starting_at(1000).collect();
assert_eq!(v.capacity(), 1000);                                    // collect uses the exact hint

The two empty impl blocks are promises, not code. Write them only when they are true. A wrong len(), or a fused iterator that yields items again after None, does not cause memory unsafety by itself. That would need TrustedLen. But a false promise causes wrong behavior in each consumer that relies on it.

05_14_fused_trait_family.rs prints:

countdown len after eating both ends: 8
collect() trusted our size_hint: capacity = 1000
fuse() on an already-fused iterator: zero-cost formality

All assertions passed.

Summary

Code Examples