OrderedDict vs dict in Python: The Right Tool for the Job

Choosing Between OrderedDict and dict

For years, Python dictionaries were unordered data structures. Python developers were used to this fact, and they relied on lists or other sequences when they needed to keep their data in order. With time, developers found a need for a new type of dictionary, one that would keep its items ordered.

Back in 2008, PEP 372 introduced the idea of adding a new dictionary class to collections. Its main goal was to remember the order of items as defined by the order in which keys were inserted. That was the origin of OrderedDict.

Core Python developers wanted to fill in the gap and provide a dictionary that could preserve the order of inserted keys. That, in turn, allowed for a more straightforward implementation of specific algorithms that rely on this property.

OrderedDict was added to the standard library in Python 3.1. Its API is essentially the same as dict. However, OrderedDict iterates over keys and values in the same order that the keys were inserted. If a new entry overwrites an existing entry, then the order of items is left unchanged. If an entry is deleted and reinserted, then it will be moved to the end of the dictionary.

Python 3.6 introduced a new implementation of dict. This new implementation represents a big win in terms of memory usage and iteration efficiency. Additionally, the new implementation provides a new and somewhat unexpected feature: dict objects now keep their items in the same order they were introduced. Initially, this feature was considered an implementation detail, and the documentation advised against relying on it.

In the words of Raymond Hettinger, core Python developer and coauthor of OrderedDict, the class was specially designed to keep its items ordered, whereas the new implementation of dict was designed to be compact and to provide fast iteration:

The current regular dictionary is based on the design I proposed several years ago. The primary goals of that design were compactness and faster iteration over the dense arrays of keys and values. Maintaining order was an artifact rather than a design goal. The design can maintain order but that is not its specialty.

In contrast, I gave collections.OrderedDict a different design (later coded in C by Eric Snow). The primary goal was to have efficient maintenance of order even for severe workloads such as that imposed by the lru_cache which frequently alters order without touching the underlying dict. Intentionally, the OrderedDict has a design that prioritizes ordering capabilities at the expense of additional memory overhead and a constant factor worse insertion time.

It is still my goal to have collections.OrderedDict have a different design with different performance characteristics than regular dicts. It has some order specific methods that regular dicts don’t have (such as a move_to_end() and a popitem() that pops efficiently from either end). The OrderedDict needs to be good at those operations because that is what differentiates it from regular dicts. (Source)

In Python 3.7, the items-ordered feature of dict objects was declared an official part of the Python language specification. So, from that point on, developers could rely on dict when they needed a dictionary that keeps its items ordered.

At this point, a question arises: Is OrderedDict still needed after this new implementation of dict? The answer depends on your specific use case and also on how explicit you want to be in your code.

At the time of writing, some features of OrderedDict still made it valuable and different from a regular dict:

1. Intent signaling: If you use OrderedDict over dict, then your code makes it clear that the order of items in the dictionary is important. You’re clearly communicating that your code needs or relies on the order of items in the underlying dictionary.
2. Control over the order of items: If you need to rearrange or reorder the items in a dictionary, then you can use .move_to_end() and also the enhanced variation of .popitem().
3. Equality test behavior: If your code compares dictionaries for equality, and the order of items is important in that comparison, then OrderedDict is the right choice.

There’s at least one more reason to continue using OrderedDict in your code: backward compatibility. Relying on regular dict objects to preserve the order of items will break your code in environments that run versions of Python older than 3.6.

It’s difficult to say if dict will fully replace OrderedDict soon. Nowadays, OrderedDict still offers interesting and valuable features that you might want to consider when selecting a tool for a given job.

Getting Started With Python’s OrderedDict

Python’s OrderedDict is a dict subclass that preserves the order in which key-value pairs, commonly known as items, are inserted into the dictionary. When you iterate over an OrderedDict object, items are traversed in the original order. If you update the value of an existing key, then the order remains unchanged. If you remove an item and reinsert it, then the item is added at the end of the dictionary.

