How iteration works: iterables and iterators

Read the marks "72 85 91 64" through map(int, …), add them up with sum(), then count them with len(list(marks)), and the count comes out as 0. Nothing was lost: a map hands out each value once, and sum() had already taken all four, so the average divides by zero one line later.

That zero comes from the two calls inside every for loop, iter() and next(), and from the difference between an iterableiterable: A value a for loop can go through one item at a time, such as a string, a list, a tuple, a dict, a set or a range. A dict gives its keys. More in “for loops with range, enumerate and zip”, which hands every loop a fresh iteratoriterator: An object that hands out items one at a time: next() returns its next item, or raises StopIteration when none are left. It keeps one position, so it is used up after one pass, and iter() returns the iterator itself., and an iterator, which keeps one position and is used up after one pass. Below you will step through real runs of both, write iterator classes of both kinds, and read data in fixed-size pieces with iter(function, sentinel).

A for loop calls iter() once, then next() until StopIteration

A for loop never counts positions. It asks the object after in for an iterator by calling iter() on it, once, then calls next() on that iterator again and again, binding each result to the loop variable, until next() raises the exception StopIterationStopIteration: The exception next() raises when an iterator has no items left. A for loop catches it and ends quietly, which is why a loop never shows it., which the loop treats as “no items left”. The iterator is the object that remembers the position and produces one item per next() call:

The program below runs both versions over the same three marks: first a for statement, then the same loop spelled out by hand with the three steps that the statement performs for you. Step through it and watch the flag under marks, the position the next item comes from:

marks = [72, 85, 91]

for m in marks:
    print("for:", m)

it = iter(marks)
while True:
    try:
        item = next(it)
    except StopIteration:
        break
    print("by hand:", item)

print(type(it).__name__, iter(it) is it)

for: 72
for: 85
for: 91
by hand: 72
by hand: 85
by hand: 91
list_iterator True

The while loop is what Python does underneath. iter(marks) runs once and returns a list_iterator, a separate object that keeps the position. Each next(it) returns the following item, and after the last one next() raises StopIteration. A for statement catches that exception itself, which is why you never see it. The last line shows the rule that makes iterators special: calling iter() on an iterator returns the very same object.

A list hands out new iterators; an iterator keeps one position

Anything that can hand out an iterator is an iterable: lists, strings, dictionaries, ranges and files are all iterables. An iterable has an __iter__() method that returns an iterator. An iterator has a __next__() method that returns the next item or raises StopIteration, plus an __iter__() method that returns the iterator itself, so that an iterator can be used wherever an iterable is expected. Step through two iterators over one list, and a second name for one of them:

marks = [72, 85, 91]
first = iter(marks)
second = iter(marks)
print(next(first), next(first))
print(next(second))
same = iter(first)
print(same is first, next(same))
print(next(first, "empty"))

72 85
72
True 91
empty

Every container makes a new iterator each time you ask, so two loops over a list never disturb each other: the flags of first and second moved on their own. An iterator has only one position, so every loop over it, and every name for it, continues where the previous one stopped.

The program below loops twice over eleven common objects and reports what the second loop saw:

import io

things = {
    "list": [1, 2],
    "tuple": (1, 2),
    "str": "ab",
    "dict": {"a": 1, "b": 2},
    "range": range(2),
    "map": map(str, [1, 2]),
    "filter": filter(None, [1, 0, 2]),
    "zip": zip("ab", "cd"),
    "enumerate": enumerate("ab"),
    "reversed": reversed([1, 2]),
    "file": io.StringIO("line 1\nline 2\n"),
}
for name, obj in things.items():
    first = list(obj)
    second = list(obj)
    kind = "iterator" if iter(obj) is obj else "iterable"
    print(f"{name:10} {kind:9} second loop: {len(second)} of {len(first)} items")

