Chapter 3

Containers

In C++ and Java a container is a library class you name and construct. Python builds its containers into the grammar: [1, 2], {"a": 1}, and {1, 2} are literals, in and len() work on all of them, and slicing works on the sequences, without importing anything. Lists, tuples, dictionaries, and sets are fundamental data types.

Lists

The for statement iterates through a list directly rather than counting through a sequence of numbers:

# list.py

odds = [1, 3, 5, 7, 9, 11]
print(odds)
#: [1, 3, 5, 7, 9, 11]
odds.append(13)
for x in odds:
    print(x)
#: 1
#: 3
#: 5
#: 7
#: 9
#: 11
#: 13

The first line creates a list. append() adds new elements to odds. The list automatically resizes itself. The for statement iterates through odds, so x takes on each value in the list.

A list holds objects, of any kind, in an ordered, mutable sequence. Indexing starts at zero, and negative indices count from the end. A slice [start:stop:step] copies a subrange, with stop excluded:

# slicing.py

xs = [10, 20, 30, 40, 50]
print(xs[0], xs[-1])  # First and last
#: 10 50
print(xs[1:3])  # The stop index is excluded
#: [20, 30]
print(xs[:2])  # From the start
#: [10, 20]
print(xs[2:])  # To the end
#: [30, 40, 50]
print(xs[::2])  # Every second item
#: [10, 30, 50]
print(xs[::-1])  # Reversed
#: [50, 40, 30, 20, 10]

Slicing works on any sequence, including strings and tuples.

Lists grow, shrink, and answer questions about themselves:

# list_ops.py

xs = [10, 20, 30]
xs.append(40)  # Add one item at the end
xs.extend([50, 60])  # Add every item of an iterable
xs.insert(1, 15)  # Insert before index 1
print(xs, len(xs))
#: [10, 15, 20, 30, 40, 50, 60] 7
xs.remove(15)  # Remove the first item equal to 15
del xs[0]  # Remove by index
print(xs, 30 in xs)
#: [20, 30, 40, 50, 60] True

append() adds its argument as a single element, so xs.append([1, 2]) puts a list inside the list. extend() adds each item of its argument instead.

sorted() builds a new sorted list from any iterable. list.sort() reorders a list in place and returns None:

# sorting.py

words = ["pear", "Fig", "apple"]
print(sorted(words))  # A new list; words is untouched
#: ['Fig', 'apple', 'pear']
print(words)
#: ['pear', 'Fig', 'apple']
print(words.sort())  # Sorts in place and returns None
#: None
print(words)
#: ['Fig', 'apple', 'pear']
print(sorted(words, reverse=True))
#: ['pear', 'apple', 'Fig']

sorted(x) returns the result while x.sort() returns None, so x = x.sort() binds None and loses the list. Uppercase sorts before lowercase because Python compares strings by code point. Functions shows how a key= function changes the ordering; key=str.lower would fold the case here.

Each slot of a list holds a reference to whatever object you put there, so the same list can mix strings, numbers, None, and other containers:

# mixed_types.py

mixed = [1, "two", 3.0, True, None, [5, 6]]
for item in mixed:
    print(item, type(item).__name__)
#: 1 int
#: two str
#: 3.0 float
#: True bool
#: None NoneType
#: [5, 6] list

Mixing types is convenient but easy to overuse. A list of mixed types usually means each element needs different handling. A tuple, a data class, or distinct lists, each holding a single type, express those differing roles better.

Two list operations produce surprises. * repeats a reference rather than copying what it points at, so a grid built that way has one row under three names:

# list_traps.py

grid = [[0]] * 3  # Three names for one inner list
grid[0][0] = 1
print(grid)
#: [[1], [1], [1]]
grid = [[0] for _ in range(3)]  # Three separate lists
grid[0][0] = 1
print(grid)
#: [[1], [0], [0]]

The grid is Variables and References again: * binds the same object into every slot, and assignment never copies.

Removing items from a list while iterating over it is the same kind of surprise:

# remove_while_iterating.py

xs = [1, 2, 3, 4]
for x in xs:
    xs.remove(x)
print(xs)
#: [2, 4]