Being a dict subclass means that it inherits all the methods a regular dictionary provides. OrderedDict also has additional features that you’ll learn about in this tutorial. In this section, however, you’ll learn the basics of creating and using OrderedDict objects in your code.

>>> from collections import OrderedDict

>>> numbers = OrderedDict()

>>> numbers["one"] = 1
>>> numbers["two"] = 2
>>> numbers["three"] = 3

>>> numbers
OrderedDict([('one', 1), ('two', 2), ('three', 3)])

>>> from collections import OrderedDict

>>> numbers = OrderedDict([("one", 1), ("two", 2), ("three", 3)])
>>> numbers
OrderedDict([('one', 1), ('two', 2), ('three', 3)])

>>> letters = OrderedDict({("a", 1), ("b", 2), ("c", 3)})
>>> letters
OrderedDict([('c', 3), ('a', 1), ('b', 2)])

Python 3.9.0 (default, Oct  5 2020, 17:52:02)
[GCC 9.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> from collections import OrderedDict

>>> numbers = OrderedDict({"one": 1, "two": 2, "three": 3})
>>> numbers
OrderedDict([('one', 1), ('two', 2), ('three', 3)])

Python 3.5.10 (default, Jan 25 2021, 13:22:52)
[GCC 9.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> from collections import OrderedDict

>>> numbers = OrderedDict({"one": 1, "two": 2, "three": 3})
>>> numbers
OrderedDict([('one', 1), ('three', 3), ('two', 2)])

>>> from collections import OrderedDict

>>> numbers = OrderedDict(one=1, two=2, three=3)
>>> numbers
OrderedDict([('one', 1), ('two', 2), ('three', 3)])

>>> from collections import OrderedDict

>>> keys = ["one", "two", "three"]
>>> OrderedDict.fromkeys(keys, 0)
OrderedDict([('one', 0), ('two', 0), ('three', 0)])

>>> from collections import OrderedDict

>>> numbers = OrderedDict(one=1, two=2, three=3)
>>> numbers
OrderedDict([('one', 1), ('two', 2), ('three', 3)])

>>> numbers["four"] = 4
>>> numbers
OrderedDict([('one', 1), ('two', 2), ('three', 3), ('four', 4)])

>>> from collections import OrderedDict
>>> numbers = OrderedDict(one=1, two=2, three=3)

>>> del numbers["one"]
>>> numbers
OrderedDict([('two', 2), ('three', 3)])

>>> numbers["one"] = 1
>>> numbers
OrderedDict([('two', 2), ('three', 3), ('one', 1)])

>>> from collections import OrderedDict
>>> numbers = OrderedDict(one=1, two=2, three=3)

>>> numbers["one"] = 1.0
>>> numbers
OrderedDict([('one', 1.0), ('two', 2), ('three', 3)])

>>> numbers.update(two=2.0)
>>> numbers
OrderedDict([('one', 1.0), ('two', 2.0), ('three', 3)])

>>> from collections import OrderedDict
>>> numbers = OrderedDict(one=1, two=2, three=3)

>>> # Iterate over the keys directly
>>> for key in numbers:
...     print(key, "->", numbers[key])
...
one -> 1
two -> 2
three -> 3

>>> # Iterate over the items using .items()
>>> for key, value in numbers.items():
...     print(key, "->", value)
...
one -> 1
two -> 2
three -> 3

>>> # Iterate over the keys using .keys()
>>> for key in numbers.keys():
...     print(key, "->", numbers[key])
...
one -> 1
two -> 2
three -> 3

>>> # Iterate over the values using .values()
>>> for value in numbers.values():
...     print(value)
...
1
2
3

>>> from collections import OrderedDict
>>> numbers = OrderedDict(one=1, two=2, three=3)

>>> # Iterate over the keys directly in reverse order
>>> for key in reversed(numbers):
...     print(key, "->", numbers[key])
...
three -> 3
two -> 2
one -> 1

>>> # Iterate over the items in reverse order
>>> for key, value in reversed(numbers.items()):
...     print(key, "->", value)
...
three -> 3
two -> 2
one -> 1

>>> # Iterate over the keys in reverse order
>>> for key in reversed(numbers.keys()):
...     print(key, "->", numbers[key])
...
three -> 3
two -> 2
one -> 1

>>> # Iterate over the values in reverse order
>>> for value in reversed(numbers.values()):
...     print(value)
...
3
2
1

Python 3.7.9 (default, Jan 14 2021, 11:41:20)
[GCC 9.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> numbers = dict(one=1, two=2, three=3)

>>> for key in reversed(numbers):
...     print(key)
...
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'dict' object is not reversible

Exploring Unique Features of Python’s OrderedDict

Since Python 3.6, regular dictionaries have kept their items in the same order that they were inserted into the underlying dictionary. This limits the usefulness of OrderedDict, as you’ve seen so far. However, OrderedDict provides some unique features that you can’t find in a regular dict object.

With an ordered dictionary, you have access to the following extra and enhanced methods:

• .move_to_end() is a new method added in Python 3.2 that allows you to move an existing item either to the end or to the beginning of the dictionary.

• .popitem() is an enhanced variation of its dict.popitem() counterpart that allows you to remove and return an item from either the end or the beginning of the underlying ordered dictionary.

OrderedDict and dict also behave differently when they’re tested for equality. Specifically, when you compare ordered dictionaries, the order of items matters. That’s not the case with regular dictionaries.

Finally, OrderedDict instances provide an attribute called .__dict__ that you can’t find in a regular dictionary instance. This attribute allows you to add custom writable attributes to an existing ordered dictionary.

>>> from collections import OrderedDict
>>> numbers = OrderedDict(one=1, two=2, three=3)
>>> numbers
OrderedDict([('one', 1), ('two', 2), ('three', 3)])

>>> numbers.move_to_end("one")
>>> numbers
OrderedDict([('two', 2), ('three', 3), ('one', 1)])

>>> numbers.move_to_end("one", last=False)
>>> numbers
OrderedDict([('one', 1), ('two', 2), ('three', 3)])

>>> from collections import OrderedDict
>>> letters = OrderedDict(b=2, d=4, a=1, c=3)

>>> for key in sorted(letters):
...     letters.move_to_end(key)
...
>>> letters
OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 4)])

