Skip to content

Choosing the Right Container

What this lesson gives you

The collections module and dataclasses give you purpose-built structures. Picking the right one signals engineering maturity.

Estimated time: 20 min read · Part: Data Structures That Carry Real Work

Learning objectives

  • Know the full collections toolkit: Counter, defaultdict, deque, namedtuple, OrderedDict, ChainMap
  • Write @dataclasses correctly, including safe mutable defaults with field()
  • Use heapq as a priority queue for scheduling and top-k problems
  • Apply the container selection decision framework to any problem
  • Understand array.array and memoryview for memory-efficient numeric storage

Beyond the four core containers, the standard library's collections module offers specialized structures for common patterns. Reaching for the right one — instead of bolting everything onto a plain dict or list — signals the difference between someone who knows Python and someone who engineers with it. A Counter where you'd otherwise write three lines of counting logic; a defaultdict where you'd write a setdefault() check; a deque where you'd write costly pop(0) calls.

Counter: Frequency Analysis in One Line

Counter is a dict subclass purpose-built for counting. You construct it from any iterable and get a mapping of element → count. Its .most_common(n) method returns the top-n elements by frequency in O(n log k) time. Counter objects support arithmetic: adding two Counters sums their counts; subtracting removes counts (keeping only positives).

counter_patterns.py
from collections import Counter

# Construct from any iterable
word_freq = Counter("the quick brown fox jumps over the lazy fox".split())
# Counter({'the': 2, 'fox': 2, 'quick': 1, ...})

word_freq.most_common(3)    # [('the', 2), ('fox', 2), ('quick', 1)]
word_freq["the"]            # 2
word_freq["missing"]        # 0  — Counter never raises KeyError

# Arithmetic on Counters
a = Counter({"python": 3, "java": 2, "rust": 1})
b = Counter({"python": 1, "go": 4, "java": 1})
a + b    # Counter({'go': 4, 'python': 4, 'java': 3, 'rust': 1})
a - b    # Counter({'python': 2, 'rust': 1})  — positive only
a & b    # Counter({'python': 1, 'java': 1})  — min of each
a | b    # Counter({'go': 4, 'python': 3, 'java': 2, 'rust': 1})  — max

# Real-world: count HTTP status codes in access log
import re
log_lines = [
    "GET /api/users 200", "POST /api/orders 201",
    "GET /api/users 200", "DELETE /api/item 404",
    "GET /api/orders 500", "GET /api/users 200",
]
status_codes = Counter(
    m.group() for line in log_lines
    if (m := re.search(r"\d{3}$", line))
)
print(status_codes)     # Counter({'200': 3, '201': 1, '404': 1, '500': 1})
print(status_codes.most_common(2))   # [('200', 3), ('201', 1)]

Counter({'200': 3, '201': 1, '404': 1, '500': 1})

defaultdict and ChainMap: Auto-init and Layered Lookups

defaultdict takes a callable as its first argument. When a missing key is accessed, it calls that callable to produce a default and inserts it. This eliminates the boilerplate if key not in d: d[key] = [] pattern, making grouping and accumulation code much cleaner.

defaultdict_patterns.py
from collections import defaultdict, ChainMap

# Grouping: one-to-many mapping
events = [
    ("alice", "login"), ("bob", "view"), ("alice", "purchase"),
    ("carol", "login"), ("bob", "logout"), ("alice", "logout"),
]

by_user = defaultdict(list)
for user, action in events:
    by_user[user].append(action)
# defaultdict(list, {'alice': ['login', 'purchase', 'logout'],
#                    'bob':   ['view', 'logout'],
#                    'carol': ['login']})

# Nested grouping: region → category → list of amounts
sales = [
    ("EU", "hardware", 200), ("US", "software", 150),
    ("EU", "software", 80),  ("US", "hardware", 320),
    ("EU", "hardware", 110),
]
grouped = defaultdict(lambda: defaultdict(list))
for region, cat, amount in sales:
    grouped[region][cat].append(amount)
# {"EU": {"hardware": [200, 110], "software": [80]}, ...}

# Summing: accumulate totals without init check
revenue = defaultdict(float)
for region, _, amount in sales:
    revenue[region] += amount
# defaultdict(float, {'EU': 390.0, 'US': 470.0})

# ChainMap: layered lookup (think: local scope → module scope → builtins)
defaults = {"color": "blue", "size": "M", "qty": 1}
user_prefs = {"size": "XL"}
session = {"qty": 3}

# First match wins — like variable scoping
config = ChainMap(session, user_prefs, defaults)
config["size"]    # "XL"   — from user_prefs
config["color"]   # "blue" — fallback to defaults
config["qty"]     # 3      — from session

dataclasses: Structured Records Without Boilerplate

@dataclass (Python 3.7+) generates __init__, __repr__, and __eq__ from class-level type annotations. It's the recommended way to define data-carrying objects — more expressive than a plain dict, less ceremonious than a full OOP class. The field() function handles mutable defaults, computed fields, and comparison exclusion.

