The collections module

You have met Counter in the standard library tour and deque in choosing the right collection, and abstract base classes at the intermediate level. This lesson goes further: multiset arithmetic, the containers the earlier lessons skipped, and how to write a mapping of your own. The general ideas behind maps, stacks and queues are in the fundamentals track, in maps and sets and stacks, queues and linked lists.

Counter arithmetic

A Counter is a dictionary from items to counts, and it supports arithmetic as a multiset, a set in which items can appear more than once. - subtracts, + adds, & keeps the smaller count of each item and | the larger. total() adds up all the counts:

from collections import Counter

stock = Counter(apples=5, pears=2)
sold = Counter(apples=3, pears=2, plums=1)

print(stock - sold)
print(stock + sold)
print(stock & sold)
print(stock | sold)
print(stock.total(), sold.total())

Counter({'apples': 2})
Counter({'apples': 8, 'pears': 4, 'plums': 1})
Counter({'apples': 3, 'pears': 2})
Counter({'apples': 5, 'pears': 2, 'plums': 1})
7 6

The subtraction left no pears and no plums. Every binary operator on counters keeps only positive counts, so a stock level can never print as negative. When you do want negative counts, use the method subtract, which changes the counter in place and keeps everything. A unary + then strips the zero and negative entries. Counters also compare as multisets: <= asks “is every count on the left at most the one on the right?”, treating missing items as zero.

left = stock.copy()
left.subtract(sold)
print(left)
print(+left)
print(Counter(apples=2) <= stock)

Counter({'apples': 2, 'pears': 0, 'plums': -1})
Counter({'apples': 2})
True

3.15+Requires version 3.15 or later Python 3.15 adds ^, the symmetric difference: for each item, how far apart the two counts are, keeping only the items that differ.

from collections import Counter

monday = Counter(tea=3, coffee=5)
tuesday = Counter(tea=1, coffee=5, juice=2)
print(monday ^ tuesday)

Counter({'tea': 2, 'juice': 2})

defaultdict for grouping

A defaultdict calls a factory function to create the value for a missing key. With list as the factory, grouping becomes one line in the loop, with no “is the key there yet?” check:

from collections import defaultdict

words = ["ant", "ape", "bee", "cow"]

by_letter = defaultdict(list)
for word in words:
    by_letter[word[0]].append(word)
print(by_letter)
print(dict(by_letter))

defaultdict(<class 'list'>, {'a': ['ant', 'ape'], 'b': ['bee'], 'c': ['cow']})
{'a': ['ant', 'ape'], 'b': ['bee'], 'c': ['cow']}

int gives counts that start at 0, and set gives groups without duplicates. Wrapping the result in dict() gives an ordinary dictionary for printing or for passing on.

The factory runs on any lookup with square brackets, including one that only reads:

print(by_letter.get("q"), len(by_letter))
print(by_letter["z"])
print("z" in by_letter, len(by_letter))

None 3
[]
True 4

get does not trigger the factory, so the length stayed at 3. Reading by_letter["z"] created an empty list for "z", and now the dictionary has 4 keys. In code that only checks for a key, use in or get, or convert to a plain dict once the grouping is done.

OrderedDict for an LRU cache

A plain dict keeps insertion order, so OrderedDict is no longer needed for that. It survives for two operations a dict lacks: move_to_end(key) moves a key to the end, or to the front with last=False, and popitem(last=False) removes the oldest key. Together they make a least recently used (LRU) cache: every use moves a key to the end, so the front is always the key to evict:

from collections import OrderedDict


class LRUCache:
    def __init__(self, size):
        self.size = size
        self.data = OrderedDict()

    def get(self, key):
        if key not in self.data:
            return None
        self.data.move_to_end(key)  # now the most recently used
        return self.data[key]

    def put(self, key, value):
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.size:
            self.data.popitem(last=False)  # drop the least recently used


cache = LRUCache(2)
cache.put("a", 1)
cache.put("b", 2)
cache.get("a")
cache.put("c", 3)
print(list(cache.data), cache.get("b"))

['a', 'c'] None

Reading a made b the oldest key, so adding c evicted b. Both operations take constant time. For caching a function’s results, functools.lru_cache already does this. Write your own when the cache needs to hold something other than return values, or to report what it evicts.

A deque is the other ordered container here. Beyond the queue operations from the beginner lesson, rotate(n) moves the last n items to the front, and maxlen makes a bounded buffer, as the first exercise uses.

namedtuple: a tuple with field names

namedtuple builds a tuple subclass whose positions also have names. Instances are still tuples, so they unpack, index and compare like one, and use no more memory:

from collections import namedtuple

Point = namedtuple("Point", ["x", "y"])
p = Point(3, 4)
print(p, p.x, p[1])

x, y = p
print(x + y, p == (3, 4))
print(p._replace(y=10), p._asdict())

