Posted in13.Python Collections

OrderedDict – Collections in Python

An OrderedDict in Python is a dictionary class from the collections module. It is a subclass of the dict class. This is used to maintain the order of key-value pairs, in which keys are inserted to this dictionary.

Before Python 3.7 version – OrderedDict was more useful before Python 3.7 version. Before Python 3.7 version, regular Python dictionaries (dict) were unordered collection, which does not maintain the order of keys in which they were inserted.

After Python 3.7 version – From Python 3.7 version, normal dictionary (dict) start supporting (maintaining) the insertion order of key-value pairs. OrderedDict still offers additional features that might be useful.

Table of Contents

OrderedDict

Syntax to create OrderedDict object:

ordereddict_object = OrderedDict(dict)

  • OrderedDict() – This is the constructor to create an object
  • dict – This is the regular dictionary passed as an argument based on which OrderedDict object will be created.
  • ordereddict_object – This is the reference to the OrderedDict object.

OrderedDict is subclass of dict

OrderedDict is subclass of regular dictionary (dict). This we can verify using the issubclass() method.

from collections import OrderedDict

# check for OrderedDict as subclass of dict
print("check for OrderedDict as subclass of dict")
print(issubclass(OrderedDict, dict))  # Output => True

Create OrderedDict object

There are multiple ways to create OrderedDict object.

  1. Empty OrderedDict object without the regular dictionary
  2. OrderedDict object with dictionary
  3. OrderedDict object using fromkeys() method
from collections import OrderedDict

# Scenario 1 - create empty OrderedDict
print("create empty OrderedDict")
empty_odict = OrderedDict()
print(empty_odict)
print(type(empty_odict))

# Scenario 2 - create OrderedDict from dictionary
print("create OrderedDict from dictionary")
courses_odict = OrderedDict({1:"AWS", 2:"Python", 3:"DevOps"}) 
print(courses_odict)
print(type(courses_odict))

# Scenario 3 - create OrderedDict using fromkeys() method
print("create OrderedDict using fromkeys() method")
fromkeys_odict = OrderedDict.fromkeys("shbytes")
print(fromkeys_odict)
print(type(fromkeys_odict))
  1. In first scenario, we are using OrderedDict() without regular dictionary. This will create an empty OrderedDict object.
  2. In second scenario, we are using OrderedDict({1:"AWS", 2:"Python", 3:"DevOps"}) to create an OrderedDict object. This object will have key-value pairs from the given dictionary and order of elements will be reserved in which they are inserted.
  3. In third scenario, we are using OrderedDict.fromkeys("shbytes") to create an OrderedDict object. fromkeys() method takes any iterable like list, tuple, string as an argument and dictionary key-value pairs are created based on that. Iterable elements are taken as key and None is assigned as a value.

Program Output

create empty OrderedDict
OrderedDict()
<class 'collections.OrderedDict'>

create OrderedDict from dictionary
OrderedDict({1: 'AWS', 2: 'Python', 3: 'DevOps'})
<class 'collections.OrderedDict'>

create OrderedDict using fromkeys() method
OrderedDict({'s': None, 'h': None, 'b': None, 'y': None, 't': None, 'e': None})
<class 'collections.OrderedDict'>

Compare OrderedDict and dict

from collections import OrderedDict

# compare OrderedDict and dict
print("compare regular dictionary")
print({1:"AWS", 2:"Python"} == {1:"AWS", 2:"Python"})  # Output => True

print("compare OrderedDict")
courses1_odict = OrderedDict({1:"AWS", 2:"Python"}) 
courses2_odict = OrderedDict({1:"AWS", 2:"Python"}) 
print(courses1_odict==courses2_odict)  # Output => True

Access key-value from OrderedDict

Most of methods with OrderedDict are similar to used with regular dictionary object.

from collections import OrderedDict

courses_odict = OrderedDict({'c1':"AWS",'c2':"Python",'c3':"DevOps"})
print(courses_odict)
print(courses_odict.keys())   # Access all keys in order
print(courses_odict.items())  # Access all values in order
print(courses_odict.values()) # Access key-value pairs
print('c4'.join(courses_odict.keys())) # all keys are joined with c4 in between those keys

Program Output

