LRU-style caches
Maintain a bounded recent-items structure by moving accessed keys to one endpoint and evicting from the other.
Python · Class
OrderedDict
OrderedDict is a dict subclass for mappings where changing entry order is important. It adds endpoint reordering and configurable-end removal operations beyond ordinary dictionary behavior.
- Since
- 3.1
How it works
OrderedDict is a dict subclass built for operations that rearrange key order. It retains insertion order, lets you move an existing key to either endpoint, and lets popitem choose whether removal occurs from the right or left.
Syntax
class collections.OrderedDict([items])Parameters
| Name | Type | Description |
|---|---|---|
iterable | iterable or mapping | Optional iterable or mapping supplying initial key-value pairs; the class constructor otherwise accepts the usual mapping-style inputs. |
last | bool | Whether to remove from the right endpoint (default) or the left endpoint. |
key | hashable | Existing key whose entry should be moved to an endpoint. |
Returns
An instance of a dict subclass with methods specialized for rearranging dictionary order.
Key points
- OrderedDict provides normal mapping behavior plus operations specifically concerned with changing entry order.
- Its design prioritizes efficient reordering rather than minimizing space or maximizing iteration speed.
- Choose it when a program repeatedly changes the relative positions of entries.
- Constructing OrderedDict returns a dictionary subclass with order-management methods.
- move_to_end() is the dedicated operation for moving an existing entry to either boundary.
- An OrderedDict can be traversed backwards with reversed().
Common mistakes
- popitem() removes from the right by default, but passing last=False removes from the left.
- Assigning a new value to an existing key does not reposition that key.
- Two OrderedDict instances with identical key-value pairs can compare unequal when their orders differ.
Example: Reorder and remove items
from collections import OrderedDict
recent = OrderedDict([("a", 1), ("b", 2), ("c", 3)])
recent.move_to_end("a")
print(list(recent.items()))
print(recent.popitem(last=False))
print(list(recent.items()))Creates an ordered mapping, moves an existing key to the right endpoint, then removes the leftmost item.
When to use it
Reordering-heavy workflows
Repeatedly reposition entries while preserving mapping access and iteration behavior.
Deque-like mapping operations
Consume entries from either endpoint with explicit FIFO or LIFO semantics.
Interview questions
QWhat distinguishes OrderedDict from dict?
OrderedDict is a dict subclass with methods specialized for rearranging dictionary order. It remains useful when frequent reordering matters, even though regular dict preserves insertion order.
Follow-up: Why is it suitable for an LRU cache? Its move_to_end() method efficiently moves accessed entries to an endpoint, and popitem(last=False) can evict the oldest entry.
QHow does popitem() determine which item to remove?
popitem(last=True) removes and returns a key-value pair from the right side, giving LIFO behavior. With last=False, it removes from the left side, giving FIFO behavior.
Follow-up: How would you remove the oldest entry? Call popitem(last=False), because the leftmost item is the earliest ordered entry.
QHow does move_to_end() reorder entries?
move_to_end(key, last=True) moves an existing key to the right endpoint by default. Passing last=False moves it to the beginning.
Follow-up: What happens if the key is absent? The operation cannot move a nonexistent key; normal key lookup behavior raises KeyError.
Related
dictdefaultdictCounterUserDictmove_to_end()popitem()reversed()