Skip to content
Tutorials Center
My learning

Topics

Lesson 53 of 132 ยท Collections and Iterators

Writing Your Own Iterators

Learn to implement Rust's Iterator trait, IntoIterator for your collections and references, DoubleEndedIterator, ExactSizeIterator, impl Iterator returns, from_fn and successors.

The standard library gives you iterators for ranges, slices, vectors, strings and maps. Sooner or later you will have a type of your own that deserves one too: a countdown, a Fibonacci generator, a tree walker, a custom collection that should work in a for loop. Because Iterator is an ordinary trait, you can implement it for any type, and the moment you do, every adapter and consumer from the previous lessons works on it for free.

This lesson covers four levels, from smallest to largest: implementing Iterator for a state struct, making a collection loopable with IntoIterator, adding capabilities such as DoubleEndedIterator and ExactSizeIterator, and the shortcuts (impl Iterator, from_fn, successors) that avoid writing a struct at all.

Implementing Iterator

You need two things: a type that holds the iteration state, and an impl Iterator for it with an Item type and a next method. That is all. Here is a countdown:

Rust A countdown iterator

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.

Read next as the iterator's heartbeat: each call must do exactly one step of work and either return the next value or None. The struct stores whatever it needs to resume, here just a counter. The parentheses around Countdown { remaining: 3 } in the for header are required; a bare struct literal there confuses the parser.

The last line pairs 4, 3, 2, 1 with 3, 2, 1 (the second sequence is shifted by skip(1)); zip stops at the shorter one, so we get 4*3 + 3*2 + 2*1 = 20.

Fibonacci: an infinite iterator

An iterator never has to end. Returning Some forever is perfectly fine; the consumer decides when to stop with take, take_while or find.

Rust An infinite Fibonacci iterator

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.

Using ? on an Option inside next is a neat trick: when checked_add returns None, the whole function returns None and the sequence ends. Without that check, a debug build would panic with "attempt to add with overflow" once the numbers outgrow u64.

If your iterator can fail halfway, set type Item = Result<T, E> and yield Err for the bad step. Consumers can then collect::<Result<Vec<_>, _>>() as in Iterator Patterns.

IntoIterator: making a collection loopable

for x in thing calls IntoIterator::into_iter(thing). Standard collections implement it three times, which is how for x in v, for x in &v and for x in &mut v all work. For your own collection you decide which of those to support.

The simplest implementation delegates to an existing iterator:

Rust IntoIterator for a custom collection

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.

The associated type IntoIter names the iterator that into_iter returns. Spelling out types like std::slice::Iter<'a, String> is the traditional way; it is verbose but it works on every edition. In many programs you only need the &Playlist version, and an iter(&self) method returning impl Iterator<Item = &String> + '_ is a lighter alternative.

DoubleEndedIterator and ExactSizeIterator

Two extra traits unlock more adapters:

  • DoubleEndedIterator adds next_back(). That enables rev(), last() in constant time and rfind.
  • ExactSizeIterator adds len(), so consumers can pre-size allocations.

Both are optional promises you make about your iterator. Here we implement them for a range-like struct:

Rust Double-ended and exact-size

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.

The two ends share state, so they never overlap: after two next and two next_back calls, one item (3) remains, the fifth call returns it, and the sixth returns None. ExactSizeIterator has no required methods, but its len() relies on size_hint returning identical lower and upper bounds, so make those truthful.

Returning iterators from functions

You often want a function that returns an iterator without exposing (or even being able to write) its concrete type, because closures have unnameable types. Use impl Iterator<Item = T> in return position:

Rust Returning impl Iterator

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.

impl Iterator is a promise to the caller of "some single concrete iterator type"; it costs nothing at run time. An if that returns two different iterator types does not satisfy that promise, which is why count_up_or_down boxes the iterator as a trait object (one heap allocation, dynamic dispatch). See trait objects. Without the move in long_words, the closure would borrow min, a local that dies when the function returns.

from_fn and successors: iterators without a struct

For one-off generators the standard library offers two constructors in std::iter.

  • from_fn(f) calls a closure again and again; the closure keeps its own state and returns Option<T>.
  • successors(first, f) starts from an initial Option value and computes each next value from the previous one.
  • repeat, repeat_with, once and empty cover the trivial cases.
Rust from_fn and successors

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 has no yield keyword for general generators in stable code, so from_fn with a captured state variable is the closest everyday equivalent. When the state machine gets complicated, a struct with an explicit enum state (as in enums) is clearer.

Design notes and pitfalls

  • Prefer returning impl Iterator over Vec when callers may not need every item; it stays lazy and allocates nothing.
  • Item type of a borrowing iterator carries a lifetime. Iterators that yield references into a struct must say so (type Item = &'a T). See lifetimes.
  • Do not write next that does unbounded work per call. Callers assume each step is cheap.
  • Fused behaviour. After returning None, a plain Iterator may legally return Some again. Use .fuse() if you cannot trust the source, or implement FusedIterator.
  • Returning a borrowing iterator without saying so (in editions before 2024) gives lifetime errors; adding + '_ or + 'a is the usual fix.
  • Overriding size_hint is optional but makes collect faster; a wrong hint on an ExactSizeIterator is a logic bug.

Here is a classic mistake: writing next that returns a reference to data created inside the call. It cannot work, because the iterator trait has no way to tie the item's lifetime to &mut self.

Rust Items cannot borrow from self (fails on purpose)

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.

rustc stops at the type Item = &str; line with the error "associated type Iterator::Item is declared without lifetime parameters, so using a borrowed type for them requires that lifetime to come from the implemented type", and a note that you cannot create an Iterator that borrows each Item from itself. The fix it suggests is a new type that borrows existing data: struct Lines<'a> { rest: &'a str } with type Item = &'a str, so the struct borrows the string instead of owning it. Iterators that hand out references into themselves ("lending iterators") are not expressible with the standard trait; yield owned values, indexes, or borrow from outside data.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What must you define to implement Iterator for your own type?

    Item and next are the only required parts. Every adapter and consumer is a provided method built on next.
  2. 2. Which trait makes for x in &my_collection work?

    A for loop calls IntoIterator::into_iter on the expression. Implement it for MyCollection, &MyCollection and &mut MyCollection to support by-value, shared and mutable loops.
  3. 3. Why can rev() be called on Span in the lesson?

    rev() requires DoubleEndedIterator. Ranges, slices and vectors implement it; your type must supply next_back to opt in.
  4. 4. A function has two branches returning different iterator types. What is a fix?

    impl Iterator stands for exactly one concrete type. With different types per branch, box them as trait objects (or use an enum that implements Iterator).
  5. 5. What does std::iter::successors(Some(1), |&n| n.checked_mul(2)) do?

    successors yields the first value, then keeps applying the closure to the previous value until it returns None. checked_mul returns None on overflow, ending the sequence cleanly.

Summary

  • Implement Iterator with type Item and next(&mut self) -> Option<Item>; all adapters and consumers then work on your type.
  • Iterators can be infinite; the consumer chooses where to stop.
  • Implement IntoIterator for T, &T and &mut T so for loops work by value, by reference and by mutable reference.
  • Add DoubleEndedIterator (next_back, enables rev) and ExactSizeIterator (len, backed by a truthful size_hint) when they make sense.
  • Return impl Iterator<Item = T> (add + '_ when it borrows) or Box<dyn Iterator> when branches differ.
  • iter::from_fn and iter::successors build one-off generators without a struct.
  • Items that borrow from the iterator itself are not possible with the standard trait; yield owned values.

Next: Closures