OrderedDict({'c1': 'AWS', 'c2': 'Python', 'c3': 'DevOps'})
odict_keys(['c1', 'c2', 'c3'])
odict_items([('c1', 'AWS'), ('c2', 'Python'), ('c3', 'DevOps')])
odict_values(['AWS', 'Python', 'DevOps'])
c1c4c2c4c3

OrderedDict – move_to_end() method

move_to_end() method is used to move the given key element either at the left end of the dictionary or at the right end of the dictionary.

Syntax – ordereddict_object.move_to_end(key, last=True)

  • key – This is a mandatory parameter. It is the element key which needs to be moved at the end of the dictionary.
  • last – This is an optional parameter. True is the default value. When last=True, then key element is moved to the right end (last position) of the dictionary. When last=False, then key element is moved to the first position of the dictionary.
  • move_to_end() method raises KeyError, if the given key does not exists in the dictionary.
from collections import OrderedDict

# Scenario 1 - move_to_end(key, last=True) (default is True)
# move an existing key to right end of an ordered dictionary, if last is True (the default)
print("move an existing key to right end of an ordered dictionary, if last is True (the default)")
courses_odict = OrderedDict({1:"AWS", 2:"Python", 3:"DevOps"})
print(courses_odict)         # Original order of elements
courses_odict.move_to_end(2) # default value for last=True
print(courses_odict)         # Order of elements after moving key element to right end

# Scenario 2 - move_to_end(key, last=False) (default is True)
# move an existing key to left end of an ordered dictionary, if last is False
print("move an existing key to left end of an ordered dictionary, if last is False")
courses_odict = OrderedDict({1:"AWS", 2:"Python", 3:"DevOps"})
print(courses_odict)                         # Original order of elements
courses_odict.move_to_end(2, False) # last=False, key element move to left end
print(courses_odict)                         # Order of elements after moving key element at first position

# Scenario 3 - raises KeyError if the key does not exist
print("raises KeyError if the key does not exist")
courses_odict = OrderedDict({1:"AWS", 2:"Python", 3:"DevOps"})
print(courses_odict)
try:
	courses_odict.move_to_end(4) # key 4 does not exist in dictionary
except KeyError as err:          # raise and catch KeyError
	print("error", err)
  1. In scenario 1, using courses_odict.move_to_end(2) to move key 2 element to the right end (last position) of the dictionary. Default value of last=True.
  2. In scenario 2, using courses_odict.move_to_end(2, False) to move key 2 element at the first position of the dictionary.
  3. In scenario 3, courses_odict.move_to_end(4), where key 4 does not exists in the dictionary. KeyError will be raised.
move an existing key to right end of an ordered dictionary, if last is True (the default)
OrderedDict({1: 'AWS', 2: 'Python', 3: 'DevOps'}) # Original order of elements
OrderedDict({1: 'AWS', 3: 'DevOps', 2: 'Python'}) # Element with key 2 move to the right end

move an existing key to left end of an ordered dictionary, if last is False
OrderedDict({1: 'AWS', 2: 'Python', 3: 'DevOps'}) # Original order of elements
OrderedDict({2: 'Python', 1: 'AWS', 3: 'DevOps'}) # Element with key 2 move to the first position

raises KeyError if the key does not exist
OrderedDict({1: 'AWS', 2: 'Python', 3: 'DevOps'}) # Original order of elements
error 4  # Key 4 does not exists in the dictionary

Remove element from OrderedDict

We can use pop(key) and popitem(last) methods to take out the key-values from the OrderedDict.

  1. odict.pop(key) – This method takeout the given key element from the dictionary. Key element value will be returned and element removed from the dictionary.
  2. odict.popitem(last=True) – This method takeout the last element from the dictionary. It returns key-value pair for the element.
    • last is an optional parameter with default value True.
    • If last=True, then last element will be removed.
    • if last=False, then first element will be removed.
from collections import OrderedDict

# pop(key)
# take out element with the given key
print("take out element with the given key")
courses_odict = OrderedDict({1:"AWS", 2:"Python", 3:"DevOps"})
print(courses_odict)              # Original elements in dictionary
pop_value = courses_odict.pop(3)  # Pop element with key 3
print(courses_odict)              # Elements after removing element with key 3
print(pop_value)                  # Value for key 3