list       iterable  second loop: 2 of 2 items
tuple      iterable  second loop: 2 of 2 items
str        iterable  second loop: 2 of 2 items
dict       iterable  second loop: 2 of 2 items
range      iterable  second loop: 2 of 2 items
map        iterator  second loop: 0 of 2 items
filter     iterator  second loop: 0 of 2 items
zip        iterator  second loop: 0 of 2 items
enumerate  iterator  second loop: 0 of 2 items
reversed   iterator  second loop: 0 of 2 items
file       iterator  second loop: 0 of 2 items

The pattern is exact: every object that is its own iterator came back empty the second time. The documentation of iterator types adds a rule for the end of an iterator. Once __next__() has raised StopIteration, it must keep raising it on every later call; an iterator that starts producing items again is called broken.

Every read moves an iterator forward, so a second loop sees what is left

The difference matters because many everyday objects, map(), zip(), filter(), enumerate() and open files among them, are iterators themselves, and anything that reads an iterator moves it on, not only a for loop. To watch it happen, wrap a sequence in a class that counts the calls to next():

class Counted:
    """Wraps an iterable and counts how often next() is called on it."""

    def __init__(self, items):
        self._it = iter(items)
        self.calls = 0

    def __iter__(self):
        return self

    def __next__(self):
        self.calls += 1
        return next(self._it)   # raises StopIteration at the end


c = Counted("abcde")
for ch in c:
    pass
print("a for loop over 5 items:", c.calls, "calls to next()")

c = Counted(range(1_000_000))
print("999_999 in c:", 999_999 in c, "after", c.calls, "calls")

c = Counted(range(1_000_000))
print("3 in c:", 3 in c, "after", c.calls, "calls")
print("list(c) then holds", len(list(c)), "items")

a for loop over 5 items: 6 calls to next()
999_999 in c: True after 1000000 calls
3 in c: True after 4 calls
list(c) then holds 999996 items

• A loop over 5 items calls next() 6 times: one call for each item, and one more that raises StopIteration.
• 999_999 in c had to pull a million items before it found the last one, because in on an iterator has nothing better to do than call next() and compare.
• 3 in c stopped after 4 calls, and those 4 items were gone: the list() that followed collected only the 999,996 items that were left. A membership test on an iterator moves it forward.

The bug this causes is rarely a crash at the point of the mistake. Here sum() reads every number from a map object, and the line that counts them gets an iterator that is already exhausted:

line = "72 85 91 64"

marks = map(int, line.split())
total = sum(marks)
count = len(list(marks))       # the map was used up by sum()
print("total:", total, "count:", count)
try:
    print("average:", total / count)
except ZeroDivisionError as e:
    print("ZeroDivisionError:", e)

marks = list(map(int, line.split()))   # a list can be read again
print("average:", sum(marks) / len(marks))

total: 312 count: 0
ZeroDivisionError: division by zero
average: 78.0

count is 0 because list(marks) started where sum() stopped, at the end. Step through the two reads and watch the map’s position:

The error appears one line later, as a division by zero, far from its cause. The fix is to decide how many times the data will be read. If more than once, store it in a list first. If the data is too big for a list, compute everything in one pass, keeping a running total and a running count in the same loop.

An iterator class keeps its position in its attributes

Any class with those two methods works with for, list(), sum(), in and every other tool that iterates. Countdown below counts down from a start to 1: __next__() returns the current number and moves on, and raises StopIteration once it reaches 0. Its __repr__() lets the figure show the attribute that holds the position, so step through and watch c:

class Countdown:
    """An iterator: counts down from start to 1, once."""

    def __init__(self, start):
        self.current = start

    def __iter__(self):
        return self

    def __next__(self):
        if self.current <= 0:
            raise StopIteration
        value = self.current
        self.current -= 1
        return value

    def __repr__(self):
        return f"Countdown(current={self.current})"


c = Countdown(3)
for n in c:
    print(n)
print(list(c))
print(next(c, "done"))

3
2
1
[]
done

The position is the attribute current, which __next__() lowers on every pass. Because the class returns self from __iter__(), a Countdown object behaves like map: once the loop has used it up, list(c) is empty. The last line shows next() with a second argument, a default that it returns instead of raising StopIteration. Press Edit, change the start to 5 and run it again: the loop prints five numbers, and the list after it is still empty.