dataclasses_deep.py
from dataclasses import dataclass, field, KW_ONLY
from datetime import datetime

@dataclass
class LineItem:
    sku:   str
    qty:   int
    price: float

    @property
    def subtotal(self) -> float:
        return round(self.qty * self.price, 2)

@dataclass
class Order:
    id:         int
    customer:   str
    items:      list[LineItem] = field(default_factory=list)   # safe mutable default
    created_at: datetime       = field(default_factory=datetime.utcnow)
    _:          KW_ONLY        = field(init=False, repr=False)  # forces rest to kw-only
    paid:       bool           = False

    def total(self) -> float:
        return round(sum(i.subtotal for i in self.items), 2)

    def add_item(self, sku: str, qty: int, price: float) -> None:
        self.items.append(LineItem(sku, qty, price))

# Usage
order = Order(id=1, customer="Ada")
order.add_item("PEN-001", qty=3, price=2.50)
order.add_item("PAD-002", qty=1, price=12.99)
print(order.total())   # 20.49
print(order)
# Order(id=1, customer='Ada', items=[LineItem(...), LineItem(...)], paid=False)

# Frozen dataclass: immutable, hashable (can be a set member / dict key)
@dataclass(frozen=True)
class Point:
    x: float
    y: float

p = Point(1.0, 2.0)
# p.x = 3.0  # FrozenInstanceError
{p: "origin"}   # works because frozen=True makes it hashable

20.49 Order(id=1, customer='Ada', items=[LineItem(sku='PEN-001', qty=3, price=2.5), LineItem(sku='PAD-002', qty=1, price=12.99)], paid=False)

Never use a mutable default in @dataclass without field()

The exact same mutable-default-argument bug applies: items: list = [] as a dataclass field would be shared across all instances. Python 3.7+ detects this and raises ValueError: mutable default ... is not allowed. The fix is always field(default_factory=list) — the factory is called fresh for each instance. This is one of the most common dataclass mistakes when migrating from plain dicts.

heapq: Priority Queues and Top-K Problems

A min-heap is a binary tree stored in a list where every parent is smaller than its children. The standard library's heapq module gives O(log n) push/pop and O(n) heapify. Use it for: scheduler priority queues, Dijkstra's algorithm, top-k elements, and merge-sorted-iterables.

heapq_patterns.py
import heapq

# Min-heap: smallest element always at index 0
tasks = []
heapq.heappush(tasks, (3, "low priority task"))
heapq.heappush(tasks, (1, "urgent task"))
heapq.heappush(tasks, (2, "normal task"))

heapq.heappop(tasks)    # (1, 'urgent task')  — always min
heapq.heappop(tasks)    # (2, 'normal task')

# Top-k smallest/largest — O(n log k) — more efficient than full sort for small k
scores = [88, 42, 95, 67, 12, 73, 99, 56, 31, 84]
heapq.nlargest(3, scores)     # [99, 95, 88]
heapq.nsmallest(3, scores)    # [12, 31, 42]

# Merge sorted iterables — O(n log k) where k = number of iterables
import heapq
iter1 = [1, 4, 7]
iter2 = [2, 5, 8]
iter3 = [3, 6, 9]
list(heapq.merge(iter1, iter2, iter3))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

# Max-heap trick: negate the priority
events = [(3, "C"), (1, "A"), (4, "D"), (2, "B")]
max_heap = []
for priority, item in events:
    heapq.heappush(max_heap, (-priority, item))  # negate for max behavior
heapq.heappop(max_heap)   # (-4, 'D') — was highest priority
Need Best container Why
Ordered, grows/shrinks at end list Default; O(1) amortized append/pop
Queue: add right, remove left collections.deque O(1) both ends
Sliding window / BFS frontier collections.deque O(1) pops; maxlen auto-evicts
Key-value mapping dict O(1) average lookup
Counting occurrences collections.Counter Built-in most_common(), arithmetic
Grouping (one-to-many) collections.defaultdict(list) Auto-creates empty list on first access
Fast membership test / dedup set O(1) membership; auto-deduplicates
Ordered set of unique items dict (keys only, 3.7+) Preserves insertion order unlike set
Fixed named record (immutable) collections.namedtuple or frozen @dataclass Hashable, named fields
Structured record with behavior @dataclass Auto-generates init/repr/eq
Priority queue / top-k heapq O(log n) push/pop, O(n log k) top-k
Large numeric array (homogeneous) array.array or NumPy Typed storage: 4–8× less memory than list

Consulting lens: container choice as a design signal

In code reviews and technical interviews, the containers you reach for reveal your fluency. A candidate who writes manual counting loops when Counter exists, or uses dict.setdefault() in a loop when defaultdict is available, signals they're at API-awareness level. A candidate who picks Counter, defaultdict, heapq, and frozen dataclasses without prompting signals they've internalized the standard library — and that they'll write code teammates can maintain. The right container isn't just more efficient; it expresses intent in the code itself.

Knowledge check

