{"title":"OrderedDict","description":"","content":"`collections.OrderedDict` is a dictionary subclass that remembers the order keys were added. Regular dictionaries already preserve insertion order since Python 3.7, so `OrderedDict` looks redundant at first glance. It isn't. `OrderedDict` carries a few order-aware operations that plain `dict` doesn't have, and it compares two instances with order in mind. This lesson covers what `OrderedDict` still buys you in modern Python and the e-commerce scenarios where it's the right tool.\n\n---\n\n# A Brief History\n\nFor most of Python's life, `dict` made no promise about key order. Iterating a dict could yield keys in any sequence, and that sequence could change between runs. If you needed predictable order, you reached for `collections.OrderedDict`, which was added in Python 3.1 for exactly this reason.\n\nThat changed in Python 3.6, when CPython's new dict implementation happened to preserve insertion order as an implementation detail. In Python 3.7, this became part of the language specification. Every Python 3.7+ implementation guarantees that iterating a dict yields keys in the order they were inserted.\n\nSo why does `OrderedDict` still exist? Two reasons. First, removing it would break a huge amount of older code. Second, and more importantly, `OrderedDict` has methods and behaviors that regular dicts don't have. The order-preservation overlap is real, but it's not the whole feature set.\n\nThis lesson focuses on what `OrderedDict` adds beyond the insertion-order guarantee that regular dicts already provide.\n\n\n```python\nfrom collections import OrderedDict\n\nrecently_viewed = OrderedDict()\nrecently_viewed[\"wireless-mouse\"] = \"Wireless Mouse\"\nrecently_viewed[\"usb-cable\"] = \"USB Cable\"\nrecently_viewed[\"hd-webcam\"] = \"HD Webcam\"\n\nfor product_id, name in recently_viewed.items():\n print(product_id, name)\n```\n\n\nSame output you'd get from a regular `dict` today. The difference becomes visible only when you reach for one of the order-aware methods.\n\n---\n\n# Creating an OrderedDict\n\nThe constructor takes the same kinds of inputs as `dict`: keyword arguments, an iterable of key-value pairs, or another mapping. The result is always a dictionary that records insertion order.\n\n\n```python\nfrom collections import OrderedDict\n\n# Empty, then add keys one at a time.\nviewed_a = OrderedDict()\nviewed_a[\"mouse\"] = \"Wireless Mouse\"\nviewed_a[\"cable\"] = \"USB Cable\"\n\n# From a list of pairs.\nviewed_b = OrderedDict([\n (\"mouse\", \"Wireless Mouse\"),\n (\"cable\", \"USB Cable\"),\n (\"webcam\", \"HD Webcam\"),\n])\n\n# From keyword arguments. Order matches the call order in Python 3.7+.\nviewed_c = OrderedDict(mouse=\"Wireless Mouse\", cable=\"USB Cable\")\n\nprint(viewed_a)\nprint(viewed_b)\nprint(viewed_c)\n```\n\n\nThe `repr` shows the keys as a list of pairs, which is one easy way to tell at a glance whether you're looking at an `OrderedDict` or a plain `dict` in a debugger.\n\nYou can iterate, look up, and assign keys exactly the way you would on a regular dict. Every standard dict operation works. What's new lives in two methods and one comparison rule.\n\n---\n\n# `move_to_end`: Shuffle a Key to Either End\n\n`move_to_end(key, last=True)` moves an existing key to the right end of the ordering (the most recently added position). With `last=False`, it moves the key to the left end (the oldest position).\n\n\n```python\nfrom collections import OrderedDict\n\ncart = OrderedDict()\ncart[\"mouse\"] = 2\ncart[\"cable\"] = 3\ncart[\"webcam\"] = 1\ncart[\"keyboard\"] = 1\n\n# Move \"cable\" to the right end (most recent).\ncart.move_to_end(\"cable\")\nprint(list(cart))\n\n# Move \"keyboard\" to the left end (oldest).\ncart.move_to_end(\"keyboard\", last=False)\nprint(list(cart))\n```\n\n\nThe key has to already exist. If it doesn't, you get a `KeyError`.\n\n\n```python\nfrom collections import OrderedDict\n\ncart = OrderedDict()\ncart[\"mouse\"] = 2\ncart.move_to_end(\"phantom\")\n```\n\n\nThis is the operation that makes `OrderedDict` useful for \"recency\" patterns: every time a user views a product, you can move that product to the end of the list so the most recent views sit at the right side and the stale ones drift to the left.\n\n\n> **INFO**\n>\n> **Cost:** `move_to_end` is O(1). `OrderedDict` maintains a doubly-linked list of entries internally, so moving an entry to either end is a constant-time pointer update, not a re-insertion.\n\n\n\n```python\nfrom collections import OrderedDict\n\n# Track the order in which a shopper views products.\nviewed = OrderedDict()\n\ndef view_product(product_id):\n if product_id in viewed:\n viewed.move_to_end(product_id)\n else:\n viewed[product_id] = True\n\nview_product(\"mouse\")\nview_product(\"cable\")\nview_product(\"webcam\")\nview_product(\"mouse\") # re-viewing pushes mouse to the end\nview_product(\"keyboard\")\n\nprint(list(viewed))\n```\n\n\nAfter this sequence, the left side holds the products the shopper saw earliest and hasn't returned to. The right side holds the products they touched most recently. That's the building block for a recently-viewed widget, a browsing history, or an LRU cache.\n\n---\n\n# `popitem`: LIFO or FIFO\n\nRegular dicts have `popitem`, but `OrderedDict.popitem(last=True)` adds a `last` flag. `last=True` (the default) removes and returns the rightmost pair, which is LIFO behavior. `last=False` removes the leftmost pair, which is FIFO.\n\n\n```python\nfrom collections import OrderedDict\n\ncart = OrderedDict()\ncart[\"mouse\"] = 2\ncart[\"cable\"] = 3\ncart[\"webcam\"] = 1\n\n# LIFO: remove the most recently added item.\nprint(cart.popitem())\nprint(list(cart))\n\n# Add some more, then FIFO: remove the oldest item.\ncart[\"keyboard\"] = 1\ncart[\"monitor\"] = 1\nprint(cart.popitem(last=False))\nprint(list(cart))\n```\n\n\nCompare this with regular `dict.popitem()`, which only supports LIFO (it removes the last-inserted pair) and has no `last` flag. If you need FIFO from a regular dict, you'd have to find the first key by iterating and then `del` it, which is more code and reads worse.\n\n\n```python\n# Regular dict: LIFO only.\nd = {\"mouse\": 2, \"cable\": 3, \"webcam\": 1}\nprint(d.popitem())\nprint(d)\n```\n\n\nThe `last=False` mode is what makes `OrderedDict` a clean fit for a FIFO queue when you also want key-based lookup. A plain `collections.deque` is faster if you only need ends, but a `deque` doesn't let you check membership or look up by key in constant time.\n\n\n> **INFO**\n>\n> **Cost:** Both `popitem(last=True)` and `popitem(last=False)` are O(1). The doubly-linked list lets `OrderedDict` reach either end without scanning.\n\n\nIf the `OrderedDict` is empty, `popitem` raises `KeyError`, same as on a regular dict.\n\n\n```python\nfrom collections import OrderedDict\n\nempty = OrderedDict()\nempty.popitem()\n```\n\n\n---\n\n# Order-Sensitive Equality\n\nThis is the one behavioral difference that catches people off guard. Two regular dicts are equal if they have the same keys mapped to the same values, regardless of insertion order. Two `OrderedDict` instances are equal only if the keys are also in the same order.\n\n\n```python\nfrom collections import OrderedDict\n\n# Regular dict: order-insensitive equality.\na = {\"mouse\": 1, \"cable\": 1, \"webcam\": 1}\nb = {\"webcam\": 1, \"mouse\": 1, \"cable\": 1}\nprint(a == b)\n\n# OrderedDict: order-sensitive equality.\noa = OrderedDict([(\"mouse\", 1), (\"cable\", 1), (\"webcam\", 1)])\nob = OrderedDict([(\"webcam\", 1), (\"mouse\", 1), (\"cable\", 1)])\nprint(oa == ob)\n```\n\n\nThat second `False` is the headline. The two `OrderedDict` values map the same keys to the same values, but the orders differ, so they don't compare equal.\n\nWhat about an `OrderedDict` compared against a regular `dict`? Python uses the regular-dict rules in that case: order is ignored, only keys and values matter.\n\n\n```python\nfrom collections import OrderedDict\n\noa = OrderedDict([(\"mouse\", 1), (\"cable\", 1), (\"webcam\", 1)])\nregular = {\"webcam\": 1, \"mouse\": 1, \"cable\": 1}\nprint(oa == regular)\nprint(regular == oa)\n```\n\n\nThe order-sensitive rule only applies when both sides are `OrderedDict`. When one side is a plain `dict`, the comparison falls back to the order-insensitive behavior. That's a deliberate compromise so `OrderedDict` and `dict` stay loosely interoperable.\n\nThis matters for cases where the sequence carries meaning, not just the keys. A few e-commerce examples:\n\n- **Recipe step order.** Two recipes with the same ingredients but a different cooking sequence are not the same recipe.\n- **Navigation breadcrumbs.** A trail of `Home > Electronics > Mice` is not the same as `Home > Mice > Electronics` (the second doesn't even make sense).\n- **Browsing history.** Two history lists with the same products in different orders represent different shopping journeys.\n\n\n```python\nfrom collections import OrderedDict\n\njourney_a = OrderedDict()\njourney_a[\"home\"] = \"Home\"\njourney_a[\"electronics\"] = \"Electronics\"\njourney_a[\"mice\"] = \"Wireless Mice\"\n\njourney_b = OrderedDict()\njourney_b[\"home\"] = \"Home\"\njourney_b[\"mice\"] = \"Wireless Mice\"\njourney_b[\"electronics\"] = \"Electronics\"\n\nprint(journey_a == journey_b)\n```\n\n\nIf you wrote this with a plain dict, the two journeys would compare equal and the bug would be invisible. With `OrderedDict`, the equality check captures what you actually meant.\n\n---\n\n# Reverse Iteration: Same as Regular Dict\n\nReverse iteration over a dict works in both `OrderedDict` and regular `dict` since Python 3.8.\n\n\n```python\nfrom collections import OrderedDict\n\nrecent = OrderedDict()\nrecent[\"mouse\"] = \"Wireless Mouse\"\nrecent[\"cable\"] = \"USB Cable\"\nrecent[\"webcam\"] = \"HD Webcam\"\n\n# Forward iteration.\nfor key in recent:\n print(key)\n\n# Reverse iteration.\nfor key in reversed(recent):\n print(key)\n```\n\n\nThis works the same on a plain dict in Python 3.8+. Earlier versions of Python required an `OrderedDict` for `reversed()` to be defined on the mapping at all. In modern Python, there's parity on this specific operation. If you only need reverse iteration, you don't need `OrderedDict`.\n\n---\n\n# A Sketch of an LRU Cache\n\nThe classic use case for `OrderedDict` is building an LRU (least recently used) cache from scratch. The idea is simple:\n\n- On every access, move the key to the end (most recently used).\n- When the cache is full and you need to insert, pop from the left (least recently used) to make room.\n\nBoth operations are O(1) on `OrderedDict`, which is exactly what you need.\n\n\n```python\nfrom collections import OrderedDict\n\nclass LRUCache:\n def __init__(self, capacity):\n self.capacity = capacity\n self.data = OrderedDict()\n\n def get(self, key):\n if key not in self.data:\n return None\n self.data.move_to_end(key)\n return self.data[key]\n\n def put(self, key, value):\n if key in self.data:\n self.data.move_to_end(key)\n elif len(self.data) >= self.capacity:\n self.data.popitem(last=False)\n self.data[key] = value\n\n# Cache of recently viewed product pages, capped at 3.\ncache = LRUCache(capacity=3)\ncache.put(\"mouse\", \"Wireless Mouse\")\ncache.put(\"cable\", \"USB Cable\")\ncache.put(\"webcam\", \"HD Webcam\")\n\ncache.get(\"mouse\") # mouse is now the most recently used\n\ncache.put(\"keyboard\", \"Mechanical Keyboard\") # this evicts the LRU entry\n\nprint(list(cache.data.keys()))\n```\n\n\n`cable` got evicted because it was the oldest untouched entry when `keyboard` came in. `mouse` survived because `cache.get(\"mouse\")` bumped it to the end before the eviction.\n\nHere's what happens internally on each step:\n\n\n```mermaid\nflowchart LR\n S0[\"[]
empty\"]:::teal\n S1[\"[mouse]\"]:::cyan\n S2[\"[mouse, cable]\"]:::cyan\n S3[\"[mouse, cable, webcam]\"]:::cyan\n S4[\"[cable, webcam, mouse]
get('mouse')\"]:::orange\n S5[\"[webcam, mouse, keyboard]
evict cable\"]:::green\n\n S0 -->|\"put mouse\"| S1\n S1 -->|\"put cable\"| S2\n S2 -->|\"put webcam\"| S3\n S3 -->|\"get mouse
move_to_end\"| S4\n S4 -->|\"put keyboard
popitem(last=False)\"| S5\n\n classDef cyan fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n```\n\n\nThe left side of each box is the least recently used, the right side is the most recently used. Every `get` moves the touched key to the right. Once capacity is exceeded, an insert pops the leftmost key and pushes the new one on the right.\n\nIn real code you'd reach for `functools.lru_cache` if you wanted to memoize function results, since it's a decorator and handles thread safety, statistics, and corner cases for you. The `OrderedDict` sketch above is the right tool when you need to manage a cache as data, not as a decorator: storing recently viewed products per user, capping a session's worth of search results, or limiting the size of a \"what you looked at\" widget that a frontend reads.\n\n---\n\n# A FIFO Queue With Key Lookup\n\n`OrderedDict` is a sensible choice when you want a queue (FIFO) that also lets you check or remove items by key. A plain list gives you indexed access but O(n) membership checks. A `deque` gives you O(1) ends but no key lookup. An `OrderedDict` gives you both, at a small memory cost.\n\n\n```python\nfrom collections import OrderedDict\n\n# Pending orders waiting to be processed. Each order ID maps to customer info.\npending = OrderedDict()\n\npending[\"ORD-1001\"] = {\"customer\": \"Alice\", \"total\": 49.99}\npending[\"ORD-1002\"] = {\"customer\": \"Bob\", \"total\": 19.99}\npending[\"ORD-1003\"] = {\"customer\": \"Carol\", \"total\": 89.50}\n\n# Process the oldest pending order.\norder_id, info = pending.popitem(last=False)\nprint(\"Processing\", order_id, info)\n\n# A customer cancels their pending order before it's processed.\ndel pending[\"ORD-1003\"]\n\nprint(\"Still pending:\", list(pending))\n```\n\n\n`popitem(last=False)` pulls the next order in FIFO order. `del pending[\"ORD-1003\"]` removes a specific order in O(1) thanks to the dict-style lookup. You couldn't do that cleanly with a `deque`.\n\nA real production queue would use a database or a managed queue service for durability and concurrency. For an in-memory short-lived queue (a batch waiting to be flushed, a small per-session worklist), `OrderedDict` covers a lot of ground.\n\n---\n\n# `dict` vs `OrderedDict` in Modern Python\n\nA side-by-side view of what the two types share and where they differ:\n\n\n| Capability | `dict` (3.7+) | `OrderedDict` |\n| --------------------------------------- | ------------------------ | ---------------------------- |\n| Preserves insertion order | Yes | Yes |\n| `popitem()` removes last (LIFO) | Yes | Yes (default) |\n| `popitem(last=False)` removes first | No (`TypeError`) | Yes (FIFO) |\n| `move_to_end(key, last=True/False)` | No (`AttributeError`) | Yes |\n| Reverse iteration with `reversed()` | Yes (3.8+) | Yes |\n| Equality compares order | No (order ignored) | Yes (when both sides are OD) |\n| Equality with a regular `dict` | Order ignored | Order ignored (mixed compare)|\n| Memory overhead | Lower | Higher (linked-list bookkeeping) |\n| Speed of basic ops (`get`, `set`, `in`) | Slightly faster | Slightly slower |\n| `__repr__` shows order in pair list | No (looks like `{...}`) | Yes (`OrderedDict([...])`) |\n\n\nThe two types overlap on order preservation and reverse iteration. They diverge on the order-aware operations and on equality semantics.\n\n\n> **INFO**\n>\n> **Cost:** `OrderedDict` carries a doubly-linked list alongside the hash table to track insertion order explicitly. That's more memory than a plain dict and slightly slower hot-path operations. For a few thousand entries it's not noticeable. If you're storing millions of entries and don't need the extra methods, stick with a plain dict.\n\n\nWhen should you reach for `OrderedDict` in modern Python? The honest answer is \"rarely, but specifically.\" If your code uses `move_to_end`, `popitem(last=False)`, or relies on order-sensitive equality, `OrderedDict` is the right tool. If it doesn't, a plain dict is simpler and faster.\n\n\n```python\nfrom collections import OrderedDict\n\n# These methods only exist on OrderedDict.\nd = {\"a\": 1, \"b\": 2}\ntry:\n d.move_to_end(\"a\")\nexcept AttributeError as e:\n print(\"dict.move_to_end:\", e)\n\ntry:\n d.popitem(last=False)\nexcept TypeError as e:\n print(\"dict.popitem(last=False):\", e)\n```\n\n\nThese two errors are the litmus test. If your code needs to do either of these, switch from `dict` to `OrderedDict`. Otherwise, you're paying for features you don't use.\n\n---\n\n# Memory and Performance Note\n\nThe exact overhead has shrunk over Python versions (the linked-list bookkeeping is more compact than it used to be), but `OrderedDict` is still measurably larger and slightly slower than `dict` for the same data. You can see the size difference yourself:\n\n\n```python\nimport sys\nfrom collections import OrderedDict\n\nregular = dict.fromkeys([\"a\", \"b\", \"c\", \"d\", \"e\"], 1)\nordered = OrderedDict.fromkeys([\"a\", \"b\", \"c\", \"d\", \"e\"], 1)\n\nprint(sys.getsizeof(regular))\nprint(sys.getsizeof(ordered))\n```\n\n\nThe OrderedDict is roughly 50% larger here because of the extra per-entry pointers it maintains. For five entries the gap is meaningless, but the ratio is similar at scale. If you're storing recently-viewed items for a single user (a few dozen entries), this never matters. If you're storing one of these per row in a million-row table, it adds up.\n\nIn practice the decision rarely comes down to memory. It comes down to whether you need the order-aware methods. If you do, the overhead is the price of admission. If you don't, you don't pay it.\n\n---\n\n# When to Reach for OrderedDict\n\nA decision flow for choosing between `dict`, `OrderedDict`, and `deque`:\n\n\n```mermaid\nflowchart TD\n Q1{\"Do I need
move_to_end
or popitem(last=False)?\"}:::cyan\n Q2{\"Do I need
O(1) lookup
by key?\"}:::cyan\n Q3{\"Does order matter
for equality?\"}:::cyan\n\n OD[\"OrderedDict\"]:::green\n PD[\"plain dict\"]:::teal\n DQ[\"collections.deque\"]:::orange\n\n Q1 -->|\"yes\"| OD\n Q1 -->|\"no\"| Q3\n Q3 -->|\"yes\"| OD\n Q3 -->|\"no\"| Q2\n Q2 -->|\"yes\"| PD\n Q2 -->|\"no\"| DQ\n\n classDef cyan fill:#00ceff,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n```\n\n\nThe three branches map to three patterns:\n\n- **`OrderedDict`** when you're doing LRU-style recency management, FIFO with key lookup, or comparing sequences by order.\n- **`dict`** when you want fast key-value lookup and you don't care about order operations beyond insertion-order iteration.\n- **`deque`** when you only need ends (push/pop from front or back) and don't need to look up by key.\n\nDon't overuse `OrderedDict` out of habit. In a modern codebase, the default container for key-value data is `dict`, and `OrderedDict` is a specific tool you pick when the problem actually calls for one of its order-aware features.","pageType":"python"}

OrderedDict

Get Premium