Point(x=3, y=4) 3 4
7 True
Point(x=3, y=10) {'x': 3, 'y': 4}

Since a named tuple is immutable, _replace returns a new one. The leading underscore keeps the method names out of the way of your field names, not to mark them private. The class form, typing.NamedTuple, reads better, takes defaults and methods, and gives type checkers the field types:

from typing import NamedTuple


class Version(NamedTuple):
    major: int
    minor: int
    patch: int = 0

    def __str__(self):
        return f"{self.major}.{self.minor}.{self.patch}"


versions = [Version(3, 15), Version(3, 9, 2), Version(3, 14, 8)]
print(Version._fields)
print(max(versions), min(versions))
print(repr(versions[0]))

('major', 'minor', 'patch')
3.15.0 3.9.2
Version(major=3, minor=15, patch=0)

The versions compared as tuples, field by field, so max found 3.15. That ordering is a reason to choose a named tuple. Choose a dataclass when the record should not act as a tuple: a dataclass is never equal to a plain tuple, cannot be unpacked by accident, and can be mutable.

ChainMap: layered lookups

A ChainMap searches several mappings in order and returns the first value it finds, without copying anything. This is exactly how settings work: command-line options beat the config file, which beats the defaults.

from collections import ChainMap

defaults = {"colour": "auto", "width": 80, "verbose": False}
from_file = {"width": 100}
from_cli = {"verbose": True}

settings = ChainMap(from_cli, from_file, defaults)
print(settings["width"], settings["verbose"], settings["colour"])
print(dict(settings))

100 True auto
{'colour': 'auto', 'width': 100, 'verbose': True}

Writes and deletions only ever touch the first mapping. new_child puts a new mapping in front, empty or the one you pass, which is handy for a temporary override, such as one test:

settings["colour"] = "never"
print(from_cli)
print(defaults["colour"], settings["colour"])

test = settings.new_child({"width": 40})
print(test["width"], settings["width"])

{'verbose': True, 'colour': 'never'}
auto never
40 100

defaults kept "auto": the assignment landed in from_cli. Since a ChainMap is a view, a later change to defaults shows through it immediately.

The same structure models scopes, the way Python itself looks up a name: local, then module, then built-in. Each function call adds a child in front, and assignments land in the innermost scope:

from collections import ChainMap

builtins = {"print": "<built-in print>", "len": "<built-in len>"}
module = ChainMap({"x": 1, "len": 3}, builtins)
function = module.new_child({"y": 2})

print(function["x"], function["y"], function["print"], function["len"])
function["x"] = 99  # a local assignment shadows the module's x
print(function["x"], module["x"], function.maps[0])
print(function.parents == module)

1 2 <built-in print> 3
99 1 {'y': 2, 'x': 99}
True

The module’s len shadows the built-in one, exactly the bug a module-level len = 3 causes. maps is the list of layers, and parents is a new ChainMap without the first one, the scope a function returns to.

UserDict: when you need a custom dict

To change how a mapping stores keys, subclassing dict looks natural, but dict’s own methods do not call your overrides. __init__ and update write directly into the table, bypassing __setitem__. collections.UserDict keeps its data in a real dict at self.data, and all its methods go through the mapping methods, so one override covers every path:

from collections import UserDict


class LowerDict(dict):
    def __setitem__(self, key, value):
        super().__setitem__(key.lower(), value)


class LowerUserDict(UserDict):
    def __setitem__(self, key, value):
        super().__setitem__(key.lower(), value)


for cls in (LowerDict, LowerUserDict):
    d = cls({"Host": "db"})
    d.update(Port=5432)
    d["USER"] = "ada"
    print(cls.__name__, sorted(d))

LowerDict ['Host', 'Port', 'user']
LowerUserDict ['host', 'port', 'user']

Only the explicit d["USER"] assignment reached the dict subclass’s override. Subclass dict when you only add methods, or override __missing__, the hook defaultdict uses. When you change behaviour, use UserDict.

Your own mapping from collections.abc

When the data does not live in a dict at all, inherit from collections.abc.Mapping and write three methods: __getitem__, __iter__ and __len__. The class then gets get, keys, items, values, in, == and the rest for free, and isinstance(x, Mapping) is true. MutableMapping adds __setitem__ and __delitem__ to the list and gives you update, pop and setdefault. Here is a read-only view of environment variables with a prefix:

from collections.abc import Mapping


class EnvView(Mapping):
    """Read-only view of the variables that start with a prefix."""

    def __init__(self, environ, prefix):
        self._environ = environ
        self._prefix = prefix

    def __getitem__(self, key):
        return self._environ[self._prefix + key]

    def __iter__(self):
        n = len(self._prefix)
        return (k[n:] for k in self._environ if k.startswith(self._prefix))

    def __len__(self):
        return sum(1 for _ in self)


