When to Use OrderedDict Instead of dict

You are writing a small cache that keeps the 100 results used most recently. When it is full, it drops the one used longest ago. A plain dict keeps its keys in the order you inserted them, and d[key] = d.pop(key) moves a key to the end. But a dict has no quick way to remove the oldest entry or to move a key to the front. A collections.OrderedDict has both.

from collections import OrderedDict

values = OrderedDict(a=1, b=2, c=3)
values.move_to_end("a")
assert list(values) == ["b", "c", "a"]
values.move_to_end("c", last=False)
assert list(values) == ["c", "b", "a"]
assert values.popitem(last=False) == ("c", 3)

The move_to_end(key) method moves a key to the end, or to the front with last=False, and keeps its value. A missing key raises KeyError.

Remove from either end

dict.popitem() removes the pair you inserted last. OrderedDict.popitem(last=False) removes the first pair in the current order instead. Both raise KeyError when the dict is empty. After move_to_end, the first pair is not always the one you inserted first.

Build a small LRU cache

An LRU cache, short for least recently used, keeps a fixed number of entries and drops the one used longest ago. Move a key to the end each time you read or write it, then remove from the front when the cache is too big:

from collections import OrderedDict


class LRU:
    def __init__(self, capacity: int) -> None:
        if capacity < 0:
            raise ValueError("capacity must be 0 or more")
        self.capacity = capacity
        self._data: OrderedDict[str, int] = OrderedDict()

    def get(self, key: str) -> int | None:
        if key not in self._data:
            return None
        self._data.move_to_end(key)
        return self._data[key]

    def put(self, key: str, value: int) -> None:
        self._data[key] = value
        self._data.move_to_end(key)
        if len(self._data) > self.capacity:
            self._data.popitem(last=False)


cache = LRU(2)
cache.put("a", 1)
cache.put("b", 2)
cache.get("a")     # "a" is now the most recent
cache.put("c", 3)  # the cache is full, so "b" goes
assert cache.get("b") is None
assert cache.get("a") == 1

Here None means a miss, which works because the stored values are ints. A capacity of 0 keeps nothing. To cache the results of a function, use functools.lru_cache instead, which a later article in this track covers.

Equality between two OrderedDicts includes order

from collections import OrderedDict

left = OrderedDict(a=1, b=2)
right = OrderedDict(b=2, a=1)
assert left != right
assert left == dict(right)
assert dict(left) == dict(right)

Two OrderedDict objects are equal only when their items are in the same order. An OrderedDict compared with a plain dict ignores order. So using OrderedDict does not make every comparison check order. To test that a result has the right items in the right order, compare list(result.items()) with the list you expect.

Insertion order is not sorted order

mapping = {"a": 1, "b": 2}
mapping["a"] = 3
assert list(mapping) == ["a", "b"]
del mapping["a"]
mapping["a"] = 4
assert list(mapping) == ["b", "a"]
assert sorted(mapping.items()) == [("a", 4), ("b", 2)]

Changing the value of an existing key keeps its position, in a dict and in an OrderedDict. Deleting the key and adding it again puts it at the end. Neither type keeps its keys sorted. When you need sorted output, call sorted at the point where you produce that output.

Conversions give you a plain dict

dict(ordered) and {**ordered} return a plain dict. The items stay in the same order, but the OrderedDict methods and the order-aware equality are gone. json.loads also builds plain dicts. Pass object_pairs_hook=OrderedDict if you need an OrderedDict instead.

Going further

An OrderedDict uses more memory than a dict. Choose it for one of the behaviors above, and use a plain dict when insertion order is all you need.