Iterator Protocol

The previous lesson measured that a copy stays one layer deep: a list taken by slice was a new container, but every item inside it was the same object as before. Still, building that container was not free. The new list did not duplicate items, but it had to write each one’s reference into itself — the copy produced no items, it touched all of them.

This lesson’s question goes one step further. To see a collection’s items start to finish, does that container have to be rebuilt? Is it possible to pass over items without ever touching them, without building any new container? Python’s answer is the iterator contract, and this lesson measures that contract on the course’s axis: how many objects does a pass materialize, how many does it retain, how many does it share?

The Contract

The contract consists of two built-ins and two special methods. iter(n) requests an iterator from an object and calls the object’s __iter__ method. next(y) requests the next item from the iterator and calls __next__. When there is no item left to give, __next__ does not return a value, it throws StopIteration.

The Python Fundamentals course’s loops lesson measured this protocol from the consuming side: which special method the for notation calls and how many times, and that what ends the loop is not a return value but an exception, were established there; that measurement is not repeated here. This lesson’s side is the other one — the side that writes the contract. Two objects following the same protocol look identical from outside, but one materializes and retains its items ahead of time, the other materializes on demand and retains nothing at all. Syntax does not say this difference; numbers do.

Iterable and Iterator

The contract defines two roles, and confusing them is the most common mistake. An iterable object defines __iter__; it is not walked itself, it gives what will walk it. An iterator defines __next__ and does the actual walking. A list is an iterable but not an iterator: next(a_list) does not work, iter(a_list) has to be called first.

It is not forbidden for an object to define both. Then __iter__’s body returns itself, and the distinction disappears; the result of that is measured below. In the case where the distinction stays intact, __iter__ produces a fresh iterator every time it is called.

The definition that follows sits at the course’s axis: what an iterator carries is not items, it is where it left off. A position is not an item, and it does not grow with item count.

The measurement’s assumptions:

• IF1 — The oracle is the rig itself: Item counts every production of itself, and sharing is shown with is; the measure for “how many objects were materialized” is this counter.
• IF2 — The shared reference’s Item class is used as is, with its counting arrangement.
• IF3 — The source has three items. The count is kept small, because what is measured is not size, it is whether the pass builds a container.
• IF4 — “Held in container” is the number of item references an object coming out of the pass writes into itself: a list’s length, zero for an iterator. The measure is the reference count, not bytes measured.
• IF5 — “Shared” is how many of the items coming out of the walk are the same, by is, as the object in the source.
• IF6 — Counting materializes items on demand and stores none of them; Container materializes items at construction and holds them in a list. The two classes differ only at this point, and both sign the same contract.
• IF7 — The single-pass measurement is done by calling list() twice on the same object; the item count the second call returns is the measure.
• IF8 — In the sentinel measurement, next is called with a second argument and tried twice on an exhausted iterator; the goal is showing that exhaustion is permanent.
• IF9 — In the two-pass measurement, all three of the three approaches request the same five-item source; the only thing that changes is where the items come from. The materialized count is the sum of the two passes; the retained count is the number of references staying alive between passes.

Measurement

"""Iterator contract: how many objects does a pass materialize, how many references does it hold."""

COUNTER = {"produced": 0}


class Item:
    """An item that counts every production of itself."""

    def __init__(self, value):
        COUNTER["produced"] += 1
        self.value = value

    def __repr__(self):
        return f"Item({self.value})"


def reset():
    COUNTER["produced"] = 0


def produced():
    return COUNTER["produced"]


def retained(obj):
    """The number of Item objects an object keeps alive: on itself or in a list attribute."""
    if isinstance(obj, list):
        return sum(isinstance(o, Item) for o in obj)
    count = 0
    for d in getattr(obj, "__dict__", {}).values():
        if isinstance(d, list):
            count += sum(isinstance(o, Item) for o in d)
    return count


SOURCE = [Item(i) for i in range(3)]
FORMS = (("iter(source)", lambda: iter(SOURCE)),
            ("source[:]", lambda: SOURCE[:]),
            ("list(source)", lambda: list(SOURCE)),
            ("reversed(source)", lambda: reversed(SOURCE)),
            ("copy via comprehension", lambda: [Item(o.value) for o in SOURCE]))

print(f"{'pass form':<22s} {'new container':>13s} {'materialized':>12s}"
      f" {'held in container':>18s} {'shared':>7s}")
for name, build in FORMS:
    reset()
    obj = build()
    container = "list" if isinstance(obj, list) else "no"
    held = retained(obj)
    shared = sum(1 for o in list(obj) if any(o is k for k in SOURCE))
    print(f"  {name:<20s} {container:>13s} {produced():12d} {held:18d} {shared:7d}")