env = {"APP_HOST": "db", "APP_PORT": "5432", "HOME": "/home/ada"}
app = EnvView(env, "APP_")
print(dict(app), len(app))
print("PORT" in app, app.get("USER", "-"), app == {"HOST": "db", "PORT": "5432"})

{'HOST': 'db', 'PORT': '5432'} 2
True - True

get, in and == came from the base class, built on the three methods. If you only need type checkers to accept “anything with __getitem__”, a protocol is lighter than inheriting.

Flattening and merging

3.15+Requires version 3.15 or later Python 3.15 allows * and ** unpacking inside comprehensions (PEP 798). [*batch for batch in batches] flattens one level, and {**d for d in dicts} merges dictionaries with later keys winning:

from itertools import chain

batches = [["ada", "ben"], [], ["cy"]]
print([name for batch in batches for name in batch])
print(list(chain.from_iterable(batches)))
print([*batch for batch in batches])

layers = [{"width": 80, "colour": "auto"}, {"width": 100}, {"colour": "never"}]
print({**layer for layer in layers})

['ada', 'ben', 'cy']
['ada', 'ben', 'cy']
['ada', 'ben', 'cy']
{'width': 100, 'colour': 'never'}

The three lists are the same, but the unpacking form says what it does, and {*s for s in sets} and (*x for x in xs) work the same way. Code that must run on older versions keeps using chain.from_iterable. The merged dictionary is a copy, unlike the live view a ChainMap gives.

When not to reach for collections

A plain dict or list is the default, and most code needs nothing else. Do not wrap a dict in UserDict just in case, or write a Mapping class for data that is a dictionary anyway. Use defaultdict while building a structure, then hand out a plain dict. Use Counter for counting, not as a general number store, since its operators silently drop negative values. Reach for namedtuple only when tuple behaviour is wanted, and a dataclass otherwise.

Common pitfalls

• Expecting negative counts from -. Counter operators drop zero and negative counts. Use subtract() to keep them.
• Reading a defaultdict with square brackets. A lookup adds the key. Use in or get to check.
• Overriding __setitem__ on a dict subclass. __init__, update and setdefault bypass it. Use UserDict.
• Assuming ChainMap writes go to the mapping that has the key. They always go to the first mapping.
• Implementing __len__ and __iter__ inconsistently. The Mapping mixins trust both. Derive one from the other, as EnvView does.

['a.py']
['b.py', 'a.py']
['c.py', 'b.py', 'a.py']
['a.py', 'c.py', 'b.py']
['d.py', 'a.py', 'c.py']
['e.py', 'd.py', 'a.py']

from collections import deque


class RecentFiles:
    def __init__(self, size):
        self._items = deque(maxlen=size)

    def open(self, name):
        if name in self._items:
            self._items.remove(name)
        self._items.appendleft(name)

    def items(self):
        return list(self._items)


recent = RecentFiles(3)
for name in ["a.py", "b.py", "c.py", "a.py", "d.py", "e.py"]:
    recent.open(name)
    print(recent.items())

['a.py']
['b.py', 'a.py']
['c.py', 'b.py', 'a.py']
['a.py', 'c.py', 'b.py']
['d.py', 'a.py', 'c.py']
['e.py', 'd.py', 'a.py']

from collections import Counter, defaultdict

seen = defaultdict(int)
for word in ["a", "b", "a"]:
    seen[word] += 1
if seen["c"] == 0:
    print("no c")
print(len(seen))
print(Counter(a=2) - Counter(a=5, b=1))

no c
3
Counter()

text/html True */*
['accept', 'content-type']

from case_insensitive import Headers

headers = Headers({"Content-Type": "text/html"})
headers.update({"X-Trace": "a1"})
headers["ACCEPT"] = "*/*"
print(headers["content-type"], "x-trace" in headers, headers.get("Accept"))
del headers["X-TRACE"]
print(sorted(headers))

from collections import UserDict


class Headers(UserDict):
    def __setitem__(self, key, value):
        super().__setitem__(key.lower(), value)

    def __getitem__(self, key):
        return super().__getitem__(key.lower())

    def __delitem__(self, key):
        super().__delitem__(key.lower())

    def __contains__(self, key):
        return key.lower() in self.data

Summary

• Counter does multiset arithmetic. Operators keep positive counts only, subtract() keeps all, and total() sums them. 3.15+Requires version 3.15 or later ^ gives the symmetric difference.
• defaultdict fills in missing keys from a factory, on every square-bracket lookup.
• OrderedDict.move_to_end and popitem(last=False) make an LRU cache.
• namedtuple and typing.NamedTuple give tuples field names. Use a dataclass when the record should not behave as a tuple.
• ChainMap layers mappings for settings and scopes, and writes only to the first.
• Override behaviour with UserDict, not a dict subclass. For data stored elsewhere, implement Mapping with three methods.
• 3.15+Requires version 3.15 or later [*x for x in xs] flattens and {**d for d in ds} merges.
• Next: immutability, and how to design data that cannot change under you.