Each remove() slides the following elements one place to the left, and the loop then advances its index, so it steps over the element that moved into the vacated slot. Skipping every other element leaves half of xs, and no exception reports the skip. Build a new list instead, or iterate over a copy with for x in xs[:].

The usual way to build a list from another one is a comprehension: a single expression that produces the new list, in place of a loop with append(). Control Flow introduces it, and Comprehensions explores every form in depth.

Tuples and Unpacking

A tuple is an immutable sequence. The comma makes the tuple, not the parentheses. Tuples are the natural way to return several values from a function and to group values for unpacking:

# tuples.py

point = (3, 4)
point = 3, 4  # Also a tuple; the comma matters
empty = ()  # Empty tuple
x, y = point  # Unpacking
print(x, y)
#: 3 4
# A one-element tuple needs the trailing comma
single = (42,)
print(len(single))
#: 1
print(tuple([1, 2, 3]))  # Converts a list to a tuple
#: (1, 2, 3)
print(tuple("abc"))
#: ('a', 'b', 'c')

def min_max(values):
    return min(values), max(values)  # Returns a tuple

low, high = min_max([5, 2, 9, 1])
print(low, high)
#: 1 9

The empty tuple () is the exception to the comma rule, because it has nothing to separate.

One name per element is the simplest unpacking, and two extensions relax it. A starred name absorbs whatever remains, and a target can nest to match the shape of the value:

# unpacking_assignment.py

first, *rest = [10, 20, 30, 40]
print(first, rest)  # A starred name always collects a list
#: 10 [20, 30, 40]
head, *middle, tail = "abcde"  # Any iterable unpacks
print(head, middle, tail)
#: a ['b', 'c', 'd'] e
(name, age), city = ("Alice", 30), "Rome"  # Nested targets
print(name, age, city)
#: Alice 30 Rome
values = [1, 2, 3]
try:
    x, y = values  # Without a star the counts must match
except ValueError as e:
    print(e)
#: too many values to unpack (expected 2, got 3)

At most one target can carry the star, and the starred target always receives a list, even when the source is a tuple or a string. Without a star the number of names must equal the number of elements, or the assignment raises a ValueError. By convention, a value you never read gets the name _, so *_ discards a run of elements. Pattern Matching matches case patterns against the same shapes.

Tuples are often heterogeneous, with each position a different type:

# heterogeneous.py

person = ("Alice", 30, 1.65)  # Name, age, height
name, age, height = person
print(name, age, height)
#: Alice 30 1.65
print(person[0], type(person[0]).__name__)
#: Alice str
print(person[1], type(person[1]).__name__)
#: 30 int
print(person[2], type(person[2]).__name__)
#: 1.65 float

A tuple used this way is a fixed-length immutable record, where each position has a distinct meaning. A tuple holding many values of one type is instead an immutable list.

Dictionaries

A dictionary (dict) maps keys to values, with fast lookup. Lookup computes a hash from each key: an integer derived from the key’s contents. Python reduces that integer to the slot where the entry lives. So keys must be hashable. Strings, numbers, and tuples of hashable values are hashable; the mutable built-in containers (list, dict, set) are not, so they cannot be keys.

# dictionaries.py

ages = {"Alice": 30, "Bob": 25}
print(ages)
#: {'Alice': 30, 'Bob': 25}
print(ages["Alice"])
#: 30
ages["Carol"] = 41  # Add or update
print("Bob" in ages)  # Membership tests the keys
#: True
# A default when the key is missing
print(ages.get("Dan", 0))
#: 0
print(list(ages))  # Iterating a dict yields its keys
#: ['Alice', 'Bob', 'Carol']
print(list(ages.values()))
#: [30, 25, 41]
for name, age in ages.items():
    print(name, age)
#: Alice 30
#: Bob 25
#: Carol 41

Use dict.get() instead of [] to avoid a KeyError when a key might be absent.

A dict has three views: keys(), values(), and items(). Iterating the dict iterates keys(), so for name in ages walks the names. items() alone yields (key, value) pairs, and leaving it off is a common slip: for name, age in ages iterates the keys and tries to unpack each one. Unpacking "Alice" into two names raises a ValueError, since the string has more than two characters. A two-character key such as "Bo" would unpack into its letters and the loop would finish with no error.