y = iter(SOURCE)
print()
print(f"iter(source) is source -> {y is SOURCE}, iter(y) is y -> {iter(y) is y}")
print(f"next(y) is source[0] -> {next(y) is SOURCE[0]}")
a, b = iter(SOURCE), iter(SOURCE)
print(f"two separate iterators: {len(list(a))} and {len(list(b))} items")
t = iter(SOURCE)
print(f"same iterator twice: {len(list(t))} and {len(list(t))} items")


class Counting:
    """An iterator that materializes items on demand."""

    def __init__(self, n):
        self.n, self.i = n, 0

    def __iter__(self):
        return self

    def __next__(self):
        if self.i >= self.n:
            raise StopIteration
        self.i += 1
        return Item(self.i - 1)


class Container:
    """An iterable that materializes items up front and holds them."""

    def __init__(self, n):
        self.items = [Item(i) for i in range(n)]

    def __iter__(self):
        return iter(self.items)


print()
print(f"{'object':<12s} {'at setup':>9s} {'held at setup':>15s}"
      f" {'after two items':>16s} {'__iter__ gives':>15s}")
for name, build in (("Counting(5)", lambda: Counting(5)), ("Container(5)", lambda: Container(5))):
    reset()
    n = build()
    setup, setup_held = produced(), retained(n)
    it = iter(n)
    next(it), next(it)
    print(f"  {name:<12s} {setup:9d} {setup_held:15d} {produced():16d}"
          f" {('itself' if iter(n) is n else 'another object'):>15s}")

counting = Counting(3)
print()
print(f"Counting(3) first pass {len(list(counting))} items, second pass {len(list(counting))} items")
print(f"after exhaustion: {next(counting, 'sentinel')!r} and {next(counting, 'sentinel')!r}")
container = Container(3)
print(f"Container(3) first pass {len(list(container))} items, second pass {len(list(container))} items")

remaining = [3, 2, 1, 0, 9]
print(f"iter(callable, sentinel) -> {list(iter(lambda: remaining.pop(0), 0))}")


def direct():
    s = Counting(5)
    return len(list(s)), len(list(s)), 0


def collect_to_list():
    s = list(Counting(5))
    return len(list(s)), len(list(s)), len(s)


def rebuild():
    return len(list(Counting(5))), len(list(Counting(5))), 0


print()
print(f"{'two-pass approach':<30s} {'materialized':>12s} {'retained':>9s}"
      f" {'first':>8s} {'second':>7s}")
for name, f in (("walking the same iterator", direct),
              ("collecting to a list first", collect_to_list),
              ("rebuilding on every pass", rebuild)):
    reset()
    first, second, held = f()
    print(f"  {name:<28s} {produced():12d} {held:9d} {first:8d} {second:7d}")

pass form              new container materialized  held in container  shared
  iter(source)                    no            0                  0       3
  source[:]                     list            0                  3       3
  list(source)                  list            0                  3       3
  reversed(source)                no            0                  0       3
  copy via comprehension          list            3                  3       0

iter(source) is source -> False, iter(y) is y -> True
next(y) is source[0] -> True
two separate iterators: 3 and 3 items
same iterator twice: 3 and 0 items

object        at setup   held at setup  after two items  __iter__ gives
  Counting(5)          0               0                2          itself
  Container(5)         5               5                5  another object

Counting(3) first pass 3 items, second pass 0 items
after exhaustion: 'sentinel' and 'sentinel'
Container(3) first pass 3 items, second pass 3 items
iter(callable, sentinel) -> [3, 2, 1]

two-pass approach              materialized  retained    first  second
  walking the same iterator               5         0        5       0
  collecting to a list first              5         5        5       5
  rebuilding on every pass               10         0        5       5

A Pass That Builds No Container

The top table lines up five pass forms side by side and splits them into three classes.

Those that rebuild the container. source[:] and list(source) produce a new list and write 3 references into it. The number of Item objects materialized is 0 — no item is duplicated, and shared is 3. This is the shallow copy the previous lesson measured: the outer container is new, what is inside is old.

Those that reproduce items. The comprehension in the last row materializes 3 new Item objects and shared drops to 0. Both the container and what is inside are new.

Those that do neither. In the iter(source) and reversed(source) rows there is no new container, held in container is 0, materialized is 0, and shared is still 3. The pass delivers all three of the three items, materializes none of them, and writes none of their references into itself. The opening question is answered here: passing over items without touching them is possible.

An objection is fair here: iter(source) also produces an object — the iterator itself. But that object is not a container; it holds no items, it only carries a reference to the source and a position. The table’s “materialized” column counts Item objects, and “held in container” counts item references; the iterator gives zero on both, because it is neither.

The difference looks like a matter of one reference per three items. If the source had a thousand items, list(source) would write a thousand references, iter(source) would still write zero. The container’s cost grows with item count, the iterator’s does not: the retained count is a function of item count, not of position.

What an Iterator Carries

