AdvancedPython Programming · Lesson 24 of 30 · Updated ·
The collections Module — Counter, defaultdict, deque, namedtuple, OrderedDict
Lists, dicts, sets and tuples handle most jobs. But a few patterns come up again and again: counting things, grouping things, adding and removing at both ends, and giving names to tuple positions. The standard-library module collections has a ready-made, well-tested container for each. They appear constantly in coding tests and interviews, because they turn ten lines into two.
| Container | Use it for |
|---|---|
Counter | counting how often things appear |
defaultdict | dicts that create a default value for a missing key |
deque | fast adding and removing at both ends (queues) |
namedtuple | tuples whose positions have names |
OrderedDict | a dict with extra ordering methods (move_to_end) |
1. Counter: count anything
A Counter is a dictionary that maps each item to how many times it appears.
from collections import Counter
votes = ["Asha", "Ravi", "Asha", "Neha", "Asha", "Ravi"]
c = Counter(votes)
print(c)
print(c["Asha"], c["Imran"]) # a missing key gives 0, not KeyError
print(c.most_common(2))
Counter({'Asha': 3, 'Ravi': 2, 'Neha': 1})
3 0
[('Asha', 3), ('Ravi', 2)]
Counters can be updated and combined with arithmetic:
from collections import Counter
stock = Counter(pens=10, notebooks=4)
sold = Counter(pens=3, notebooks=4)
stock.update({"pens": 5}) # add 5 more pens
print(stock)
print(stock - sold) # zero and negative counts are dropped
print(Counter("listen") == Counter("silent"))
Counter({'pens': 15, 'notebooks': 4})
Counter({'pens': 12})
True
The last line is the classic anagram check: two words are anagrams if they contain the same letters with the same counts.
2. defaultdict: no more "if key not in dict"
With a normal dict, grouping items needs a check every time:
groups = {}
for name, branch in [("Asha", "CSE"), ("Ravi", "ECE"), ("Neha", "CSE")]:
if branch not in groups:
groups[branch] = []
groups[branch].append(name)
print(groups)
{'CSE': ['Asha', 'Neha'], 'ECE': ['Ravi']}
A defaultdict takes a factory: a function it calls to make a value for a missing key. list makes [], int makes 0, set makes set().
from collections import defaultdict
groups = defaultdict(list)
for name, branch in [("Asha", "CSE"), ("Ravi", "ECE"), ("Neha", "CSE")]:
groups[branch].append(name) # missing key → new empty list
print(dict(groups))
word_len = defaultdict(int)
for w in "to be or not to be".split():
word_len[len(w)] += 1
print(dict(word_len))
{'CSE': ['Asha', 'Neha'], 'ECE': ['Ravi']}
{2: 5, 3: 1}
Careful: even reading a missing key with d[key] creates it. Use key in d or d.get(key) if you only want to check.
3. deque: a fast double-ended queue
A list is fast at the end (append, pop), but slow at the front: list.pop(0) and list.insert(0, x) must shift every other item, which is O(n). A deque (say "deck") is O(1) at both ends.
from collections import deque
queue = deque(["Asha", "Ravi"]) # people waiting at a counter
queue.append("Neha") # joins at the back
first = queue.popleft() # served from the front
print(first, list(queue))
queue.appendleft("Senior citizen") # priority: goes to the front
print(list(queue))
queue.rotate(1) # move the last item to the front
print(list(queue))
Asha ['Ravi', 'Neha']
['Senior citizen', 'Ravi', 'Neha']
['Neha', 'Senior citizen', 'Ravi']
Use deque for BFS in graphs and trees, for task queues, and for "undo" histories.
maxlen: keep only the latest items
from collections import deque
recent = deque(maxlen=3) # remembers only the last 3 searches
for search in ["java", "python", "dsa", "sql", "git"]:
recent.append(search)
print(list(recent))
['dsa', 'sql', 'git']
When the deque is full, adding at one end automatically drops an item from the other end. It is perfect for "last N" records and moving averages.
4. namedtuple: tuples with field names
point[0] and point[1] do not say what they mean. A namedtuple creates a small tuple class whose positions also have names.
from collections import namedtuple
Student = namedtuple("Student", ["name", "branch", "cgpa"])
s = Student("Asha", "CSE", 8.9)
print(s)
print(s.name, s[2]) # by name or by position
name, branch, cgpa = s # still unpacks like a tuple
print(branch)
print(s._replace(cgpa=9.1)) # tuples are immutable → returns a NEW one
print(s._asdict())
Student(name='Asha', branch='CSE', cgpa=8.9)
Asha 8.9
CSE
Student(name='Asha', branch='CSE', cgpa=9.1)
{'name': 'Asha', 'branch': 'CSE', 'cgpa': 8.9}
A namedtuple is as light as a normal tuple and is immutable. If you need defaults, methods or changeable fields, use a dataclass instead.
5. OrderedDict and a simple LRU cache
Since Python 3.7, normal dicts keep insertion order, so OrderedDict is needed less. It is still useful for its move_to_end() and popitem(last=False) methods, which make an LRU cache (Least Recently Used: when full, throw away the item that was used longest ago) easy. This is a well-known interview problem.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.data = OrderedDict()
def get(self, key):
if key not in self.data:
return -1
self.data.move_to_end(key) # mark as 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.capacity:
self.data.popitem(last=False) # remove the least recently used
cache = LRUCache(2)
cache.put("a", 1)
cache.put("b", 2)
cache.get("a") # "a" is now the most recent
cache.put("c", 3) # full: "b" is evicted
print(list(cache.data.items()))
print(cache.get("b"))
[('a', 1), ('c', 3)]
-1
Both operations are O(1).
Common mistakes
- Using
list.pop(0)as a queue in a big loop. Usedeque.popleft(). - Reading
d[key]on a defaultdict just to check it, which silently adds the key. - Printing a defaultdict and being surprised by
defaultdict(<class 'list'>, …); wrap it indict()for clean output. - Trying to change a namedtuple field with
s.cgpa = 9. Use_replace(). - Forgetting that
Countersubtraction drops zero and negative counts.
Quick recap
Counter: counts items;most_common(k); missing keys give 0; supports+and-.defaultdict(list/int/set): makes a default value for missing keys.deque: O(1) at both ends;popleft,appendleft,rotate,maxlen.namedtuple: immutable tuple with named fields;_replace,_asdict.OrderedDict.move_to_end+popitem(last=False)→ LRU cache.