keys() is also set-like, and so is items() when every value is hashable: each supports &, |, -, and ^ against another dict’s view or against any set.

# dict_views.py

ages = {"Alice": 30, "Bob": 25, "Carol": 41}
other = {"Bob": 0, "Dan": 0}
print(ages.keys() & other.keys())  # Set algebra on a view
#: {'Bob'}

The next section, on sets, names every one of these operators.

A dict iterates in insertion order, and the language guarantees that order.

Entries come out as easily as they go in, and two dictionaries combine:

# dict_ops.py

a = {"x": 1, "y": 2}
b = {"y": 20, "z": 3}
print(a | b)  # Merge; the right side wins a collision
#: {'x': 1, 'y': 20, 'z': 3}
print(a.pop("x"), a)  # Remove and return
#: 1 {'y': 2}
del b["z"]
print(b)
#: {'y': 20}
print(dict(zip("abc", [1, 2, 3])))  # Build from pairs
#: {'a': 1, 'b': 2, 'c': 3}

| builds a merged dict and |= updates in place, the same job update() does. The next section uses | for set union, where the order of the operands makes no difference. For dictionaries the order matters: when both dictionaries hold the same key, the right operand’s value wins, so "y" comes out as 20. The last line feeds dict() an iterable of (key, value) pairs, and any iterable that yields such pairs will do. zip() pairs up two sequences element by element. Control Flow covers it with the other loop tools.

Changing a dict’s size while iterating it raises a RuntimeError instead of quietly skipping elements, as remove_while_iterating.py’s list does:

# dict_iteration_trap.py

d = {"a": 1, "b": 2, "c": 3}
try:
    for k in d:
        del d[k]
except RuntimeError as e:
    print(e)
#: dictionary changed size during iteration

A set raises the same exception, with the message Set changed size during iteration. Only the list hides the mistake; the dict and the set both shout it.

Sets

A set is an unordered collection of unique items. Like the dict, it has fast membership tests. Sets also provide the expected set algebra:

# sets.py

a = {1, 2, 3, 3}  # Duplicates collapse
print(a)
#: {1, 2, 3}
print(type({}).__name__, type(set()).__name__)
#: dict set
b = {3, 4, 5}
print(a & b)  # Intersection
#: {3}
print(a | b)  # Union
#: {1, 2, 3, 4, 5}
print(a - b)  # Difference
#: {1, 2}
print(a ^ b)  # Symmetric difference
#: {1, 2, 4, 5}
c = {1, 2}
print(c <= a)  # Subset
#: True
print(a >= c)  # Superset
#: True
print(2 in a)
#: True

dict claimed the {} literal first, so an empty set is set(). The order these sets print comes from CPython’s hashing, not from any guarantee, so do not write code, or a test, that depends on it.

Every set-algebra operator in sets.py has a named method. The methods are more flexible: they accept any iterable where the operators need a set on both sides, and union(), intersection(), and difference() take several arguments at once. isdisjoint() adds one more test, with no operator form:

# set_methods.py

a = {1, 2, 3}
b = {3, 4, 5}

print(a.intersection(b))  # Same as a & b
#: {3}
print(a.union(b))  # Same as a | b
#: {1, 2, 3, 4, 5}
print(a.difference(b))  # Same as a - b
#: {1, 2}
print(a.symmetric_difference(b))  # Same as a ^ b
#: {1, 2, 4, 5}
print(a.intersection([2, 3, 9]))  # Arg can be any iterable
#: {2, 3}
print(a.union(b, [6, 7]))  # Several args
#: {1, 2, 3, 4, 5, 6, 7}
c = {1, 2}
print(c.issubset(a))  # Same as c <= a
#: True
print(a.issuperset(c))  # Same as a >= c
#: True
print(a.isdisjoint({8, 9}))  # No operator form
#: True

sets.py leaves out a few operators. < and > test proper subset and superset. They behave like <= and >= but also require the two sets to differ. The augmented assignments |=, &=, -=, and ^= modify a set in place. They match the update(), intersection_update(), difference_update(), and symmetric_difference_update() methods. Single elements move in and out with add(), remove(), and discard(). remove() raises a KeyError on a missing element. discard() stays silent.