>>> from collections import OrderedDict
>>> letters = OrderedDict(a=4, b=3, d=1, c=2)

>>> for key, _ in sorted(letters.items(), key=lambda item: item[1]):
...     letters.move_to_end(key)
...
>>> letters
OrderedDict([('d', 1), ('c', 2), ('b', 3), ('a', 4)])

>>> from collections import OrderedDict
>>> numbers = OrderedDict(one=1, two=2, three=3)

>>> numbers.popitem()
('three', 3)
>>> numbers.popitem()
('two', 2)
>>> numbers.popitem()
('one', 1)
>>> numbers.popitem()
Traceback (most recent call last):
  File "<input>", line 1, in <module>
    numbers.popitem()
KeyError: 'dictionary is empty'

>>> from collections import OrderedDict
>>> numbers = OrderedDict(one=1, two=2, three=3)

>>> numbers.popitem(last=False)
('one', 1)
>>> numbers.popitem(last=False)
('two', 2)
>>> numbers.popitem(last=False)
('three', 3)
>>> numbers.popitem(last=False)
Traceback (most recent call last):
  File "<input>", line 1, in <module>
    numbers.popitem(last=False)
KeyError: 'dictionary is empty'

>>> from collections import OrderedDict
>>> letters_0 = OrderedDict(a=1, b=2, c=3, d=4)
>>> letters_1 = OrderedDict(b=2, a=1, c=3, d=4)
>>> letters_2 = OrderedDict(a=1, b=2, c=3, d=4)