InterviewYou need to count occurrences of each word in a document and get the three most common. What is the most Pythonic approach?

  • A manual dict with a custom sort function written from scratch.
  • collections.Counter(words).most_common(3) — one call, purpose-built, O(n) counting + O(n log k) top-k.
  • Convert to a set, then count — sets track frequencies automatically.
  • Sort the word list and walk it counting runs.
Answer

collections.Counter(words).most_common(3) — one call, purpose-built, O(n) counting + O(n log k) top-k.

Counter is a dict subclass purpose-built for tallying. Constructing from an iterable counts everything in one pass. .most_common(n) returns the top-n (element, count) pairs sorted by frequency — it uses a partial sort internally and is O(n log k) where k is the number requested. It's concise, correct, and faster than a hand-rolled solution.

Knowledge check

GotchaWhat error does Python raise for: @dataclass class Cfg: items: list = []?

  • No error — Python silently shares the list across instances.
  • ValueError: mutable default <class 'list'> for field items is not allowed — use field(default_factory=list) instead.
  • TypeError: unhashable type 'list'.
  • SyntaxError — type annotations in dataclasses can't use list.
Answer

ValueError: mutable default <class 'list'> for field items is not allowed — use field(default_factory=list) instead.

Python 3.7+ dataclasses detect mutable defaults and raise ValueError at class definition time to prevent the shared-state bug. The fix is always items: list = field(default_factory=list) — the factory creates a fresh list for every new instance. This protection doesn't exist for plain classes, making dataclasses safer by design.

Knowledge check

InterviewYou need the single smallest item from a million-item list, added to one at a time. Which is better: maintaining a sorted list or using heapq?

  • Sorted list is better because sorted() is highly optimized in Python.
  • heapq — each push/pop is O(log n) vs O(n) for inserting into a sorted list. For n insertions, heap is O(n log n) total vs O(n²) for maintaining a sorted list.
  • They are equivalent in performance.
  • Use a set, since sets are always O(1).
Answer

heapq — each push/pop is O(log n) vs O(n) for inserting into a sorted list. For n insertions, heap is O(n log n) total vs O(n²) for maintaining a sorted list.

Maintaining a sorted list requires inserting each new element at the correct position — bisect + list.insert is O(log n) for finding the spot but O(n) for the actual insertion (shifting). Over n insertions: O(n²). A heap maintains the partial-order invariant with a single O(log n) "sift" operation on each push. For n pushes: O(n log n). Use heapq when you need minimum access and are adding elements one at a time.

Exercise: Event Analytics Pipeline

You have a stream of analytics events as a list of dicts with keys user_id, event_type, and revenue (may be 0.0 for non-purchase events). Write functions to: (1) count events per type using Counter, (2) group events by user using defaultdict, (3) find the top 5 users by total revenue using heapq. Write a UserStats dataclass to hold the per-user summary.

Show solution 
from collections import Counter, defaultdict
from dataclasses import dataclass, field
import heapq

@dataclass
class UserStats:
    user_id:      str
    event_count:  int        = 0
    total_revenue: float     = 0.0
    event_types:  list[str]  = field(default_factory=list)

def analyze_events(events: list[dict]):
    # 1. Count events per type
    type_counts = Counter(e["event_type"] for e in events)

    # 2. Group by user_id
    by_user: dict[str, UserStats] = defaultdict(
        lambda: UserStats(user_id="")
    )
    for event in events:
        uid  = event["user_id"]
        stat = by_user[uid]
        stat.user_id = uid
        stat.event_count += 1
        stat.total_revenue += event.get("revenue", 0.0)
        stat.event_types.append(event["event_type"])

    # 3. Top 5 by revenue using heapq.nlargest
    top5 = heapq.nlargest(
        5,
        by_user.values(),
        key=lambda s: s.total_revenue
    )

    return type_counts, dict(by_user), top5

# Sample data
events = [
    {"user_id": "u1", "event_type": "view",     "revenue": 0.0},
    {"user_id": "u2", "event_type": "purchase", "revenue": 49.99},
    {"user_id": "u1", "event_type": "purchase", "revenue": 199.0},
    {"user_id": "u3", "event_type": "view",     "revenue": 0.0},
    {"user_id": "u2", "event_type": "purchase", "revenue": 89.0},
    {"user_id": "u1", "event_type": "view",     "revenue": 0.0},
]

type_counts, user_map, top5 = analyze_events(events)
print("Event types:", type_counts)
print("Top users by revenue:")
for stat in top5:
    print(f"  {stat.user_id}: ${stat.total_revenue:.2f} ({stat.event_count} events)")

Key takeaways

  • Counter tallies any iterable; .most_common(n) returns top-n in O(n log k).
  • defaultdict(factory) auto-creates missing values — eliminates setdefault() boilerplate.
  • @dataclass generates __init__/__repr__/__eq__; use field(default_factory=list) for mutable defaults.
  • heapq gives O(log n) push/pop and is the right tool for priority queues and top-k problems.
  • Frozen dataclasses are hashable records usable as dict keys and set members.
  • Reaching for the precise container instead of over-using list/dict is a signal of engineering maturity.