Repeated lookups run faster against a set than against a list. A list compares the item you are looking for against every element in turn. A set computes one hash and looks in one place. timeit() runs a callable number times and returns the total elapsed seconds. The lambda: prefix wraps an expression into the callable timeit() needs (Functions covers lambda fully):

# membership_cost.py
from timeit import timeit
from benchmark import report

def scan_gap(n: int) -> float:
    items = list(range(n))
    lookup = set(items)
    missing = -1
    list_time = timeit(lambda: missing in items, number=20)
    set_time = timeit(lambda: missing in lookup, number=20)
    return list_time / set_time

small_gap = scan_gap(20_000)
large_gap = scan_gap(200_000)
report(small_n=small_gap, large_n=large_gap)
print(large_gap > small_gap)  # The gap widens
#: True

Searching the list is O(n) and searching the set is O(1), so the gap widens without limit as n grows. At ten times the size the ratio is bigger rather than the same, so large_gap comes out bigger than small_gap. The probe value is missing on purpose: searching for an absent item is the list’s worst case, since the scan compares all n elements before reporting False.

A timing depends on the machine that took it, so every measured listing in this book prints a comparison rather than a number. report() comes from a small helper the book supplies. By default the listing prints the comparison alone. Running it with --numbers (see Numbers on Your Machine) adds the two numbers it compared.

Specialized Containers

The collections module in the standard library includes container types built for specific jobs. Four of these show up consistently: Counter, defaultdict, deque, and namedtuple.

`Counter`

A Counter tallies the frequency of each item:

# counter.py
from collections import Counter

words = "a cat sat on a mat a cat".split()
counts = Counter(words)
print(counts)
#: Counter({'a': 3, 'cat': 2, 'sat': 1, 'on': 1, 'mat': 1})
print(counts["a"])
#: 3
print(counts["dog"])
#: 0
print("dog" in counts)  # Reading it added nothing
#: False
print(counts.most_common(2))
#: [('a', 3), ('cat', 2)]
print(Counter("aab") - Counter("ab"))  # Multiset diff
#: Counter({'a': 1})

A missing key counts as zero rather than raising a KeyError, and most_common() returns the highest counts first. -, &, and | work between two counters as well, the same operators the Sets section just used, now reading as multiset difference, minimum, and maximum. A fourth operator, +, sums the counts of both counters.

`defaultdict`

A defaultdict supplies a value the first time you touch a missing key, and that removes the setup-on-first-use boilerplate:

# defaultdict.py
from collections import defaultdict

pets = [("dog", "Rex"), ("cat", "Felix"), ("dog", "Fido")]
# A plain dict makes you create each list first:
plain = {}
for kind, name in pets:
    if kind not in plain:
        plain[kind] = []
    plain[kind].append(name)
print(plain["dog"])
#: ['Rex', 'Fido']
# A defaultdict creates the missing list:
by_kind = defaultdict(list)
for kind, name in pets:
    by_kind[kind].append(name)
print(by_kind["dog"])
#: ['Rex', 'Fido']
# A missing key gets a fresh empty list
print(by_kind["fish"])
#: []
print("fish" in by_kind)  # Reading it added the key
#: True

The defaultdict constructor argument is a factory, a callable that builds the default. The factory runs on the read, and its result goes into the dictionary, so touching a missing key grows it. Use in or dict.get() when you only want to look. Here, list produces a fresh empty list for each new key.

A plain dict has a second option, setdefault(). plain.setdefault(kind, []).append(name) returns the list already stored under kind; when kind is missing, it stores the new [] and returns that instead. The [] argument builds an empty list on every call, used or not. Every place that touches the dictionary must also repeat the whole expression. A defaultdict states the default once, where you create the dictionary.

`deque`

A deque (double-ended queue) adds and removes items at either end in constant time. A list is fast only at its append end:

# deque.py
from collections import deque

dq = deque([1, 2, 3])
dq.append(4)  # Add on the right
dq.appendleft(0)  # Add on the left
print(dq)
#: deque([0, 1, 2, 3, 4])
print(dq.popleft())  # Remove from the left
#: 0
print(dq.pop())  # Remove from the right
#: 4
print(dq)
#: deque([1, 2, 3])
window = deque(maxlen=3)  # A bounded sliding window
for i in range(5):
    window.append(i)
