Project 6: Implement an Iterator with Lifetimes

Build a collection with a custom iterator that yields borrowed elements safely and demonstrates lifetime relationships.

Quick Reference

Attribute	Value
Difficulty	Advanced
Time Estimate	1 week
Main Programming Language	Rust
Alternative Programming Languages	C++ (iterators), Java (Iterable)
Coolness Level	Medium
Business Potential	Medium
Prerequisites	Lifetimes, borrowing, trait implementations
Key Topics	Iterator trait, borrowing during iteration, GATs

1. Learning Objectives

By completing this project, you will:

Implement a custom iterator that yields &T with correct lifetimes.
Explain how the iterator’s lifetime is tied to the collection.
Prevent mutation while iteration is active.
Explore advanced iterator patterns like lending iterators and GATs.

2. All Theory Needed (Per-Concept Breakdown)

2.1 Iterator Trait and Lifetime Relationships

Fundamentals

The Iterator trait defines a method next that returns an Option<Item>. If the iterator yields references (&T), those references must live at least as long as the iterator. This is expressed by storing a reference to the collection inside the iterator struct. The iterator’s lifetime parameter ensures the compiler enforces that the collection outlives the iterator.

Deep Dive into the concept

Rust’s iterator model is based on ownership and borrowing. For an iterator that yields owned values, you can consume the collection. But when you want to yield borrowed values, you must ensure the borrowed data remains alive. The standard pattern is:

struct Iter<'a, T> { slice: &'a [T], index: usize }

Then you implement Iterator for Iter<'a, T> with type Item = &'a T. The lifetime 'a ties the returned references to the slice. The borrow checker enforces that the slice (and therefore the original collection) outlives the iterator.

This relationship is why you cannot mutate a collection while iterating over it. When you call iter(), you borrow the collection immutably for the duration of the iterator. If you try to borrow it mutably (e.g., push new elements), the compiler rejects it because the immutable borrow is still active. This is a direct example of Rust’s aliasing rules preventing iterator invalidation.

The iterator trait has limitations: it cannot express a “lending iterator” where each call to next returns a reference tied to the borrow of self at that moment. Instead, Iterator assumes the Item type has a single lifetime parameter, which is why you use Iter<'a, T> and store a reference. This works for slices but fails for more complex iterators that need to return references tied to temporary borrows. In Rust 1.65+, Generic Associated Types (GATs) allow you to define type Item<'a> and build lending iterators, but they are more advanced and still require careful API design.

Understanding iterator lifetimes also helps you reason about IntoIterator and iter() vs iter_mut() vs into_iter(). iter() borrows, iter_mut() mutably borrows, and into_iter() consumes. This project focuses on iter() and the lifetime it introduces. A key lesson is that the iterator struct is the real borrow; as long as it exists, the borrow is active.

How this fit on projects

This concept is applied in §3.1 (what you build) and §5.10 (phase 2). It connects to Project 5 (iterating interned values) and Project 10 (designing safe APIs).

Definitions & key terms

Iterator: Trait defining sequential access.
Borrowed iterator: Iterator yielding references.
Lending iterator: Iterator whose items borrow from self per call.
GATs: Generic Associated Types enabling advanced lifetimes.

Mental model diagram (ASCII)

Collection --borrow--> Iter<'a>
Iter::next() -> &'a T

How it works (step-by-step)

Collection creates iterator with a slice reference.
next returns references into the slice.
Collection cannot be mutated while iterator lives.

Minimal concrete example

pub fn iter<'a>(&'a self) -> Iter<'a, T> { ... }

Common misconceptions

“Iterators copy data.” Borrowed iterators return references, not copies.
“Mutation during iteration is safe.” It can invalidate references.

Check-your-understanding questions

Why does the iterator store a reference to the collection?
What prevents mutation during iteration?
When would you need a lending iterator?

Check-your-understanding answers

To ensure items live long enough.
The immutable borrow created by iter().
When items borrow from internal buffers created per next call.

Real-world applications

Iterating over slices without copying.
Streaming parsers that yield borrowed tokens.

Where you’ll apply it

This project: §5.10 Phase 1-2, §6 tests.
Also used in: Project 5: String Interning.

References

TRPL Ch. 13 (iterators).
Rust RFCs on GATs.

Key insights

Iterator lifetimes are just borrowed references stored in the iterator itself.

Summary

Borrowed iterators are safe because the iterator struct holds the borrow.

Homework/Exercises to practice the concept

Implement iter() and iter_mut() for a custom collection.
Try to mutate the collection while iterating and observe compiler errors.

Solutions to the homework/exercises

Return iterator structs with &[T] or &mut [T].
Rust rejects mutable borrow while immutable borrow exists.

2.2 Aliasing and Mutation During Iteration

Fundamentals

Rust forbids mutation of a collection while an iterator holds an immutable borrow. This prevents invalidation of references and is enforced at compile time. Iterators that yield &mut T require exclusive access to the collection.

Deep Dive into the concept

