Are there any reasons not to use an OrderedDict?

python dictionary python-3.x ordereddictionary
temporary_user_name picture temporary_user_name · Sep 23, 2013 · Viewed 11.5k times · Source

I'm referring to the OrderedDict from the collections module, which is an ordered dictionary.

If it has the added functionality of being orderable, which I realize may often not be necessary but even so, are there any downsides? Is it slower? Is it missing any functionality? I didn't see any missing methods.

In short, why shouldn't I always use this instead of a normal dictionary?

Answer

Tim Peters picture Tim Peters · Sep 23, 2013

OrderedDict is a subclass of dict, and needs more memory to keep track of the order in which keys are added. This isn't trivial. The implementation adds a second dict under the covers, and a doubly-linked list of all the keys (that's the part that remembers the order), and a bunch of weakref proxies. It's not a lot slower, but at least doubles the memory over using a plain dict.

But if it's appropriate, use it! That's why it's there :-)

How it works

The base dict is just an ordinary dict mapping keys to values - it's not "ordered" at all. When a <key, value> pair is added, the key is appended to a list. The list is the part that remembers the order.

But if this were a Python list, deleting a key would take O(n) time twice over: O(n) time to find the key in the list, and O(n) time to remove the key from the list.

So it's a doubly-linked list instead. That makes deleting a key constant (O(1)) time. But we still need to find the doubly-linked list node belonging to the key. To make that operation O(1) time too, a second - hidden - dict maps keys to nodes in the doubly-linked list.

So adding a new <key, value> pair requires adding the pair to the base dict, creating a new doubly-linked list node to hold the key, appending that new node to the doubly-linked list, and mapping the key to that new node in the hidden dict. A bit over twice as much work, but still O(1) (expected case) time overall.

Similarly, deleting a key that's present is also a bit over twice as much work but O(1) expected time overall: use the hidden dict to find the key's doubly-linked list node, delete that node from the list, and remove the key from both dicts.

Etc. It's quite efficient.

Related questions

Accessing items in an collections.OrderedDict by index

Lets say I have the following code: import collections d = collections.OrderedDict() d['foo'] = 'python' d['bar'] = 'spam' Is there a way I can access the items in a numbered manner, like: d(0) #foo's Output d(1) #bar's Output

Read More
Difference between dictionary and OrderedDict

I am trying to get a sorted dictionary. But the order of the items between mydict and orddict doesn't seem to change. from collections import OrderedDict mydict = {'a': 1, 'b': 2, 'c': 3, 'd': 4} orddict = OrderedDict(mydict) print(mydict, orddict) # print items in …

Read More
Creating an Ordered Counter

I've been reading into how super() works. I came across this recipe that demonstrates how to create an Ordered Counter: from collections import Counter, OrderedDict class OrderedCounter(Counter, OrderedDict): 'Counter that remembers the order elements are first seen' def __repr__(…

Read More