The three lines in the middle block separate the roles. iter(source) is source is false: a list is an iterable, but it does not do the walking itself; iter returns a separate object from it. iter(y) is y is true: requesting an iterator from an iterator gives back itself. This is why a for loop can accept both collections and iterators with the same notation — iter is applied to both, and on the second this call changes nothing.

next(y) is source[0] is true: the item delivered is the source’s own item, not a copy of it. An iterator is not a producer, it is a deliverer.

The next two lines show where the position is held. Two separate iterators taken from the same list are independent of each other: each gives 3 items. The same iterator walked twice gives 3 and 0. Because the position lives in the iterator, not the list, every new iterator requested from the list starts from zero; an existing iterator continues from where it left off and eventually exhausts.

Two Classes Writing the Contract

The second table compares two classes that sign the same contract. Counting materializes 0 objects at setup and retains 0; once two items are requested, the produced count rises to 2. Container materializes 5 at setup, retains 5, and after two items are requested the number is still 5 — production had already finished.

The two objects are indistinguishable from outside. Both go into a for loop, both give the same five values, iter and next work on both. The distinction is only in the numbers: one does the work at setup, the other on demand.

The last column gives the second distinction. Counting.__iter__ returns itself; Container.__iter__ takes another object from its inner list on every call. This shows up in the two lines below: Counting(3) gives 3 items on the first pass, 0 on the second — it exhausts. Container(3) gives 3 on both passes, because every pass starts with a fresh iterator.

Single-pass behavior is not a flaw, it is the contract’s direct consequence. The contract says “give the next item on request”; it does not say “give the same items a second time too.” For an iterator to give a second pass, it would have to store every item it saw — that is, do exactly the thing it avoids. An object that retains nothing cannot rewind.

Exhaustion is permanent. When next is called two more times on an emptied Counting, both give the sentinel value; the object does not renew itself.

The Cost of Two Passes

The last table measures the practical counterpart of this result in three ways. On hand is a single-pass source, and items are needed twice.

Walking the same iterator twice does not work: 5 and 0. Materialized is 5, retained is 0 — the cheapest row, but it does not give a second pass.

Collecting to a list and walking it twice gives the second pass: 5 and 5. Materialized is still 5, because the items were produced once and stored. The cost shows in the retained column: it rose from 0 to 5. Had item count been a thousand, this column would be a thousand.

Rebuilding the source on every pass also gives the second pass, and retained stays at 0. Its cost shows in the other column: materialized rose from 5 to 10, because five items were produced twice. This route only works if the source can be rebuilt; a network stream or user input may not give the same items a second time.

None of the three rows beats the sum of the others, and there is a real choice here: there is no two-pass without retaining. You either store the items, reproduce them, or settle for a single pass. An iterator does not remove this choice; it just makes the third option free.

The Contract’s Two Escape Hatches

The last two lines show two built-in flexibilities of the contract.

Called with a second argument, next(y, sentinel) does not throw StopIteration, it returns the given value. The exception turns into a value; it is the way to ask “is it done?” without setting up a try block. The value chosen as the sentinel has to be one that cannot occur in the stream, or the ending gets mixed up with an item — this is the same reason StopIteration is not a return value.

Called with two arguments, iter does something entirely different: it produces an iterator whose source is not a collection but a callable. In the example, every next takes one item from the front of a list, and the pass ends when the sentinel 0 shows up. The result is [3, 2, 1] — the sentinel itself is not delivered. This way, a file, a queue, or any source giving one next item per call can be fed into a for loop without ever being turned into a collection.

Summary

• The iterator contract is two built-ins and two special methods: iter calls __iter__, next calls __next__; StopIteration is thrown when no item is left.
• Passing, copying, and reproducing are three separate jobs: iter builds no container and writes 0 references, list(source) writes 3, and a comprehension additionally materializes 3 new objects. Sharing is measured in all three, and is 0 only in the last.
• An iterable defines __iter__, an iterator defines __next__; iter(a_list) gives a separate object from the list, iter(an_iterator) gives the object itself. What an iterator carries is not items, it is the position left off at.
• Two classes signing the same contract are indistinguishable from outside but differ in their numbers: 0 versus 5 production at setup, 0 versus 5 retention.
• Single-pass behavior is a consequence of the contract: an object whose __iter__ returns itself gives 3 then 0 items, one returning a fresh iterator gives 3 on both passes. An object retaining nothing cannot rewind, and exhaustion is permanent.

Next Step

The Counting class needed three methods, a bound, and a position field across five lines — all for one thing: remembering where it left off. This is work repeated in every hand-written iterator, and when the position is not a single number (a nested walk, a branched search), the class grows fast. The next lesson measures the form where the language takes this job off your hands: a function whose body pauses and resumes from where it left off. The number to be measured is this — calling such a function, how many of the thousand productions in its body does it do at call time?