When you iterate over a collection and yield references, you must guarantee that the collection’s contents will not move or be mutated in ways that invalidate those references. This is why Vec<T> invalidates references when it grows. Rust uses borrowing rules to enforce this: if an iterator holds &self, you cannot call methods that require &mut self. This statically prevents structural changes that would invalidate references.

However, you can still mutate elements in place if you have a mutable iterator (iter_mut()). In that case, the iterator holds &mut [T], which guarantees exclusive access to the slice. This prevents any other borrows, ensuring safety. The borrow checker enforces that you cannot have two mutable iterators simultaneously, which would allow aliasing.

This concept is crucial for designing iterators on custom collections. If your collection internally stores data in multiple buffers, you must ensure that your iterator does not outlive those buffers or allow mutation that moves data. For example, if your collection uses a Vec<Vec<T>> internally, you must ensure the outer vector is not mutated while iterating.

In advanced cases, you can use interior mutability to allow certain mutations during iteration (like updating counters), but you must carefully document that these mutations do not invalidate references. This is a common pattern in caching iterators, but it requires strict invariants.

How this fit on projects

This is applied in §5.4 and §6 testing. It connects to Project 3 (borrow splitting) and Project 4 (shared mutation under locks).

Definitions & key terms

Alias: Multiple references to the same location.
Invalidation: Moving data such that references become dangling.
Structural mutation: Changing collection size or layout.

Mental model diagram (ASCII)

iter(): &self  -> no mutation
iter_mut(): &mut self -> exclusive mutation

How it works (step-by-step)

iter() borrows collection immutably.
Attempt to mutate -> compiler error.
iter_mut() borrows mutably, allowing in-place changes.

Minimal concrete example

for x in collection.iter() { /* cannot push */ }

Common misconceptions

“Mutation during iteration is okay if it’s small.” It’s not safe unless proven.
“Rust is too strict.” It prevents subtle use-after-free bugs.

Check-your-understanding questions

Why can’t you push to a Vec while iterating?
What kind of mutation is safe under iter_mut()?

Check-your-understanding answers

Pushing may reallocate and move elements.
In-place mutation of existing elements.

Real-world applications

Safe iteration in parsers and interpreters.

Where you’ll apply it

This project: §5.10 Phase 2 and tests.
Also used in: Project 3: Graph Data Structure.

References

TRPL Ch. 13 (iterators).

Key insights

Iterator safety is the same as aliasing safety: do not move data while borrowed.

Summary

Rust’s borrow checker prevents iterator invalidation by forbidding conflicting borrows.

Homework/Exercises to practice the concept

Write code that tries to push during iteration and observe the error.
Refactor to collect indices first, then mutate.

Solutions to the homework/exercises

The compiler rejects the mutable borrow.
Use a two-phase approach: collect then mutate.

2.3 GATs and Lending Iterators (Advanced)

Fundamentals

Generic Associated Types (GATs) allow the Item type of an iterator to depend on a lifetime. This makes it possible to write iterators that borrow from self on each call to next, known as lending iterators.

Deep Dive into the concept

The standard Iterator trait uses a fixed Item type, which makes it hard to express iterators that yield references tied to temporary borrows. For example, a parser might need to return references into an internal buffer that changes each time you call next. With GATs, you can define:

trait LendingIterator {
    type Item<'a> where Self: 'a;
    fn next<'a>(&'a mut self) -> Option<Self::Item<'a>>;
}

This allows each next call to borrow self and return references valid only for that borrow. While this pattern is still advanced and unstable in some contexts, it is a key idea in Rust’s evolving iterator ecosystem.

For this project, you don’t need to implement a full lending iterator, but you should understand the limitation and document it. This is important for API design: if your collection needs to yield references that depend on a temporary borrow, you might need GATs or a different API design (like returning owned values).

How this fit on projects

This concept is optional but informs your design choices and connects to Project 10’s safe abstraction design.

Definitions & key terms

GATs: Generic Associated Types.
Lending iterator: Iterator with items borrowing from self per call.

Mental model diagram (ASCII)

next(&mut self) -> Item<'a>
Item borrows from self

How it works (step-by-step)

next borrows self.
Item is tied to that borrow.
Borrow ends before next call.

Minimal concrete example

trait LendingIterator {
    type Item<'a> where Self: 'a;
    fn next<'a>(&'a mut self) -> Option<Self::Item<'a>>;
}

Common misconceptions

“GATs solve all iterator issues.” They solve specific lifetime issues only.

Check-your-understanding questions

Why can’t the standard Iterator express lending iterators?
What is the benefit of GATs here?

Check-your-understanding answers

Item is a single type, not dependent on borrow lifetime.
It allows Item to be parameterized by lifetime.

Real-world applications

Streaming parsers and tokenizers.

Where you’ll apply it

This project: §8 Extensions.
Also used in: Project 10: Capstone.

References

Rust RFCs on GATs.

Key insights

GATs unlock iterators that borrow from self per call, enabling more expressive APIs.

Summary

GATs are the future of advanced iterator patterns, but they are optional for basic collections.

Homework/Exercises to practice the concept

