size_hint and DoubleEndedIterator: an iterator with two ends

Implement an inclusive integer span that can be consumed from both ends and that reports its length honestly.

pub struct Span { pub lo: i64, pub hi: i64 }

pub fn span_probe(lo: i64, hi: i64, take_front: usize, take_back: usize)
    -> (Vec<i64>, usize, usize)

Span { lo, hi } covers lo..=hi and is empty when lo > hi. Give it:

• Iterator — next yields from the low end;
• a correct size_hint;
• DoubleEndedIterator — next_back yields from the high end;
• ExactSizeIterator.

span_probe then, in this exact order:

1. records span.len() — the value returned by ExactSizeIterator;
2. records span.size_hint().0 — the hint’s lower bound;
3. alternately takes one element from the front (while take_front budget remains) and one from the back (while take_back budget remains), pushing each onto the output as it is taken, stopping as soon as either end returns None or both budgets are exhausted.

span_probe(1, 5, 2, 1)    ->  ([1, 5, 2],    5, 5)
span_probe(1, 4, 10, 10)  ->  ([1, 4, 2, 3], 4, 4)
span_probe(5, 1, 2, 2)    ->  ([],           0, 0)
span_probe(0, 0, 0, 0)    ->  ([],           1, 1)

Asserting on the hint is what makes this gradeable

A wrong size_hint is not a compile error, not undefined behaviour, and not a wrong answer from any adapter. It makes collect allocate badly and nothing else. That is exactly why nobody notices when it is wrong — so this problem returns the reported values and checks them.

What size_hint is for

fn size_hint(&self) -> (usize, Option<usize>)

A lower bound and an optional upper bound on how many items remain. The default implementation returns (0, None) — “I promise nothing” — which is always correct and always useless.

collect reads it and calls Vec::with_capacity(lower) before it starts. With a good hint that is one allocation; with (0, None) it is a doubling sequence of reallocations and memcpys. extend, String::from_iter, and Vec::from_iter all do the same.

Adapters propagate it, and the pattern is worth memorising because it explains most of the performance surprises in the next section. Verified on rustc 1.95:

map cannot change the count, so it forwards the hint untouched. filter might reject everything, so its lower bound is 0. flatten has no idea how long the inner iterators are without running them, so it knows nothing — and neither does split, which would have to scan the string to answer.

Where “zero-cost abstraction” stops being true

Two measurements, same method, opposite results:

(0..1_000_000).map(..).collect::<Vec<u32>>()     0.049 ms
Vec::with_capacity(1_000_000) + push loop        0.716 ms   <- collect 14.6x FASTER

chunks.iter().flatten().copied().collect()       0.511 ms
chunks.concat()                                  0.079 ms   <- collect 6.5x SLOWER

(Absolute times depend on machine and allocator; the directions reproduce.)

size_hint explains both. A Range has an exact hint and, internally, an unsafe marker trait called TrustedLen, which lets collect specialise to “allocate once, then fill without a per-element capacity check” — which vectorises. The push loop cannot: push must check capacity every time, even though you know it will never grow.

Flatten has hint (0, None), so collect starts from an empty Vec and reallocates its way up, copying as it goes. concat asks each inner slice for its length first, allocates exactly once, and memcpys. Same answer, six times the work.

The honest caveat: TrustedLen is an unstable unsafe trait. You cannot opt your own iterator into the fast path. A correct size_hint still buys you the single up-front allocation, which is most of the win — but not the vectorised fill.

ExactSizeIterator and the panic you can cause

pub trait ExactSizeIterator: Iterator {
    fn len(&self) -> usize {
        let (lower, upper) = self.size_hint();
        assert_eq!(upper, Some(lower));
        lower
    }
}

The default len is derived from size_hint, and it asserts that the bounds agree. Implement ExactSizeIterator with a sloppy hint and you get:

thread 'main' panicked at library/core/src/iter/traits/exact_size.rs:
assertion `left == right` failed
  left: Some(4)
 right: Some(3)

So implementing ExactSizeIterator is a promise about size_hint, not a separate piece of work. Get the hint right and the impl body is empty.

DoubleEndedIterator and meeting in the middle

fn next_back(&mut self) -> Option<Self::Item>

This is what rev(), last() and rposition() are built on. The contract is that next and next_back draw from the same pool and must meet in the middle without overlapping: once they cross, both return None forever.

An off-by-one here duplicates the middle element, and the alternating-take cases catch it. span_probe(1, 4, 10, 10) must give [1, 4, 2, 3] — four elements, each exactly once — and span_probe(10, 12, 3, 3) must give [10, 12, 11] and then stop, not yield 11 twice.

Also worth knowing: .last() on a DoubleEndedIterator walks forward to the end unless the iterator overrides it, because last is defined on plain Iterator. Clippy’s default-on double_ended_iterator_last tells you to call .next_back() instead.

FusedIterator, briefly

An iterator that returns None and then Some again is legal but astonishing. FusedIterator is a marker promising it never happens, which lets adapters skip a “have we finished” flag. .fuse() adds that flag to any iterator. Span is naturally fused: once lo > hi it stays that way. You do not need to implement the marker here, but knowing why it exists is worth the minute.

Grade is compile + tests + clippy -D warnings.