>>> letters_0 == letters_1
False

>>> letters_0 == letters_2
True

>>> letters_0 = dict(a=1, b=2, c=3, d=4)
>>> letters_1 = dict(b=2, a=1, c=3, d=4)
>>> letters_2 = dict(a=1, b=2, c=3, d=4)

>>> letters_0 == letters_1
True

>>> letters_0 == letters_2
True

>>> letters_0 == letters_1 == letters_2
True

>>> from collections import OrderedDict
>>> letters_0 = OrderedDict(a=1, b=2, c=3, d=4)
>>> letters_1 = dict(b=2, a=1, c=3, d=4)

>>> letters_0 == letters_1
True

>>> from collections import OrderedDict
>>> letters = OrderedDict(b=2, d=4, a=1, c=3)
>>> letters.__dict__
{}

>>> letters1 = dict(b=2, d=4, a=1, c=3)
>>> letters1.__dict__
Traceback (most recent call last):
  File "<input>", line 1, in <module>
    letters1.__dict__
AttributeError: 'dict' object has no attribute '__dict__'

>>> from collections import OrderedDict
>>> letters = OrderedDict(b=2, d=4, a=1, c=3)

>>> letters.sorted_keys = lambda: sorted(letters.keys())
>>> vars(letters)
{'sorted_keys': <function <lambda> at 0x7fa1e2fe9160>}

>>> letters.sorted_keys()
['a', 'b', 'c', 'd']

>>> letters["e"] = 5
>>> letters.sorted_keys()
['a', 'b', 'c', 'd', 'e']

>>> for key in letters.sorted_keys():
...     print(key, "->", letters[key])
...
a -> 1
b -> 2
c -> 3
d -> 4
e -> 5

>>> letters
OrderedDict([('b', 2), ('d', 4), ('a', 1), ('c', 3), ('e', 5)])

>>> letters = dict(b=2, d=4, a=1, c=3)
>>> letters.sorted_keys = lambda: sorted(letters.keys())
Traceback (most recent call last):
  File "<input>", line 1, in <module>
    letters.sorted_keys = lambda: sorted(letters.keys())
AttributeError: 'dict' object has no attribute 'sorted_keys'

Merging and Updating Dictionaries With Operators

Python 3.9 added two new operators to the dictionary space. Now you have merge (|) and update (|=) dictionary operators. These operators also work with OrderedDict instances:

Python 3.9.0 (default, Oct  5 2020, 17:52:02)
[GCC 9.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> from collections import OrderedDict

>>> physicists = OrderedDict(newton="1642-1726", einstein="1879-1955")
>>> biologists = OrderedDict(darwin="1809-1882", mendel="1822-1884")

>>> scientists = physicists | biologists
>>> scientists
OrderedDict([
   ('newton', '1642-1726'),
   ('einstein', '1879-1955'),
   ('darwin', '1809-1882'),
   ('mendel', '1822-1884')
])

As its name suggests, the merge operator merges the two dictionaries into a new one that contains the items of both initial dictionaries. If the dictionaries in the expression have common keys, then the rightmost dictionary’s values will prevail.

The update operator is handy when you have a dictionary and want to update some of its values without calling .update():

>>> physicists = OrderedDict(newton="1642-1726", einstein="1879-1955")

>>> physicists_1 = OrderedDict(newton="1642-1726/1727", hawking="1942-2018")
>>> physicists |= physicists_1
>>> physicists
OrderedDict([
    ('newton', '1642-1726/1727'),
    ('einstein', '1879-1955'),
    ('hawking', '1942-2018')
])

In this example, you use the dictionary update operator to update Newton’s lifetime information. The operator updates a dictionary in place. If the dictionary that provides the updated data has new keys, then those keys are added to the end of the original dictionary.

Considering Performance

Performance is an important subject in programming. Knowing how fast an algorithm runs or how much memory it uses are common concerns. OrderedDict was initially coded in Python and then written in C to maximize efficiency in its methods and operations. These two implementations are currently available in the standard library. However, the Python implementation serves as an alternative if the C implementation isn’t available for some reason.

Both implementations of OrderedDict involve using a doubly linked list to capture the order of items. Despite having linear time for some operations, the linked list implementation in OrderedDict is highly optimized to preserve the fast times of the corresponding dictionary methods. That said, the operations on an ordered dictionary are O(1) but with a greater constant factor compared to regular dictionaries.

In general, OrderedDict has lower performance than regular dictionaries. Here’s an example that measures the execution time of several operations on both dictionary classes:

# time_testing.py

from collections import OrderedDict
from time import perf_counter

def average_time(dictionary):
    time_measurements = []
    for _ in range(1_000_000):
        start = perf_counter()
        dictionary["key"] = "value"
        "key" in dictionary
        "missing_key" in dictionary
        dictionary["key"]
        del dictionary["key"]
        end = perf_counter()
        time_measurements.append(end - start)
    return sum(time_measurements) / len(time_measurements) * int(1e9)

ordereddict_time = average_time(OrderedDict.fromkeys(range(1000)))
dict_time = average_time(dict.fromkeys(range(1000)))
gain = ordereddict_time / dict_time

print(f"OrderedDict: {ordereddict_time:.2f} ns")
print(f"dict:        {dict_time:.2f} ns ({gain:.2f}x faster)")

In this script, you compute the average_time() that it takes to run several common operations on a given dictionary. The for loop uses time.perf_counter() to measure the execution time of the set of operations. The function returns the average time, in nanoseconds, that it takes to run the selected set of operations.

If you run this script from your command line, then you get an output similar to this:

$ python time_testing.py
OrderedDict: 272.93 ns
dict:        197.88 ns (1.38x faster)

As you see in the output, operations on dict objects are faster than operations on OrderedDict objects.

Regarding memory consumption, OrderedDict instances have to pay a storage cost because of their ordered list of keys. Here’s a script that gives you an idea of this memory cost:

>>> import sys
>>> from collections import OrderedDict

>>> ordereddict_memory = sys.getsizeof(OrderedDict.fromkeys(range(1000)))
>>> dict_memory = sys.getsizeof(dict.fromkeys(range(1000)))
>>> gain = 100 - dict_memory / ordereddict_memory * 100

>>> print(f"OrderedDict: {ordereddict_memory} bytes")
OrderedDict: 85408 bytes

>>> print(f"dict:        {dict_memory} bytes ({gain:.2f}% lower)")
dict:        36960 bytes (56.73% lower)

In this example, you use sys.getsizeof() to measure the memory footprint in bytes of two dictionary objects. In the output, you can see that the regular dictionary occupies less memory than its OrderedDict counterpart.

Selecting the Right Dictionary for the Job

So far, you’ve learned about the subtle differences between OrderedDict and dict. You’ve learned that, even though regular dictionaries have been ordered data structures since Python 3.6, there’s still some value in using OrderedDict because of a set of useful features that aren’t present in dict.

Here’s a summary of the more relevant differences and features of both classes that you should consider when you’re deciding which one to use:

This table summarizes some of the main differences between OrderedDict and dict that you should consider when you need to choose a dictionary class to solve a problem or to implement a specific algorithm. In general, if the order of items in the dictionary is vital or even important for your code to work correctly, then your first look should be toward OrderedDict.

Building a Dictionary-Based Queue

A use case in which you should consider using an OrderedDict object rather than a dict object is when you need to implement a dictionary-based queue. Queues are common and useful data structures that manage their items in a FIFO manner. This means that you push in new items at the end of the queue, and old items pop out from the beginning of the queue.

Typically, queues implement an operation to add an item to their end, which is known as an enqueue operation. Queues also implement an operation to remove items from their beginning, which is known as a dequeue operation.

To create a dictionary-based queue, fire up your code editor or IDE, create a new Python module called queue.py and add the following code to it:

# queue.py

from collections import OrderedDict

class Queue:
    def __init__(self, initial_data=None, /, **kwargs):
        self.data = OrderedDict()
        if initial_data is not None:
            self.data.update(initial_data)
        if kwargs:
            self.data.update(kwargs)

    def enqueue(self, item):
        key, value = item
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value

    def dequeue(self):
        try:
            return self.data.popitem(last=False)
        except KeyError:
            print("Empty queue")

    def __len__(self):
        return len(self.data)

    def __repr__(self):
        return f"Queue({self.data.items()})"

In Queue, you first initialize an instance attribute called .data. This attribute holds an empty ordered dictionary that you’ll use to store the data. The class initializer takes a first optional argument, initial_data, that allows you to provide initial data when you instantiate the class. The initializer also takes optional keyword arguments (kwargs) to allow you to use keyword arguments in the constructor.

Then you code .enqueue(), which allows you to add key-value pairs to the queue. In this case, you use .move_to_end() if the key already exists, and you use a normal assignment for new keys. Note that for this method to work, you need to provide a two-item tuple or list with a valid key-value pair.

The .dequeue() implementation uses .popitem() with last set to False to remove and return items from the beginning of the underlying ordered dictionary, .data. In this case, you use a try … except block to handle the KeyError that occurs when you call .popitem() on an empty dictionary.

A special method, .__len__(), provides the required functionality for retrieving the length of the internal ordered dictionary, .data. Finally, the special method .__repr__() provides a user-friendly string representation of the queue when you print the data structure to the screen.

Here are some examples of how you can use Queue:

>>> from queue import Queue

>>> # Create an empty queue
>>> empty_queue = Queue()
>>> empty_queue
Queue(odict_items([]))

>>> # Create a queue with initial data
>>> numbers_queue = Queue([("one", 1), ("two", 2)])
>>> numbers_queue
Queue(odict_items([('one', 1), ('two', 2)]))

>>> # Create a queue with keyword arguments
>>> letters_queue = Queue(a=1, b=2, c=3)
>>> letters_queue
Queue(odict_items([('a', 1), ('b', 2), ('c', 3)]))

>>> # Add items
>>> numbers_queue.enqueue(("three", 3))
>>> numbers_queue
Queue(odict_items([('one', 1), ('two', 2), ('three', 3)]))

>>> # Remove items
>>> numbers_queue.dequeue()
('one', 1)
>>> numbers_queue.dequeue()
('two', 2)
>>> numbers_queue.dequeue()
('three', 3)
>>> numbers_queue.dequeue()
Empty queue

In this code example, you first create three different Queue objects using different approaches. Then you use .enqueue() to add a single item to the end of numbers_queue. Finally, you call .dequeue() several times to remove all the items in numbers_queue. Note that the final call to .dequeue() prints a message to the screen to inform you that the queue is already empty.

Conclusion

For years, Python dictionaries were unordered data structures. This revealed the need for an ordered dictionary that helps in situations where the order of items is important. So Python developers created OrderedDict, which was specially designed to keep its items ordered.

Python 3.6 introduced a new feature into regular dictionaries. Now they also remember the order of items. With this addition, most Python programmers wonder if they still need to consider using OrderedDict.

In this tutorial, you learned:

• How to create and use OrderedDict objects in your code
• What the main differences are between OrderedDict and dict
• What the pros and cons are of using OrderedDict vs dict

Now you’re in a better position to make an educated decision on whether to use dict or OrderedDict if your code needs an ordered dictionary.

In this tutorial, you coded an example of how to implement a dictionary-based queue, which is a use case that shows that OrderedDict can still be of value in your daily Python coding adventures.