Write a dummy LendingIterator trait and implement it for a slice wrapper.

Solutions to the homework/exercises

Use &'a [T] and return a subslice per call.

3. Project Specification

3.1 What You Will Build

A crate iter_lab with a custom collection and a borrowed iterator that yields &T, plus tests and a CLI demo.

3.2 Functional Requirements

Implement iter() returning Iter<'a, T>.
Iterator yields &T and stops at end.
Mutation during iteration is forbidden by the type system.
CLI demo shows iteration and mutation error case.

3.3 Non-Functional Requirements

Safety: No invalid references.
Clarity: API mirrors standard iterators.

3.4 Example Usage / Output

$ cargo run --example iter_demo
item: 10
item: 20
item: 30
exit code: 0

3.5 Data Formats / Schemas / Protocols

Iter<'a, T> { slice: &'a [T], index: usize }.

3.6 Edge Cases

Empty collection.
Single element.

3.7 Real World Outcome

Deterministic demo plus failure case.

3.7.1 How to Run (Copy/Paste)

cargo run --example iter_demo

3.7.2 Golden Path Demo (Deterministic)

Use fixed collection [10,20,30].

3.7.3 CLI Transcript (Success)

$ cargo run --example iter_demo
item: 10
item: 20
item: 30
exit code: 0

3.7.4 Failure Demo (Mutation Attempt)

$ cargo run --example iter_demo -- --mutate
error: cannot borrow as mutable while iterating
exit code: 2

4. Solution Architecture

4.1 High-Level Design

Collection -> Iter<'a> -> &T

4.2 Key Components

Component	Responsibility	Key Decisions
Collection	Store data	Vec
Iter<’a>	Borrowed iterator	slice + index
CLI demo	Show iteration	deterministic dataset

4.4 Data Structures (No Full Code)

struct Iter<'a, T> { slice: &'a [T], index: usize }

4.4 Algorithm Overview

Key Algorithm: next

Check if index < len.
Return reference and increment index.

Complexity Analysis:

Time: O(1) per call
Space: O(1)

5. Implementation Guide

5.1 Development Environment Setup

cargo new iter_lab
cd iter_lab

5.2 Project Structure

iter_lab/
├── src/
│   ├── lib.rs
│   └── iter.rs
└── examples/
    └── iter_demo.rs

5.3 The Core Question You’re Answering

“How does Rust express that an iterator cannot outlive the data it borrows?”

5.4 Concepts You Must Understand First

Iterator trait basics.
Borrowing during iteration.
Lifetimes in struct definitions.

5.5 Questions to Guide Your Design

How will you store the borrow inside the iterator?
Should your iterator be ExactSizeIterator?
How will you show the mutation error case?

5.6 Thinking Exercise

Write the iterator struct and annotate the lifetime on paper.

5.7 The Interview Questions They’ll Ask

“Why does Rust forbid mutation during iteration?”
“What is a lending iterator?”
“How do lifetimes work in iterators?”

5.8 Hints in Layers

Hint 1: Use a slice reference in the iterator. Hint 2: Implement Iterator with Item = &'a T.

5.9 Books That Will Help

| Topic | Book | Chapter | |—|—|—| | Iterators | TRPL | Ch. 13 | | Lifetimes | TRPL | Ch. 10 |

5.10 Implementation Phases

Phase 1: Iterator Skeleton (2 days)

Implement Iter<'a, T>.

Phase 2: Trait Implementation (2 days)

Implement Iterator and ExactSizeIterator.

Phase 3: Demo and Tests (1-2 days)

CLI demo and edge case tests.

5.11 Key Implementation Decisions

6. Testing Strategy

6.1 Test Categories

6.2 Critical Test Cases

Iterator yields correct elements.
Iterator ends after last element.
Mutation during iteration fails.

6.3 Test Data

[10,20,30]

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

7.2 Debugging Strategies

Use compiler error messages to trace lifetime mismatches.

7.3 Performance Traps

Cloning items unnecessarily.

8. Extensions & Challenges

8.1 Beginner Extensions

Add iter_mut().

8.2 Intermediate Extensions

Implement a consuming iterator.

8.3 Advanced Extensions

Explore GAT-based lending iterator.

9. Real-World Connections

9.1 Industry Applications

Collections in standard libraries.
Streaming parsers.

itertools crate.

9.3 Interview Relevance

Explain lifetime ties in iterators.

10. Resources

10.1 Essential Reading

TRPL Ch. 13, 10.

10.2 Video Resources

RustConf iterator talks.

10.3 Tools & Documentation

Rust std Iterator docs.

11. Self-Assessment Checklist

11.1 Understanding

I can explain why iterators borrow the collection.
I can explain why mutation is forbidden.

11.2 Implementation

Iterator passes all tests.

11.3 Growth

I can explain lending iterators in interviews.

12. Submission / Completion Criteria

Minimum Viable Completion:

Iterator yields &T correctly.
CLI demo shows deterministic output and failure case.

Full Completion:

iter_mut and consuming iterator implemented.

Excellence (Going Above & Beyond):

GAT-based lending iterator.