# returns and removes a (key, value) pair, LIFO order if last is true
print("returns and removes a (key, value) pair, LIFO order if last is true")
courses_odict = OrderedDict({1:"AWS", 2:"Python", 3:"DevOps"})
print(courses_odict)                        # Original elements in dictionary
pop_item = courses_odict.popitem(last=True) # Pop last element
print(courses_odict)                        # Elements after removing last element
print(pop_item)                             # Element taken out

# returns and removes a (key, value) pair, FIFO order if last is False
print("returns and removes a (key, value) pair, FIFO order if last is False")
courses_odict = OrderedDict({1:"AWS", 2:"Python", 3:"DevOps"})
print(courses_odict)                         # Original elements in dictionary
pop_item = courses_odict.popitem(last=False) # Pop first element
print(courses_odict)                         # Elements after removing first element
print(pop_item)                              # Element taken out
  1. Using courses_odict.pop(3) to takeout element with key 3 and its value will be returned.
  2. Using courses_odict.popitem(last=True) to takeout last element from the dictionary.
  3. Using courses_odict.popitem(last=False) to takeout first element from the dictionary.

Program Output

take out element with the given key
OrderedDict({1: 'AWS', 2: 'Python', 3: 'DevOps'}) # Original order of elements
OrderedDict({1: 'AWS', 2: 'Python'})              # Elements after removing element with key 3
DevOps # Key 3 element value

returns and removes a (key, value) pair, LIFO order if last is true
OrderedDict({1: 'AWS', 2: 'Python', 3: 'DevOps'}) # Original order of elements
OrderedDict({1: 'AWS', 2: 'Python'})              # Elements after removing last element
(3, 'DevOps') # last element key-value pair

returns and removes a (key, value) pair, FIFO order if last is False
OrderedDict({1: 'AWS', 2: 'Python', 3: 'DevOps'}) # Original order of elements
OrderedDict({2: 'Python', 3: 'DevOps'})           # Elements after removing first element
(1, 'AWS') # first element key-value pair

Summary

In this article, we learned about OrderedDict collection in Python. Following topics were discussed:

Code – Github Repository

All code snippets and programs for this article and for Python tutorial, can be accessed from Github repository – Comments and Docstring in Python.

Python Topics


Interview Questions & Answers

Q: How is the performance of OrderedDict compared to normal dictionary?

OrderedDict can be slightly slower than a regular dictionary because it has additional overhead to maintain the doubly linked list internally that tracks the order of keys. But from Python 3.7 version normal Python dictionaries also maintain insertion order.

Q: Give some use cases in which we have to use OrderedDict?

Some common scenarios where OrderedDict or order of dictionary is useful are:

  • LRU Cache Implementation – Since we can efficiently pop from the beginning and move elements to the end, it’s suitable for implementing LRU (Least Recently Used) caches.
  • Ordered JSON serialization – Sometimes we need to ensure the order of keys when serializing to JSON.
  • Maintaining Insertion Order – If we are working in environments where order of elements is important, in those scenarios we can use OrderedDict.

Q: Write an implementation for LRU Cache using OrderedDict?

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):    # LRUCache constructor with capacity
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)  # Mark key as recently used
        return self.cache[key]       # Return value for key

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # Remove least recently used item

cache = LRUCache(2)
cache.put(1, "One")
cache.put(2, "Two")  # Elements order => {1: "One", 2: "Two"}
print(cache.get(1))  # Output => One
cache.put(3, "Three") # Cache capacity is 2, first element to be removed to add new element
print(cache.get(2))  # Output => -1 (removed as least recently used)

Program execution workflow

  • cache = LRUCache(2) => Created LRUCache object with capacity 2
  • cache.put(1, "One") => Added first element in the LRUCache dictionary. Elements order => {1: "One"}
  • cache.put(2, "Two") => Added second element in the LRUCache dictionary. Elements order => {1: "One", 2: "Two"}
  • print(cache.get(1)) => Accessed element with key 1. Element key 1 will be moved to the last position. Element order => {2: "Two", 1: "One"}
  • cache.put(3, "Three") => Adding new element in the LRUCache dictionary, but capacity is 2. First element from the dictionary will be removed and new element be added. Elements order => {1: "One", 3: "Three"}
  • print(cache.get(2)) => Element with key 2 does not exist in the LRUCache dictionary. -1 will be returned.

Tags:

Comments

No comments yet. Why don’t you start the discussion?

Leave a Reply

Your email address will not be published. Required fields are marked *