Walking a collection without knowing how it is stored: where the position lives, how generators make it lazy, and what goes wrong when the collection changes under you.
Open your order history in a delivery app and scroll. Four orders appear, then four more, then three. The screen never asks for "the orders table"; it asks for the next one, and something behind it decides when to go back to the server. That something is an iterator: an object that knows where you are in a collection, hands out the next element, and keeps the way the collection is stored to itself.
That is the Iterator pattern, and it is the one pattern most programmers use every day without meaning to: the for loop. This lesson builds the pattern by hand for one concrete problem, paging through orders, then shows what the languages give you for free (generators and lazy sequences) and what can go wrong when the collection changes while you walk it. It is also behind chess, where every piece hands back the squares it attacks one at a time, and behind the file-system lesson's find follow-up in the in-memory file system.
A bookmark is an iterator: the book keeps no place, each reader's bookmark records where they are, and a new read starts with a fresh one.
The first version: ask for page n#
The first version has one function, history_page(store, page, size). The screen asks for page 0, then 1, then 2. The function asks the store for the whole table and slices out the page:
# history_v1.py: the screen asks for "page n", and the store hands over everything
from dataclasses import dataclass
@dataclass(frozen=True)
class Order:
id: int
amount: int # rupees
class OrderStore:
"""A stand-in for the orders table. It counts what it is asked to read."""
def __init__(self, orders: list) -> None:
self.orders = list(orders) # newest first
self.fetches, self.rows_read = 0, 0
def all_rows(self) -> list:
self.fetches += 1
self.rows_read += len(self.orders)
return list(self.orders)
def add(self, order: Order) -> None: # a new order is the newest
self.orders.insert(0, order)
ORDERS = [Order(id, amount) for id, amount in [
(1011, 520), (1010, 150), (1009, 2200), (1008, 45), (1007, 310), (1006, 980),
(1005, 75), (1004, 640), (1003, 90), (1002, 1200), (1001, 250)]]
def history_page(store: OrderStore, page: int, size: int) -> list: # pages are numbered from 0
rows = store.all_rows()
return rows[page * size:(page + 1) * size]
def ids(orders: list) -> str:
return " ".join(str(o.id) for o in orders)
store = OrderStore(ORDERS)
print("-- scrolling the history, 4 per page")
for page in range(3):
print(f"page {page + 1}: {ids(history_page(store, page, 4))}")
print(f"store reads: {store.fetches} fetches, {store.rows_read} rows")
print("-- a new order arrives after page 1")
store = OrderStore(ORDERS)
first = history_page(store, 0, 4)
store.add(Order(1012, 300))
second = history_page(store, 1, 4)
print(f"page 1: {ids(first)}")
print(f"page 2: {ids(second)}")
twice = [o.id for o in first if o in second]
print("seen twice: " + (" ".join(map(str, twice)) if twice else "none"))// HistoryV1.java: the screen asks for "page n", and the store hands over everything
import java.util.ArrayList;
import java.util.List;
class HistoryV1 {
record Order(int id, int amount) {} // amount in rupees
// A stand-in for the orders table. It counts what it is asked to read.
static class OrderStore {
final List<Order> orders; // newest first
int fetches = 0;
int rowsRead = 0;
OrderStore(List<Order> orders) { this.orders = new ArrayList<>(orders); }
List<Order> allRows() {
fetches++;
rowsRead += orders.size();
return new ArrayList<>(orders);
}
void add(Order order) { orders.add(0, order); } // a new order is the newest
}
static final List<Order> ORDERS = List.of(
new Order(1011, 520), new Order(1010, 150), new Order(1009, 2200), new Order(1008, 45),
new Order(1007, 310), new Order(1006, 980), new Order(1005, 75), new Order(1004, 640),
new Order(1003, 90), new Order(1002, 1200), new Order(1001, 250));
static List<Order> historyPage(OrderStore store, int page, int size) { // pages are numbered from 0
List<Order> rows = store.allRows();
int from = Math.min(page * size, rows.size());
int to = Math.min((page + 1) * size, rows.size());
return rows.subList(from, to);
}
static String ids(List<Order> orders) {
List<String> out = new ArrayList<>();
for (Order o : orders) out.add(String.valueOf(o.id()));
return String.join(" ", out);
}
public static void main(String[] args) {
OrderStore store = new OrderStore(ORDERS);
System.out.println("-- scrolling the history, 4 per page");
for (int page = 0; page < 3; page++) {
System.out.println("page " + (page + 1) + ": " + ids(historyPage(store, page, 4)));
}
System.out.println("store reads: " + store.fetches + " fetches, " + store.rowsRead + " rows");
System.out.println("-- a new order arrives after page 1");
store = new OrderStore(ORDERS);
List<Order> first = historyPage(store, 0, 4);
store.add(new Order(1012, 300));
List<Order> second = historyPage(store, 1, 4);
System.out.println("page 1: " + ids(first));
System.out.println("page 2: " + ids(second));
List<Order> twice = new ArrayList<>();
for (Order o : first) if (second.contains(o)) twice.add(o);
System.out.println("seen twice: " + (twice.isEmpty() ? "none" : ids(twice)));
}
}// history_v1.cpp: the screen asks for "page n", and the store hands over everything
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Order {
int id;
int amount; // rupees
bool operator==(const Order& other) const { return id == other.id && amount == other.amount; }
};
// A stand-in for the orders table. It counts what it is asked to read.
class OrderStore {
public:
explicit OrderStore(std::vector<Order> orders) : orders_(std::move(orders)) {} // newest first
std::vector<Order> allRows() {
fetches++;
rowsRead += static_cast<int>(orders_.size());
return orders_;
}
void add(const Order& order) { orders_.insert(orders_.begin(), order); } // a new order is the newest
int fetches = 0;
int rowsRead = 0;
private:
std::vector<Order> orders_;
};
const std::vector<Order> ORDERS = {
{1011, 520}, {1010, 150}, {1009, 2200}, {1008, 45}, {1007, 310}, {1006, 980},
{1005, 75}, {1004, 640}, {1003, 90}, {1002, 1200}, {1001, 250}};
std::vector<Order> historyPage(OrderStore& store, size_t page, size_t size) { // pages are numbered from 0
std::vector<Order> rows = store.allRows();
size_t from = std::min(page * size, rows.size());
size_t to = std::min((page + 1) * size, rows.size());
return std::vector<Order>(rows.begin() + from, rows.begin() + to);
}
std::string ids(const std::vector<Order>& orders) {
std::string out;
for (size_t i = 0; i < orders.size(); i++) out += (i ? " " : "") + std::to_string(orders[i].id);
return out;
}
int main() {
OrderStore store(ORDERS);
std::cout << "-- scrolling the history, 4 per page\n";
for (size_t page = 0; page < 3; page++) {
std::cout << "page " << page + 1 << ": " << ids(historyPage(store, page, 4)) << "\n";
}
std::cout << "store reads: " << store.fetches << " fetches, " << store.rowsRead << " rows\n";
std::cout << "-- a new order arrives after page 1\n";
OrderStore fresh(ORDERS);
std::vector<Order> first = historyPage(fresh, 0, 4);
fresh.add({1012, 300});
std::vector<Order> second = historyPage(fresh, 1, 4);
std::cout << "page 1: " << ids(first) << "\n";
std::cout << "page 2: " << ids(second) << "\n";
std::vector<Order> twice;
for (const Order& o : first) {
if (std::find(second.begin(), second.end(), o) != second.end()) twice.push_back(o);
}
std::cout << "seen twice: " << (twice.empty() ? "none" : ids(twice)) << "\n";
}// historyV1.js: the screen asks for "page n", and the store hands over everything
class Order {
constructor(id, amount) {
this.id = id;
this.amount = amount; // rupees
}
}
class OrderStore {
// A stand-in for the orders table. It counts what it is asked to read.
constructor(orders) {
this.orders = [...orders]; // newest first
this.fetches = 0;
this.rowsRead = 0;
}
allRows() {
this.fetches += 1;
this.rowsRead += this.orders.length;
return [...this.orders];
}
add(order) {
// a new order is the newest
this.orders.unshift(order);
}
}
const ORDERS = [
[1011, 520], [1010, 150], [1009, 2200], [1008, 45], [1007, 310], [1006, 980],
[1005, 75], [1004, 640], [1003, 90], [1002, 1200], [1001, 250],
].map(([id, amount]) => new Order(id, amount));
function historyPage(store, page, size) {
// pages are numbered from 0
const rows = store.allRows();
return rows.slice(page * size, (page + 1) * size);
}
const ids = (orders) => orders.map((o) => o.id).join(" ");
let store = new OrderStore(ORDERS);
console.log("-- scrolling the history, 4 per page");
for (let page = 0; page < 3; page++) {
console.log(`page ${page + 1}: ${ids(historyPage(store, page, 4))}`);
}
console.log(`store reads: ${store.fetches} fetches, ${store.rowsRead} rows`);
console.log("-- a new order arrives after page 1");
store = new OrderStore(ORDERS);
const first = historyPage(store, 0, 4);
store.add(new Order(1012, 300));
const second = historyPage(store, 1, 4);
console.log(`page 1: ${ids(first)}`);
console.log(`page 2: ${ids(second)}`);
const twice = first.filter((o) => second.some((s) => s.id === o.id));
console.log("seen twice: " + (twice.length ? ids(twice) : "none"));-- scrolling the history, 4 per page
page 1: 1011 1010 1009 1008
page 2: 1007 1006 1005 1004
page 3: 1003 1002 1001
store reads: 3 fetches, 33 rows
-- a new order arrives after page 1
page 1: 1011 1010 1009 1008
page 2: 1008 1007 1006 1005
seen twice: 1008It works for the first screen, and the output shows two problems. The store was asked for everything three times, which is 33 rows to show 11. And when a new order (1012) arrives between the first and the second page, page 2 starts at position 4 of a list that has grown by one, so order 1008 appears on both pages. Nothing crashed. The user just sees a repeated row.
- The caller knows how the data is cut. The screen has to track page numbers and a page size, and do the arithmetic. An off-by-one there shows up as a missing or repeated row.
- Every page rereads everything. The function has no memory, so each call starts from the top. The measured cost above is 33 rows for 11 orders, and it grows with the table.
- A position by number is fragile. Position 4 means something different once a new order arrives. That is how 1008 appeared twice.
- The representation leaks. The store has to hand over a list that can be sliced. A store that reads from a cursor, a file or a remote service can't.
Count the reads
There are 11 orders and pages of 4. The first version reads the whole table for every page. A design that fetches each page once and remembers where it stopped needs how many fetches and rows, and what is the smallest thing it has to remember between pages?
One strong answer
Three fetches and 11 rows, and the id of the last order it showed. Eleven orders in pages of 4 are 4 + 4 + 3, so three fetches. The first version's three full reads cost 33 rows. What has to be remembered is not a page number but a place: the last id seen, so the next fetch is "the 4 orders older than 1008". The id doesn't move when a new order arrives, which is why this design doesn't show 1008 twice.
The pattern#
The book that named the pattern (Design Patterns, 1994, by Gamma, Helm, Johnson and Vlissides) states its intent in one sentence: "Provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation."
In the order history that gives four roles:
| Role | In the order history | Its one job |
|---|---|---|
| Aggregate (the collection) | OrderHistory |
Hand out a fresh iterator each time someone wants to walk it |
| Iterator (the interface) | has_next() and next() (in Python, __next__) |
Say whether there is another element, and return it |
| Concrete iterator | PageIterator |
Remember where this walk is (a buffer, a position, the last id) and fetch the next page only when the buffer runs out |
| Client | the screen's loop | Ask for the next order, and know nothing else |
%% title: Iterator: the order history
classDiagram
class Iterable {
<<interface>>
+iterator() Iterator
}
class Iterator {
<<interface>>
+has_next() bool
+next() Order
}
class OrderHistory {
-size int
+iterator() PageIterator
}
class PageIterator {
-buffer list
-pos int
-cursor int
+has_next() bool
+next() Order
}
class OrderStore {
+fetch(before, limit) list
}
Iterable <|.. OrderHistory
Iterator <|.. PageIterator
OrderHistory ..> PageIterator : creates
PageIterator --> OrderStore : fetches fromRead the arrows. The aggregate and the iterator are two different objects, and that is the heart of the design. OrderHistory knows how to make an iterator but never holds a position, so it can be walked twice, or by two screens at once, each with its own PageIterator. The iterator holds the position (pos, cursor) and the buffer, and the only thing it asks of the store is fetch(before, limit). The loop sees two methods, so the store could change from a table to a file or a network call, and the loop would not.
The iterator fetches a page only when its buffer is empty: one fetch of four orders serves four next calls, and the store is never asked early.
The code#
The history hands out an iterator, and the iterator fetches a page only when it has used up the last one:
# history.py: Iterator: the walker keeps the position, the history keeps the orders
from dataclasses import dataclass
from itertools import islice
from typing import Optional
@dataclass(frozen=True)
class Order:
id: int
amount: int # rupees
class OrderStore:
"""A stand-in for the orders table. It counts what it is asked to read."""
def __init__(self, orders: list) -> None:
self.orders = list(orders) # newest first
self.fetches, self.rows_read = 0, 0
def fetch(self, before: Optional[int], limit: int) -> list: # orders older than `before`, newest first
self.fetches += 1
page = [o for o in self.orders if before is None or o.id < before][:limit]
self.rows_read += len(page)
return page
def add(self, order: Order) -> None: # a new order is the newest
self.orders.insert(0, order)
class PageIterator: # the iterator: where this walk has got to, and nothing else
def __init__(self, store: OrderStore, size: int) -> None:
self.store, self.size = store, size
self.buffer, self.pos, self.cursor, self.done = [], 0, None, False
def __iter__(self) -> "PageIterator":
return self
def __next__(self) -> Order:
if self.pos >= len(self.buffer): # the buffer is used up: fetch the next page, only now
if self.done:
raise StopIteration
page = self.store.fetch(self.cursor, self.size)
if not page:
self.done = True
raise StopIteration
self.buffer, self.pos, self.cursor = page, 0, page[-1].id # remember the last id, not an offset
self.done = len(page) < self.size
order = self.buffer[self.pos]
self.pos += 1
return order
class OrderHistory: # the aggregate: a fresh iterator for every walk
def __init__(self, store: OrderStore, size: int) -> None:
self.store, self.size = store, size
def __iter__(self) -> PageIterator:
return PageIterator(self.store, self.size)
ORDERS = [Order(id, amount) for id, amount in [
(1011, 520), (1010, 150), (1009, 2200), (1008, 45), (1007, 310), (1006, 980),
(1005, 75), (1004, 640), (1003, 90), (1002, 1200), (1001, 250)]]
def ids(orders: list) -> str:
return " ".join(str(o.id) for o in orders)
store = OrderStore(ORDERS)
history = OrderHistory(store, 4)
print("-- scrolling the history, 4 per page")
walk = iter(history)
for page in range(3):
print(f"page {page + 1}: {ids(list(islice(walk, 4)))}")
print(f"store reads: {store.fetches} fetches, {store.rows_read} rows")
print("-- a new order arrives after page 1")
store2 = OrderStore(ORDERS)
walk2 = iter(OrderHistory(store2, 4))
first = list(islice(walk2, 4))
store2.add(Order(1012, 300))
second = list(islice(walk2, 4))
print(f"page 1: {ids(first)}")
print(f"page 2: {ids(second)}")
twice = [o.id for o in first if o in second]
print("seen twice: " + (" ".join(map(str, twice)) if twice else "none"))
print("-- the iterable and the iterator")
print(f"walk 1: {sum(1 for _ in history)} orders")
print(f"walk 2: {sum(1 for _ in history)} orders")
print(f"the first iterator, asked again: {sum(1 for _ in walk)} orders")// History.java: Iterator: the walker keeps the position, the history keeps the orders
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
class HistoryDemo {
record Order(int id, int amount) {} // amount in rupees
// A stand-in for the orders table. It counts what it is asked to read.
static class OrderStore {
final List<Order> orders; // newest first
int fetches = 0;
int rowsRead = 0;
OrderStore(List<Order> orders) { this.orders = new ArrayList<>(orders); }
List<Order> fetch(Integer before, int limit) { // orders older than `before`, newest first
fetches++;
List<Order> page = new ArrayList<>();
for (Order o : orders) {
if (page.size() < limit && (before == null || o.id() < before)) page.add(o);
}
rowsRead += page.size();
return page;
}
void add(Order order) { orders.add(0, order); } // a new order is the newest
}
// the iterator: where this walk has got to, and nothing else
static class PageIterator implements Iterator<Order> {
final OrderStore store;
final int size;
List<Order> buffer = new ArrayList<>();
int pos = 0;
Integer cursor = null;
boolean done = false;
PageIterator(OrderStore store, int size) { this.store = store; this.size = size; }
public boolean hasNext() {
if (pos < buffer.size()) return true;
if (done) return false; // the buffer is used up: fetch the next page, only now
List<Order> page = store.fetch(cursor, size);
if (page.isEmpty()) {
done = true;
return false;
}
buffer = page;
pos = 0;
cursor = page.get(page.size() - 1).id(); // remember the last id, not an offset
done = page.size() < size;
return true;
}
public Order next() {
if (!hasNext()) throw new NoSuchElementException();
return buffer.get(pos++);
}
}
// the aggregate: a fresh iterator for every walk
static class OrderHistory implements Iterable<Order> {
final OrderStore store;
final int size;
OrderHistory(OrderStore store, int size) { this.store = store; this.size = size; }
public Iterator<Order> iterator() { return new PageIterator(store, size); }
}
static final List<Order> ORDERS = List.of(
new Order(1011, 520), new Order(1010, 150), new Order(1009, 2200), new Order(1008, 45),
new Order(1007, 310), new Order(1006, 980), new Order(1005, 75), new Order(1004, 640),
new Order(1003, 90), new Order(1002, 1200), new Order(1001, 250));
static String ids(List<Order> orders) {
List<String> out = new ArrayList<>();
for (Order o : orders) out.add(String.valueOf(o.id()));
return String.join(" ", out);
}
static List<Order> take(int n, Iterator<Order> it) { // up to n values, asking the iterator only as needed
List<Order> out = new ArrayList<>();
while (out.size() < n && it.hasNext()) out.add(it.next());
return out;
}
static int count(Iterator<Order> it) {
int n = 0;
while (it.hasNext()) { it.next(); n++; }
return n;
}
public static void main(String[] args) {
OrderStore store = new OrderStore(ORDERS);
OrderHistory history = new OrderHistory(store, 4);
System.out.println("-- scrolling the history, 4 per page");
Iterator<Order> walk = history.iterator();
for (int page = 0; page < 3; page++) {
System.out.println("page " + (page + 1) + ": " + ids(take(4, walk)));
}
System.out.println("store reads: " + store.fetches + " fetches, " + store.rowsRead + " rows");
System.out.println("-- a new order arrives after page 1");
OrderStore store2 = new OrderStore(ORDERS);
Iterator<Order> walk2 = new OrderHistory(store2, 4).iterator();
List<Order> first = take(4, walk2);
store2.add(new Order(1012, 300));
List<Order> second = take(4, walk2);
System.out.println("page 1: " + ids(first));
System.out.println("page 2: " + ids(second));
List<Order> twice = new ArrayList<>();
for (Order o : first) if (second.contains(o)) twice.add(o);
System.out.println("seen twice: " + (twice.isEmpty() ? "none" : ids(twice)));
System.out.println("-- the iterable and the iterator");
System.out.println("walk 1: " + count(history.iterator()) + " orders");
System.out.println("walk 2: " + count(history.iterator()) + " orders");
System.out.println("the first iterator, asked again: " + count(walk) + " orders");
}
}// history.cpp: Iterator: the walker keeps the position, the history keeps the orders
#include <iostream>
#include <memory>
#include <optional>
#include <string>
#include <vector>
struct Order {
int id;
int amount; // rupees
bool operator==(const Order& other) const { return id == other.id && amount == other.amount; }
};
// A stand-in for the orders table. It counts what it is asked to read.
class OrderStore {
public:
explicit OrderStore(std::vector<Order> orders) : orders_(std::move(orders)) {} // newest first
std::vector<Order> fetch(std::optional<int> before, size_t limit) { // orders older than `before`, newest first
fetches++;
std::vector<Order> page;
for (const Order& o : orders_) {
if (page.size() < limit && (!before || o.id < *before)) page.push_back(o);
}
rowsRead += static_cast<int>(page.size());
return page;
}
void add(const Order& order) { orders_.insert(orders_.begin(), order); } // a new order is the newest
int fetches = 0;
int rowsRead = 0;
private:
std::vector<Order> orders_;
};
class OrderHistory { // the aggregate: begin() starts a fresh walk every time
public:
OrderHistory(OrderStore& store, size_t size) : store_(store), size_(size) {}
class Iterator { // the iterator: where this walk has got to, and nothing else
public:
Iterator() = default; // the end
Iterator(OrderStore& store, size_t size) : state_(std::make_shared<State>(State{&store, size, {}, 0, std::nullopt, false})) {}
const Order& operator*() const {
fill();
return state_->buffer[state_->pos];
}
Iterator& operator++() {
fill();
state_->pos++;
return *this;
}
bool operator!=(const Iterator& other) const { return atEnd() != other.atEnd(); }
private:
struct State {
OrderStore* store;
size_t size;
std::vector<Order> buffer;
size_t pos;
std::optional<int> cursor;
bool done;
};
std::shared_ptr<State> state_;
void fill() const { // the buffer is used up: fetch the next page, only now
State& s = *state_;
if (s.pos < s.buffer.size() || s.done) return;
std::vector<Order> page = s.store->fetch(s.cursor, s.size);
if (page.empty()) {
s.done = true;
return;
}
s.cursor = page.back().id; // remember the last id, not an offset
s.done = page.size() < s.size;
s.buffer = std::move(page);
s.pos = 0;
}
bool atEnd() const {
if (!state_) return true;
fill();
return state_->pos >= state_->buffer.size();
}
};
Iterator begin() const { return Iterator(store_, size_); }
Iterator end() const { return Iterator(); }
private:
OrderStore& store_;
size_t size_;
};
const std::vector<Order> ORDERS = {
{1011, 520}, {1010, 150}, {1009, 2200}, {1008, 45}, {1007, 310}, {1006, 980},
{1005, 75}, {1004, 640}, {1003, 90}, {1002, 1200}, {1001, 250}};
std::string ids(const std::vector<Order>& orders) {
std::string out;
for (size_t i = 0; i < orders.size(); i++) out += (i ? " " : "") + std::to_string(orders[i].id);
return out;
}
std::vector<Order> take(size_t n, OrderHistory::Iterator& it, const OrderHistory::Iterator& end) { // up to n values
std::vector<Order> out;
while (out.size() < n && it != end) {
out.push_back(*it);
++it;
}
return out;
}
int count(OrderHistory::Iterator& it, const OrderHistory::Iterator& end) {
int n = 0;
for (; it != end; ++it) n++;
return n;
}
int main() {
OrderStore store(ORDERS);
OrderHistory history(store, 4);
std::cout << "-- scrolling the history, 4 per page\n";
OrderHistory::Iterator walk = history.begin();
for (int page = 1; page <= 3; page++) {
std::cout << "page " << page << ": " << ids(take(4, walk, history.end())) << "\n";
}
std::cout << "store reads: " << store.fetches << " fetches, " << store.rowsRead << " rows\n";
std::cout << "-- a new order arrives after page 1\n";
OrderStore store2(ORDERS);
OrderHistory history2(store2, 4);
OrderHistory::Iterator walk2 = history2.begin();
std::vector<Order> first = take(4, walk2, history2.end());
store2.add({1012, 300});
std::vector<Order> second = take(4, walk2, history2.end());
std::cout << "page 1: " << ids(first) << "\n";
std::cout << "page 2: " << ids(second) << "\n";
std::vector<Order> twice;
for (const Order& o : first) {
for (const Order& s : second) {
if (o == s) twice.push_back(o);
}
}
std::cout << "seen twice: " << (twice.empty() ? "none" : ids(twice)) << "\n";
std::cout << "-- the iterable and the iterator\n";
OrderHistory::Iterator a = history.begin();
OrderHistory::Iterator b = history.begin();
std::cout << "walk 1: " << count(a, history.end()) << " orders\n";
std::cout << "walk 2: " << count(b, history.end()) << " orders\n";
std::cout << "the first iterator, asked again: " << count(walk, history.end()) << " orders\n";
}// history.js: Iterator: the walker keeps the position, the history keeps the orders
class Order {
constructor(id, amount) {
this.id = id;
this.amount = amount; // rupees
}
}
class OrderStore {
// A stand-in for the orders table. It counts what it is asked to read.
constructor(orders) {
this.orders = [...orders]; // newest first
this.fetches = 0;
this.rowsRead = 0;
}
fetch(before, limit) {
// orders older than `before`, newest first
this.fetches += 1;
const page = this.orders.filter((o) => before === null || o.id < before).slice(0, limit);
this.rowsRead += page.length;
return page;
}
add(order) {
// a new order is the newest
this.orders.unshift(order);
}
}
class PageIterator {
// the iterator: where this walk has got to, and nothing else
constructor(store, size) {
this.store = store;
this.size = size;
this.buffer = [];
this.pos = 0;
this.cursor = null;
this.done = false;
}
[Symbol.iterator]() {
return this;
}
next() {
if (this.pos >= this.buffer.length) {
// the buffer is used up: fetch the next page, only now
if (this.done) {
return { value: undefined, done: true };
}
const page = this.store.fetch(this.cursor, this.size);
if (page.length === 0) {
this.done = true;
return { value: undefined, done: true };
}
this.buffer = page;
this.pos = 0;
this.cursor = page[page.length - 1].id; // remember the last id, not an offset
this.done = page.length < this.size;
}
const order = this.buffer[this.pos];
this.pos += 1;
return { value: order, done: false };
}
}
class OrderHistory {
// the aggregate: a fresh iterator for every walk
constructor(store, size) {
this.store = store;
this.size = size;
}
[Symbol.iterator]() {
return new PageIterator(this.store, this.size);
}
}
const ORDERS = [
[1011, 520], [1010, 150], [1009, 2200], [1008, 45], [1007, 310], [1006, 980],
[1005, 75], [1004, 640], [1003, 90], [1002, 1200], [1001, 250],
].map(([id, amount]) => new Order(id, amount));
const ids = (orders) => orders.map((o) => o.id).join(" ");
function take(n, iterator) {
// up to n values, asking the iterator exactly n times
const out = [];
while (out.length < n) {
const step = iterator.next();
if (step.done) break;
out.push(step.value);
}
return out;
}
const count = (iterable) => {
let n = 0;
for (const _ of iterable) n += 1;
return n;
};
const store = new OrderStore(ORDERS);
const history = new OrderHistory(store, 4);
console.log("-- scrolling the history, 4 per page");
const walk = history[Symbol.iterator]();
for (let page = 0; page < 3; page++) {
console.log(`page ${page + 1}: ${ids(take(4, walk))}`);
}
console.log(`store reads: ${store.fetches} fetches, ${store.rowsRead} rows`);
console.log("-- a new order arrives after page 1");
const store2 = new OrderStore(ORDERS);
const walk2 = new OrderHistory(store2, 4)[Symbol.iterator]();
const first = take(4, walk2);
store2.add(new Order(1012, 300));
const second = take(4, walk2);
console.log(`page 1: ${ids(first)}`);
console.log(`page 2: ${ids(second)}`);
const twice = first.filter((o) => second.some((s) => s.id === o.id));
console.log("seen twice: " + (twice.length ? ids(twice) : "none"));
console.log("-- the iterable and the iterator");
console.log(`walk 1: ${count(history)} orders`);
console.log(`walk 2: ${count(history)} orders`);
console.log(`the first iterator, asked again: ${count(walk)} orders`);-- scrolling the history, 4 per page
page 1: 1011 1010 1009 1008
page 2: 1007 1006 1005 1004
page 3: 1003 1002 1001
store reads: 3 fetches, 11 rows
-- a new order arrives after page 1
page 1: 1011 1010 1009 1008
page 2: 1007 1006 1005 1004
seen twice: none
-- the iterable and the iterator
walk 1: 11 orders
walk 2: 11 orders
the first iterator, asked again: 0 ordersCheck by hand. Eleven orders in pages of 4 are 4 + 4 + 3, so the store is asked three times and returns 11 rows, not 33. The third page has 3 orders, which is fewer than the page size, so the iterator knows it has reached the end and doesn't ask a fourth time. When order 1012 arrives after page 1, the iterator's next fetch is "older than 1008", so page 2 is 1007 to 1004 and nothing repeats. The history can be walked twice (11 orders each time), but the iterator from the first walk, asked again, has nothing left: 0 orders.
What each language brings to the same design:
- Python: the
forloop is the pattern.iter(history)calls__iter__, and the loop calls__next__until it raisesStopIteration.PageIteratorreturns itself from__iter__, as every Python iterator does. - Java:
OrderHistory implements Iterable<Order>andPageIterator implements Iterator<Order>; that makes the enhancedforloop work.hasNextdoes the fetch, sonextcan rely on it. - C++:
begin()andend()plus an iterator with*,++and!=make a range-basedforwork. The walk's state sits behind ashared_ptr, so copies of an iterator share one walk: it is a single-pass input iterator, like the ones that read a stream. - JavaScript: an object with
[Symbol.iterator]()returning an object withnext(), which returns{ value, done }; that is whatfor...ofand the spread syntax call.
Iterable, or iterator?#
Two words are easy to mix up, and the mix-up causes a real bug. An iterable is something you can start a walk over (OrderHistory): ask it for an iterator as many times as you like. An iterator is one walk in progress (PageIterator): it moves forward only, and when it reaches the end, it is finished.
The last three lines of the output show it. Two for loops over history each count 11. A loop over the first iterator counts 0, because that walk was used up by the three pages. Programmers hit this when they store iter(x) or a stream in a variable and loop over it twice, and the second loop silently does nothing. If a function needs to loop twice, take the iterable, not the iterator.
Used up
walk = iter(history) is looped over once to the end. Then the same two lines are run again: for order in walk: .... What happens, and what would you change to loop twice?
One strong answer
The second loop does nothing and raises no error: the iterator is already at the end. It is one walk in progress, and it moves forward only. To loop twice, keep the iterable (history) and start a new walk each time, as for order in history: does. In Java that is history.iterator() again, in C++ history.begin() again, in JavaScript history[Symbol.iterator]() again.
Lazy sequences and generators#
An iterator that fetches only when asked is lazy: nothing is read until someone pulls the next value. That makes it composable. You can put a filter in front of it and a limit after it, and the pipeline reads only what the last stage needs. Writing the iterator class by hand is the verbose way; Python and JavaScript have a shorter one, a generator, a function that pauses at each yield until it is asked again.
# lazy.py: lazy sequences: nothing is read until someone asks for the next value
from dataclasses import dataclass
from typing import Optional
@dataclass(frozen=True)
class Order:
id: int
amount: int # rupees
class OrderStore:
"""A stand-in for the orders table. It counts what it is asked to read."""
def __init__(self, orders: list) -> None:
self.orders = list(orders) # newest first
self.fetches, self.rows_read = 0, 0
def fetch(self, before: Optional[int], limit: int) -> list: # orders older than `before`, newest first
self.fetches += 1
page = [o for o in self.orders if before is None or o.id < before][:limit]
self.rows_read += len(page)
return page
def history(store: OrderStore, size: int): # a generator: it pauses at each yield until it is asked again
cursor = None
while True:
page = store.fetch(cursor, size)
for order in page:
yield order
if len(page) < size:
return
cursor = page[-1].id
def big_orders(orders, minimum: int): # another generator, reading from the first
for order in orders:
if order.amount >= minimum:
yield order
def take(n: int, orders): # stop after n, without asking the source for an (n+1)th
taken = 0
for order in orders:
yield order
taken += 1
if taken == n:
return
ORDERS = [Order(id, amount) for id, amount in [
(1011, 520), (1010, 150), (1009, 2200), (1008, 45), (1007, 310), (1006, 980),
(1005, 75), (1004, 640), (1003, 90), (1002, 1200), (1001, 250)]]
def ids(orders) -> str:
return " ".join(str(o.id) for o in orders)
print("-- eager: list every big order first")
store = OrderStore(ORDERS)
everything = list(history(store, 4))
print(f"big orders: {ids(o for o in everything if o.amount >= 500)}")
print(f"store reads: {store.fetches} fetches, {store.rows_read} rows")
print("-- lazy: pull one at a time, and stop at 3")
store = OrderStore(ORDERS)
pipeline = take(3, big_orders(history(store, 4), 500))
print(f"built the pipeline: {store.fetches} fetches so far")
print(f"first 3 big orders: {ids(pipeline)}")
print(f"store reads: {store.fetches} fetches, {store.rows_read} rows")// Lazy.java: lazy sequences: nothing is read until someone asks for the next value
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
class LazyDemo {
record Order(int id, int amount) {} // amount in rupees
// A stand-in for the orders table. It counts what it is asked to read.
static class OrderStore {
final List<Order> orders; // newest first
int fetches = 0;
int rowsRead = 0;
OrderStore(List<Order> orders) { this.orders = new ArrayList<>(orders); }
List<Order> fetch(Integer before, int limit) { // orders older than `before`, newest first
fetches++;
List<Order> page = new ArrayList<>();
for (Order o : orders) {
if (page.size() < limit && (before == null || o.id() < before)) page.add(o);
}
rowsRead += page.size();
return page;
}
}
static class History implements Iterator<Order> { // pages in only when the buffer runs out
final OrderStore store;
final int size;
List<Order> buffer = new ArrayList<>();
int pos = 0;
Integer cursor = null;
boolean done = false;
History(OrderStore store, int size) { this.store = store; this.size = size; }
public boolean hasNext() {
if (pos < buffer.size()) return true;
if (done) return false;
List<Order> page = store.fetch(cursor, size);
if (page.isEmpty()) {
done = true;
return false;
}
buffer = page;
pos = 0;
cursor = page.get(page.size() - 1).id();
done = page.size() < size;
return true;
}
public Order next() {
if (!hasNext()) throw new NoSuchElementException();
return buffer.get(pos++);
}
}
static class BigOrders implements Iterator<Order> { // reads from another iterator, one order at a time
final Iterator<Order> source;
final int minimum;
Order ahead = null;
BigOrders(Iterator<Order> source, int minimum) { this.source = source; this.minimum = minimum; }
public boolean hasNext() {
while (ahead == null && source.hasNext()) {
Order o = source.next();
if (o.amount() >= minimum) ahead = o;
}
return ahead != null;
}
public Order next() {
if (!hasNext()) throw new NoSuchElementException();
Order o = ahead;
ahead = null;
return o;
}
}
static class Take implements Iterator<Order> { // stop after n, without asking the source for an (n+1)th
final Iterator<Order> source;
int left;
Take(int n, Iterator<Order> source) { this.left = n; this.source = source; }
public boolean hasNext() { return left > 0 && source.hasNext(); }
public Order next() {
if (!hasNext()) throw new NoSuchElementException();
left--;
return source.next();
}
}
static final List<Order> ORDERS = List.of(
new Order(1011, 520), new Order(1010, 150), new Order(1009, 2200), new Order(1008, 45),
new Order(1007, 310), new Order(1006, 980), new Order(1005, 75), new Order(1004, 640),
new Order(1003, 90), new Order(1002, 1200), new Order(1001, 250));
static String ids(Iterator<Order> orders) {
List<String> out = new ArrayList<>();
while (orders.hasNext()) out.add(String.valueOf(orders.next().id()));
return String.join(" ", out);
}
public static void main(String[] args) {
System.out.println("-- eager: list every big order first");
OrderStore store = new OrderStore(ORDERS);
List<Order> everything = new ArrayList<>();
new History(store, 4).forEachRemaining(everything::add);
List<Order> big = new ArrayList<>();
for (Order o : everything) if (o.amount() >= 500) big.add(o);
System.out.println("big orders: " + ids(big.iterator()));
System.out.println("store reads: " + store.fetches + " fetches, " + store.rowsRead + " rows");
System.out.println("-- lazy: pull one at a time, and stop at 3");
store = new OrderStore(ORDERS);
Iterator<Order> pipeline = new Take(3, new BigOrders(new History(store, 4), 500));
System.out.println("built the pipeline: " + store.fetches + " fetches so far");
System.out.println("first 3 big orders: " + ids(pipeline));
System.out.println("store reads: " + store.fetches + " fetches, " + store.rowsRead + " rows");
}
}// lazy.cpp: lazy sequences: nothing is read until someone asks for the next value
#include <functional>
#include <iostream>
#include <memory>
#include <optional>
#include <string>
#include <vector>
struct Order {
int id;
int amount; // rupees
};
// A stand-in for the orders table. It counts what it is asked to read.
class OrderStore {
public:
explicit OrderStore(std::vector<Order> orders) : orders_(std::move(orders)) {} // newest first
std::vector<Order> fetch(std::optional<int> before, size_t limit) { // orders older than `before`, newest first
fetches++;
std::vector<Order> page;
for (const Order& o : orders_) {
if (page.size() < limit && (!before || o.id < *before)) page.push_back(o);
}
rowsRead += static_cast<int>(page.size());
return page;
}
int fetches = 0;
int rowsRead = 0;
private:
std::vector<Order> orders_;
};
// A lazy sequence is a function: each call returns the next order, or nothing when it is over.
using Pull = std::function<std::optional<Order>()>;
Pull history(OrderStore& store, size_t size) { // pages in only when the buffer runs out
struct State {
std::vector<Order> buffer;
size_t pos = 0;
std::optional<int> cursor;
bool done = false;
};
auto s = std::make_shared<State>();
return [&store, size, s]() -> std::optional<Order> {
if (s->pos >= s->buffer.size()) {
if (s->done) return std::nullopt;
std::vector<Order> page = store.fetch(s->cursor, size);
if (page.empty()) {
s->done = true;
return std::nullopt;
}
s->cursor = page.back().id;
s->done = page.size() < size;
s->buffer = std::move(page);
s->pos = 0;
}
return s->buffer[s->pos++];
};
}
Pull bigOrders(Pull source, int minimum) { // reads from another sequence, one order at a time
return [source, minimum]() -> std::optional<Order> {
while (std::optional<Order> o = source()) {
if (o->amount >= minimum) return o;
}
return std::nullopt;
};
}
Pull take(int n, Pull source) { // stop after n, without asking the source for an (n+1)th
auto left = std::make_shared<int>(n);
return [left, source]() -> std::optional<Order> {
if (*left <= 0) return std::nullopt;
(*left)--;
return source();
};
}
const std::vector<Order> ORDERS = {
{1011, 520}, {1010, 150}, {1009, 2200}, {1008, 45}, {1007, 310}, {1006, 980},
{1005, 75}, {1004, 640}, {1003, 90}, {1002, 1200}, {1001, 250}};
std::string ids(const std::vector<Order>& orders) {
std::string out;
for (size_t i = 0; i < orders.size(); i++) out += (i ? " " : "") + std::to_string(orders[i].id);
return out;
}
std::vector<Order> drain(Pull pull) {
std::vector<Order> out;
while (std::optional<Order> o = pull()) out.push_back(*o);
return out;
}
int main() {
std::cout << "-- eager: list every big order first\n";
OrderStore store(ORDERS);
std::vector<Order> everything = drain(history(store, 4));
std::vector<Order> big;
for (const Order& o : everything) {
if (o.amount >= 500) big.push_back(o);
}
std::cout << "big orders: " << ids(big) << "\n";
std::cout << "store reads: " << store.fetches << " fetches, " << store.rowsRead << " rows\n";
std::cout << "-- lazy: pull one at a time, and stop at 3\n";
OrderStore store2(ORDERS);
Pull pipeline = take(3, bigOrders(history(store2, 4), 500));
std::cout << "built the pipeline: " << store2.fetches << " fetches so far\n";
std::cout << "first 3 big orders: " << ids(drain(pipeline)) << "\n";
std::cout << "store reads: " << store2.fetches << " fetches, " << store2.rowsRead << " rows\n";
}// lazy.js: lazy sequences: nothing is read until someone asks for the next value
class Order {
constructor(id, amount) {
this.id = id;
this.amount = amount; // rupees
}
}
class OrderStore {
// A stand-in for the orders table. It counts what it is asked to read.
constructor(orders) {
this.orders = [...orders]; // newest first
this.fetches = 0;
this.rowsRead = 0;
}
fetch(before, limit) {
// orders older than `before`, newest first
this.fetches += 1;
const page = this.orders.filter((o) => before === null || o.id < before).slice(0, limit);
this.rowsRead += page.length;
return page;
}
}
function* history(store, size) {
// a generator: it pauses at each yield until it is asked again
let cursor = null;
while (true) {
const page = store.fetch(cursor, size);
yield* page;
if (page.length < size) return;
cursor = page[page.length - 1].id;
}
}
function* bigOrders(orders, minimum) {
// another generator, reading from the first
for (const order of orders) {
if (order.amount >= minimum) yield order;
}
}
function* take(n, orders) {
// stop after n, without asking the source for an (n+1)th
let taken = 0;
for (const order of orders) {
yield order;
taken += 1;
if (taken === n) return;
}
}
const ORDERS = [
[1011, 520], [1010, 150], [1009, 2200], [1008, 45], [1007, 310], [1006, 980],
[1005, 75], [1004, 640], [1003, 90], [1002, 1200], [1001, 250],
].map(([id, amount]) => new Order(id, amount));
const ids = (orders) => [...orders].map((o) => o.id).join(" ");
console.log("-- eager: list every big order first");
let store = new OrderStore(ORDERS);
const everything = [...history(store, 4)];
console.log(`big orders: ${ids(everything.filter((o) => o.amount >= 500))}`);
console.log(`store reads: ${store.fetches} fetches, ${store.rowsRead} rows`);
console.log("-- lazy: pull one at a time, and stop at 3");
store = new OrderStore(ORDERS);
const pipeline = take(3, bigOrders(history(store, 4), 500));
console.log(`built the pipeline: ${store.fetches} fetches so far`);
console.log(`first 3 big orders: ${ids(pipeline)}`);
console.log(`store reads: ${store.fetches} fetches, ${store.rowsRead} rows`);-- eager: list every big order first
big orders: 1011 1009 1006 1004 1002
store reads: 3 fetches, 11 rows
-- lazy: pull one at a time, and stop at 3
built the pipeline: 0 fetches so far
first 3 big orders: 1011 1009 1006
store reads: 2 fetches, 8 rowsRead the last block of output. The first run builds the whole list of orders before it filters: 3 fetches and 11 rows. The second builds the pipeline, and the store has been asked 0 times. Only when the first big order is pulled does a fetch happen, and the pipeline stops after the third big order (1006, on page 2), so the store is asked 2 times and returns 8 rows, and page 3 is never read. The saving here is small because the table is small; with a million orders and a request for the first three, it is the difference between reading a page or two and reading the whole table.
What each language brings:
- Python and JavaScript: generators, with
yield(andyield*in JavaScript to pass a whole page through). The whole pipeline is three short functions. - Java: no generator syntax. You write the iterator class, as
BigOrdersandTakedo, or useStream, which is lazy in the same way. - C++17: no generators either (C++20 added coroutines, and C++23 the
std::generatortype built on them). The lesson uses a function that returns "the next order, or nothing", and composes functions. It is the same idea in its plainest form.
One more distinction from the book: who drives the walk. Everything above is an external iterator: the client calls next and decides when to stop. An internal iterator takes a function and applies it to every element itself: forEach in JavaScript and Java, std::for_each in C++. Internal is shorter to call, but the client gives up control: a JavaScript or Java forEach can't break (only an exception escapes it), and you can't walk two collections side by side to compare them. A generator gets the best of both: you write it like an internal iterator (a plain loop that yields) and use it like an external one.
Finding the first three big orders lazily reads 2 pages and 8 rows, against 3 pages and 11 rows when the whole list is built first.
When the collection changes under you#
There are two different problems, and the first one is the one the first version showed.
1. The data changes between pages. A position by number moves when something is inserted before it. A position by value does not. The first version's page 2 started at "position 4", so a new order pushed 1008 over the page boundary. The iterator remembers "the last id I saw" and asks for "older than 1008". That is called keyset (or cursor) paging, and it is how most feeds and APIs page. It costs one thing: you can't jump straight to page 7, because a position is a place, not a number.
2. The list you are looping over changes. Removing from a list while a for loop walks it is the classic mistake, and the languages disagree on what happens. We ran the same small loop in each: walk [cancelled, cancelled, ok, cancelled] and remove each cancelled order it meets (remove(o), splice(indexOf(o), 1) in JavaScript, erase in C++):
| Language | What happens | The safe form |
|---|---|---|
| Python | No error. One cancelled order is left behind: ['ok', 'cancelled']. |
orders = [o for o in orders if o != "cancelled"], or loop over a copy |
| JavaScript | No error, the same leftover: [ 'ok', 'cancelled' ]. |
orders.filter(...), or loop over a copy |
| Java | ConcurrentModificationException on the next step (fail-fast). The check is best effort, as the documentation says: remove the second-to-last element and the loop ends early with no exception, so [ok, cancelled, cancelled] ended as [ok, cancelled]. |
orders.removeIf(...), or an Iterator and its remove() |
| C++ | Undefined behaviour. erase invalidates the loop's hidden iterator and the end() it saved at the start. A plain build printed the same leftover as Python, by luck; with AddressSanitizer the same program reports a read past the vector's end. |
the erase-remove idiom (erase(remove_if(...), end)), C++20's std::erase_if, or erase with the iterator it returns |
Python and JavaScript skip an element because the list shifts left while the loop's position moves right. Java checks a modification counter and usually fails fast on the next step. Python also does this for dictionaries (RuntimeError: dictionary changed size during iteration). The rule behind all four rows: don't change a collection while you are walking it, unless the collection gives you the way to do it (removeIf, the iterator's own remove, a filter that builds a new list).
For a collection that other threads change, the same idea becomes a choice between a snapshot (copy first, walk the copy, accept that it is a little stale) and holding a lock for the whole walk (fresh, but everyone else waits). The file system lesson combines the two for its find follow-up: hold the lock for the walk, collect the results into a list, release it, then return the list, so the caller loops over a snapshot and nobody waits on the caller's loop.
A page number shifts when a new order arrives and shows order 1008 twice, while the last id seen does not move, so the next page is unchanged.
Iterator and its look-alikes#
| Pattern | Looks like Iterator because | The difference |
|---|---|---|
| Visitor (dp-24) | it goes over every element of a structure | An iterator only walks; the loop body decides what to do. A visitor puts a new operation into an object that the structure calls for each element, with a method per element type. |
| Composite (dp-13) | a tree is something you walk | An iterator is how you walk a composite without exposing its children: the file system lesson's find follow-up is a depth-first iterator over the tree. |
| Generator | it produces values one at a time | A generator is a way to write an iterator: the language keeps the position for you. |
| Observer (dp-17) | values arrive one by one | An iterator is pull: the consumer asks for the next value when it is ready. Observer is push: the source calls the listeners when something happens. |
| Stream or pipeline | stages are chained | A lazy pipeline is built from iterators. Streams add operators and sometimes parallelism, but each stage still pulls from the one before. |
When not to use it#
- You just loop over a list. Every language's
forloop already is the pattern. Writing aListIteratorclass for alistis ceremony. - The collection is small and you need all of it. Return a copy or a read-only view and let the caller loop.
- The caller needs random access. "Give me item 7" or "page 7" is not what an iterator offers; it only moves forward.
- The walk must be consistent while others change the data. A lazy iterator over live data can show a mix of before and after; take a snapshot, or a lock, instead.
- You expose your internal list to avoid writing an iterator. Handing out the list lets callers change it behind your back; that is the representation leak the pattern exists to avoid.
Where it shows up in the case studies#
Two rounds use it, one fully and one as a follow-up:
| Case study | The iteration | The form |
|---|---|---|
| Chess | Piece.attacks and Piece.moves, typed Iterator[Square] and Iterator[Move] |
Generators. Each piece yields the squares it attacks and the moves it can make, and the pawn uses yield from to pass a promotion's four moves along. The pieces only produce moves; the game then keeps the legal ones, by playing each and taking it back if the king is attacked. |
| File system | The patterns table lists Iterator / Visitor (follow-up) for a walk() over the tree |
A follow-up, not in the code. The code's _walk resolves one path, which isn't a traversal. The find follow-up asks for a generator that walks a subtree depth-first and yields matching paths, and says to collect the results under the lock before returning them. |
In the interview#
Say the pattern with the reason, in one breath: "The screen shouldn't know how orders are stored or paged, so I'll give the history an iterator: the loop asks for the next order, the iterator holds the position, fetches a page only when its buffer runs out, and remembers the last id it saw, not an offset, so new orders don't repeat rows." Naming the cursor is what shows you've thought about the collection changing.
Then expect the follow-ups:
- "Why not just return a list?" It reads everything up front, and it commits to one representation. An iterator reads only what is asked for and hides how the data is stored.
- "What if a new order arrives while the user scrolls?" A page number moves, so a row repeats or goes missing. Remember the last id (a cursor), and ask for "older than that".
- "Can I jump to page 7?" Not with a cursor, because a position is a place. If you need random access, say so and use an offset, and accept the repeats.
- "Iterable or iterator?" An iterable can start any number of walks; an iterator is one walk in progress and is used up at the end.
- "What if I remove items while looping?" Don't; use
removeIf, a filter that builds a new list, or the iterator's ownremove. Python and JavaScript skip elements silently, and Java usually throws. - "How do you make it lazy?" A generator, or an iterator that pulls from another iterator, so each stage reads only what the last one needs.
- "How do you test it?" Test the sequence of values against a fake store that counts its fetches: all orders in order, one fetch per page, an early stop reads fewer pages, two walks are independent.
Common mistakes#
- Exposing the internal list. Callers then depend on it, and can change it behind your back.
- A position by number in a changing collection. A new insert shifts it; use a cursor, the last id seen.
- Looping twice over an iterator. The second loop silently does nothing. Keep the iterable, and start a new walk.
- Removing from a list while looping over it. Python and JavaScript skip elements; Java usually throws, and C++ is undefined behaviour.
- Building a full list when you need three items. Pull lazily and stop.
- An aggregate that tracks its own position. Two loops over it would interfere. The walker holds the position.
- Fetching pages nobody asked for. Prefetching the next page can be a fair trade for a smooth scroll, but make it a decision; by default, fetch when the buffer runs out.
Removing from a list inside its own loop skips an element in Python and JavaScript, usually throws in Java and is undefined behaviour in C++.
Iterator
Q1/4 Where should the "where am I in the walk" state live?
Answer & explanation
Answer: B
The aggregate makes fresh walkers and each one owns its position, so two loops don't disturb each other. A position kept in the collection, or passed around as a page number, brings back the first version's problems.
Q2/4 You loop over
walk = iter(history)once to the end, then run the same loop again. What happens?Answer & explanation
Answer: C
An iterator is one walk in progress and only moves forward. The second loop finds it at the end and has nothing to do. Loop over the iterable (
history) to start a new walk each time.Q3/4 A new order arrives between page 1 and page 2, and one order is shown twice. What is the right fix?
Answer & explanation
Answer: C
A position by number shifts when something is inserted before it. The id of the last order shown does not move, so asking for "older than 1008" gives the same next page whatever has arrived since.
Q4/4 A lazy pipeline is built with a filter and a limit of 3, but nothing has been pulled yet. How many times has the store been asked?
Answer & explanation
Answer: C
A lazy pipeline does no work when it is built. The first read happens on the first pull, and the limit stops it after the third big order, so the store is asked twice in the lesson's run.
this lesson in shorts · 3
play them all →One idea from this lesson in about a minute each, made for your phone.
New lessons by email
New lessons, side quests and case files as they ship, at most once a week. No spam, unsubscribe anytime.
Discussion · …
Public: everyone reading this lesson sees comments. Be kind and keep it on the material.