print(window)
#: deque([2, 3, 4], maxlen=3)

A list has an operation for each of those four:

# list_as_deque.py

lst = [1, 2, 3]
lst.append(4)  # Add at the end
lst.insert(0, 0)  # Add at the start
print(lst)
#: [0, 1, 2, 3, 4]
print(lst.pop(0))  # Remove from the start
#: 0
print(lst.pop())  # Remove from the end
#: 4
print(lst)
#: [1, 2, 3]

A list can stand in for a deque, but insert(0, x) and pop(0) must shift every remaining element, so both are O(n) instead of O(1). Timing the two at the left end shows the difference:

# deque_timing.py
from collections import deque
from timeit import timeit
from benchmark import report

n = 20_000

def list_left_ops():
    items = []
    for i in range(n):
        items.insert(0, i)
    while items:
        items.pop(0)

def deque_left_ops():
    items = deque()
    for i in range(n):
        items.appendleft(i)
    while items:
        items.popleft()

list_time = timeit(list_left_ops, number=1)
deque_time = timeit(deque_left_ops, number=1)
report(list_ops=list_time, deque_ops=deque_time)
print(deque_time * 20 < list_time)  # Not close
#: True

Use a deque for a single-threaded queue. Indexing its middle is O(n), though, so a deque does not replace a list you index by position. A deque(maxlen=n) also caps its length, discarding from the other end when a new item would overflow it. That is a sliding window, and a list has no equivalent. For a queue shared between threads, use queue.Queue (see Concurrency), and for a priority queue, heapq.

`namedtuple`

A namedtuple builds a tuple subclass whose positions also have names:

# named_tuple.py
from collections import namedtuple

Person = namedtuple("Person", ["name", "age", "height"])
alice = Person("Alice", 30, 1.65)
print(alice)
#: Person(name='Alice', age=30, height=1.65)
print(alice.name, alice.age)  # Access by name
#: Alice 30
print(alice[0])  # Still indexable like a tuple
#: Alice
name, age, height = alice  # And unpackable
print(height)
#: 1.65

A namedtuple is a fixed-length record like the tuple in heterogeneous.py, but its fields are self-documenting. typing.NamedTuple is the class form of the same idea: it declares a type for each field instead of listing bare names, so a type checker knows what each one holds. For a record that must be mutable, use a data class (see Data Classes as Types). Data Transfer Objects compares all three.

The standard library has more specialized containers. Performance covers compact homogeneous storage (array), a zero-copy view onto another object’s memory (memoryview), binary search in a sorted list (bisect), and a heap-backed priority queue (heapq).

Immutability

Each of the three built-in mutable containers has an immutable counterpart. A tuple is an immutable list, and a frozenset is an immutable set. Since Python 3.15, frozendict (PEP 814) completes the trio: a built-in, hashable mapping that rejects changes after creation. MappingProxyType, from the types module, is a read-only view onto a dict you still hold, not a container of its own. The example below uses it along with tuples and frozensets:

# immutable_containers.py
from types import MappingProxyType

# The immutable list is tuple; the immutable set, frozenset:
nums = (1, 2, 3)
primes = frozenset({2, 3, 5, 7})
print(5 in primes)
#: True

# Immutable containers are hashable, so they can be set
# members or dictionary keys. A plain list or set cannot:
groups = {frozenset({1, 2}), frozenset({3, 4})}
print(frozenset({1, 2}) in groups)
#: True

# MappingProxyType wraps a dict in a read-only view:
settings = {"debug": False, "level": 3}
config = MappingProxyType(settings)
print(config["level"])
#: 3
settings["level"] = 4  # The view is live, not a copy
print(config["level"])
#: 4

# Mutating any of them is an error:
try:
    primes.add(11)  # type: ignore
except AttributeError as e:
    print(e)
#: 'frozenset' object has no attribute 'add'
try:
    config["level"] = 9  # type: ignore
except TypeError as e:
    print(e)
#: 'mappingproxy' object does not support item assignment

Modifying an immutable container is a type error as well as a runtime error, so each line that attempts it carries a # type: ignore. The comment silences the type checker. The runtime exception is what the listing exists to show.

