Are there any reasons not to use an OrderedDict?

by

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.

More Related Contents:

  1. Accessing items in an collections.OrderedDict by index
  2. Creating an Ordered Counter
  3. How to get count dict of items but maintain the order in which they appear?
  4. How to select random key with common values?
  5. How to remove [ ] and ” from Python output [duplicate]
  6. Are dictionaries ordered in Python 3.6+?
  7. count the number of occurrences of a certain value in a dictionary in python?
  8. TypeError: ‘dict_keys’ object does not support indexing
  9. Accessing dict_keys element by index in Python3
  10. What is the purpose of collections.ChainMap?
  11. One liner: creating a dictionary from list with indices as keys
  12. Accessing dictionary items by position in Python 3.6+ efficiently
  13. Override the {…} notation so i get an OrderedDict() instead of a dict()?
  14. Unpack dictionary from Pandas Column
  15. Updating a dictionary in python
  16. Why is a class __dict__ a mappingproxy?
  17. Extract a subset of key-value pairs from dictionary?
  18. Will OrderedDict become redundant in Python 3.7?
  19. How to create a Python dictionary with double quotes as default quote format?
  20. How do I return dictionary keys as a list in Python?
  21. How to reverse a dictionary (whose values are lists) in Python? [duplicate]
  22. Changing one dict changes all dicts in a list of dicts [duplicate]
  23. Python dictionary replace values
  24. enumerate() for dictionary in Python
  25. Appending to list in Python dictionary [duplicate]
  26. Python – How to convert only numbers in a mixed list into float?
  27. How to change all the dictionary keys in a for loop with d.items()?
  28. How to convert string representation of dictionary in Pandas DataFrame to a new columns?
  29. How to convert only numbers in a mixed list into float
  30. How to add an element to the beginning of an OrderedDict?

Leave a Comment