An iterable class gives every loop its own iterator

A collection that people loop over more than once should not be its own iterator. Make __iter__() return a new iterator object instead, so that every loop gets its own position, nested loops included. reusable.py runs the same nested loops over a one-shot iterator and over such an iterable. Its OneShot is the iterator class of the previous section under a new name, and its Countdown is a different class, the iterable built on it:

class OneShot:
    """An iterator: every loop shares the same position."""

    def __init__(self, start):
        self.current = start

    def __iter__(self):
        return self

    def __next__(self):
        if self.current <= 0:
            raise StopIteration
        self.current -= 1
        return self.current + 1


class Countdown:
    """An iterable: every loop gets a new iterator of its own."""

    def __init__(self, start):
        self.start = start

    def __iter__(self):
        return OneShot(self.start)


for make in (OneShot, Countdown):
    launch = make(3)
    pairs = [(a, b) for a in launch for b in launch if a > b]
    print(f"{make.__name__:9}", pairs)

OneShot   [(3, 2), (3, 1)]
Countdown [(3, 2), (3, 1), (2, 1)]

With OneShot, the outer loop took 3, and the inner loop then took 2 and 1 from the same object, leaving nothing for the outer loop: only two pairs. Countdown stores just the starting number and creates a fresh OneShot each time iter() is called, so the inner loop starts again at 3 for every outer item and the result has all three pairs. Step through both runs:

Lists, dictionaries and ranges are built exactly this way. The next lesson replaces such iterator classes with a single function that uses yield, which saves writing the class at all.

range computes its numbers, so two billion take no more memory than three

range() stores only its start, stop and step, and computes numbers when they are needed. Its length, its items by position and membership tests come from arithmetic, so a range of two billion numbers costs no more memory than range(3):

import sys

r = range(0, 10**10, 5)        # two billion numbers: every fifth one below ten billion

print(len(r), r[3], r[-1])     # length and indexing, computed
print(9_999_999_995 in r, 7 in r)      # membership by arithmetic, not by looping
print(sys.getsizeof(r) == sys.getsizeof(range(3)))   # the same size in memory
print(list(range(3)), list(range(3)))  # loops over it twice

it = iter(range(3))            # an iterator over a range is one-shot
print(type(it).__name__, list(it), list(it))

2000000000 15 9999999995
True False
True
[0, 1, 2] [0, 1, 2]
range_iterator [0, 1, 2] []

sys.getsizeof() reports the same size for both ranges, the third line’s True. The membership test for 9,999,999,995 answered at once: for integers, CPython computes it from the start, stop and step instead of looping. And because a range is an iterable, not an iterator, it can be looped over any number of times. Only iter(range(3)), a range_iterator, behaves like the one-shot objects above.

iter(function, sentinel) calls a function until it returns the sentinel

iter() has a second form. Given a function and a sentinelsentinel: A value that marks the end of the data instead of a count, such as the b"" that read() returns at the end of a file. iter(func, sentinel) calls func() until it returns that value. value, iter(function, sentinel) returns an iterator that calls the function with no arguments on every next() and stops as soon as it returns the sentinel. Reading a binary file in fixed-size pieces is its classic use, because read() returns b"" at the end:

import io
import random
from functools import partial

data = io.BytesIO(b"0123456789abcdef!")
read4 = partial(data.read, 4)        # read4() returns the next 4 bytes
for chunk in iter(read4, b""):       # call read4() until it returns b""
    print(chunk)

rng = random.Random(7)
roll = partial(rng.randint, 1, 6)
print("rolls before the first 6:", list(iter(roll, 6)))

b'0123'
b'4567'
b'89ab'
b'cdef'
b'!'
rolls before the first 6: [3, 2, 4]

functools.partial(data.read, 4) makes a function that needs no arguments, which is what this form of iter() requires. Step through the first loop and watch each result meet the sentinel test:

The loop received 4 bytes at a time and the 1 byte left at the end, then stopped at b"" without passing it on. The dice show that the sentinel can be any value: the rolls before the first 6 were 3, 2 and 4, and the 6 itself was not returned. The random generator is seeded, so the run gives the same rolls every time.

Practise: a Fibonacci iterator and overlapping pairs

Write two iterators with sample tests that run in your browser and a first hint: a Fibonacci class that is used up after one pass, and a pairs() function that stays lazy on input that can be read only once.

class Fibonacci:
    """The Fibonacci numbers 0, 1, 1, 2, 3, ... up to limit (None: no end)."""

    def __init__(self, limit=None):
        self.limit = limit

    def __iter__(self):
        return self

    def __next__(self):
        raise StopIteration


def pairs(iterable):
    """An iterator of the overlapping pairs of neighbouring items."""
    items = list(iterable)
    return iter([(items[i], items[i + 1]) for i in range(len(items) - 1)])

from itertools import islice

from sequences import Fibonacci, pairs


class Reader:
    """An iterator over items that counts how many were read."""

    def __init__(self, items):
        self._it = iter(items)
        self.read = 0

    def __iter__(self):
        return self

    def __next__(self):
        value = next(self._it)
        self.read += 1
        return value


def test_fibonacci_with_limit():
    """stops after the last number that is not greater than the limit"""
    assert list(Fibonacci(10)) == [0, 1, 1, 2, 3, 5, 8]
    assert list(Fibonacci(13)) == [0, 1, 1, 2, 3, 5, 8, 13]
    assert list(Fibonacci(0)) == [0]


def test_fibonacci_without_limit():
    """keeps going without a limit"""
    assert list(islice(Fibonacci(), 12)) == [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]


def test_fibonacci_is_one_shot():
    """is its own iterator and stays used up"""
    f = Fibonacci(5)
    assert iter(f) is f
    assert list(f) == [0, 1, 1, 2, 3, 5]
    assert list(f) == []
    assert next(f, "done") == "done"


def test_pairs():
    """pairs neighbouring items, and gives nothing for fewer than two items"""
    assert list(pairs("abcd")) == [("a", "b"), ("b", "c"), ("c", "d")]
    assert list(pairs([1, 2])) == [(1, 2)]
    assert list(pairs([1])) == []
    assert list(pairs([])) == []


def test_pairs_is_lazy():
    """reads only the items it needs, from an iterator that can be read once"""
    source = Reader(range(1_000_000))
    p = pairs(source)
    assert next(p) == (0, 1)
    assert source.read == 2
    assert next(p) == (1, 2)
    assert source.read == 3
    assert iter(p) is p

Last, a session of questions on the seven ideas above. It opens with the idea you have answered least well so far and explains every answer, right or wrong, as soon as you give it:

Interview questions

Fresher to 2–5 years · What is the difference between an iterable and an iterator?

An iterable is any object that can produce an iterator: calling iter() on it works, because it defines __iter__() (or, in older code, __getitem__() with indexes from 0). Lists, strings, dictionaries, sets, ranges and files are iterables. An iterator is the object that does the iterating: it has __next__(), which returns the next item or raises StopIteration when there are no more, and an __iter__() that returns itself. The practical difference is reuse. A container gives every loop a new iterator, so it can be looped over again and again, while an iterator has a single position and is used up after one pass. That is why map(), zip(), filter() and open files give an empty second loop. Every iterator is an iterable, but not every iterable is an iterator.

Key takeaways

• for x in obj calls iter(obj) once, then next() until StopIteration, which the loop handles silently.
• An iterable hands out a new iterator to every loop; an iterator returns itself from iter(), keeps one position and is used up after one pass, as map, filter, zip, enumerate, reversed and files are.
• Every read moves an iterator forward, in and sum() included, so a second loop over the same iterator sees only what is left: keep a list when the data is read more than once.
• Write an iterator class with __iter__() returning self and __next__() raising StopIteration; for data that is looped over more than once, return a new iterator from __iter__() instead.
• range is a lazy sequence that computes its numbers and can be looped over many times; iter(function, sentinel) calls a function until it returns the sentinel.