A MappingProxyType is a window onto a dict that still exists and can change; a frozendict owns its contents outright. This listing requires Python 3.15:

# frozendict_demo.py

prefs = frozendict(theme="dark", zoom=125)
print(prefs["zoom"])
#: 125
# Equal contents compare equal; entry order is ignored:
print(prefs == frozendict(zoom=125, theme="dark"))
#: True
cache = {prefs: "rendered"}  # Usable as a dict key
print(cache[frozendict(zoom=125, theme="dark")])
#: rendered
try:
    prefs["zoom"] = 150  # type: ignore
except TypeError as e:
    print(e)
#: 'frozendict' object does not support item assignment

Because a frozendict cannot change, it is hashable when its values are. Like a tuple or a frozenset, it can then be a dictionary key or a set member. A dictionary key must be hashable, though it need not be immutable. Immutability is how a container earns a stable hash.

Use the immutable form whenever a container should not change after you build it. Neither you nor the code that receives it can add, remove, or replace an element by accident, so a container of immutable elements needs no defensive copy before you share it. An immutable container is safe as a default argument, unlike the mutable default in Functions. A MappingProxyType is the one exception to watch. It blocks writes through the view, but it is a window onto the original dict, so changes to that dict still show through. In immutable_containers.py, writing to settings changes what config reports.

Immutability is also shallow. An immutable container fixes which objects it holds, not what those objects contain:

# shallow_immutability.py

nested = (1, [2, 3])
nested[1].append(4)  # The tuple's element is still mutable
print(nested)
#: (1, [2, 3, 4])
try:
    hash(nested)  # So the tuple cannot be hashed
except TypeError as e:
    print(e)
#: unhashable type: 'list'
try:
    nested[0] = 9  # type: ignore
except TypeError as e:
    print(e)
#: 'tuple' object does not support item assignment

The tuple holds the same list for its whole life, and that list stays free to change. A container holding an unhashable object is unhashable too. Immutability pays off when it goes all the way down. Rethinking Objects shows the same leak inside a frozen data class.

Choosing a container comes down to one question: what do you do with it most? Ordered items you walk through are a list. A fixed record whose positions mean different things is a tuple or a namedtuple. Lookup by key is a dict. Uniqueness and membership are a set. Go past those four only when a measurement or a specific job calls for it, and freeze whichever you pick as soon as it stops changing.

Exercises

In deque_timing.py, change n from 20_000 to 2_000, change the printed comparison to deque_time < list_time, and run the timing again. Does deque_time < list_time still hold? Change n to 200_000 and try again. The list version takes several seconds at that size, and much longer on a slow machine. That is the point. Explain what changes about the comparison as n grows.
In defaultdict.py, replace defaultdict(list) with defaultdict(int), change the loop to count occurrences of each kind instead of collecting names, and print the result.
In set_methods.py, add a third set c = {1, 5, 9} and print a.union(b, c) and a.intersection(b, c).
In immutable_containers.py, add a line that tries groups.add([1, 2]) (a plain list, not a frozenset) and catch the exception it raises. Explain, in terms of hashability, why a frozenset works as a set member but a list does not.
Given xs = [10, 20, 30, 40, 50], write one slice expression for each of: the last two items, everything but the first and last, and a reversed copy of the middle three.
Rewrite counter.py’s tally using a defaultdict(int) and no Counter. Which parts of Counter did you have to write yourself?
Rewrite heterogeneous.py with a namedtuple. Show that the unpacking line still works unchanged.
Given pairs = [("a", 1), ("b", 2), ("c", 3)], build a dict from it, then print its keys, its values, and the result of merging it with {"c": 30, "d": 4}. Which value ends up under "c", and why?
Using one unpacking assignment each, and no indexing, pull the first element, the last element, and everything in between out of row = [1, 2, 3, 4, 5]. Then explain why a, b = row raises a ValueError while a, *b = row does not.
Build a frozendict from the pairs [("host", "localhost"), ("port", 8080)], then use it as a key in a dict that maps a configuration to a connection name. Look that value up again with a separately built, equal frozendict. Catch the TypeError that assigning to one of its entries raises. Finally, build a frozendict whose value is a list, try to hash it, and explain the result in terms of shallow immutability.