OrderedDict in Python

What is OrderedDict?

The OrderedDict is a class in the collections module of Python. It acts like a regular dictionary but preserves the order in which items are inserted. Unlike standard dictionaries (in Python versions before 3.7, which did not guarantee insertion order), OrderedDict maintains the insertion sequence.

Key Features of OrderedDict:

1. Maintains Insertion Order: Keys of elements remain in the order when added.
2. Equality Check: Two OrderedDict objects are equal only if their key-value pairs and their order are the same.
3. Extra Methods: It includes special methods like move_to_end() and popitem() for order-specific operations.
4. Slower: It’s little slower because it has some added functionality compared to the normal dictionaries.

Importing OrderedDict

To use OrderedDict, import it from the collections module.

from collections import OrderedDict

Creating an OrderedDict

from collections import OrderedDict

# Creating an OrderedDict
ordered_dict = OrderedDict()
ordered_dict['a'] = 1
ordered_dict['b'] = 2
ordered_dict['c'] = 3

print(ordered_dict)

Output:

OrderedDict([('a', 1), ('b', 2), ('c', 3)])

Methods of OrderedDict

1. move_to_end(key, last=True)

Moves a given key to the end or to the beginning of the dictionary.

• last=True (default): Moves the key to the end.
• last=False: Shifts the key to the beginning.

od = OrderedDict({'a': 1, 'b': 2, 'c': 3})

# Move key 'b' to the end
od.move_to_end('b')
print(od)

# Move key 'a' to the beginning
od.move_to_end('a', last=False)
print(od)

Output:

OrderedDict([('a', 1), ('c', 3), ('b', 2)])
OrderedDict([('a', 1), ('c', 3), ('b', 2)])

2. popitem(last=True)

Remove and return an arbitrary (key, value) pair from the dictionary.

• last=True: remove last inserted item
• last=False: remove first inserted item

od = OrderedDict({'a': 1, 'b': 2, 'c': 3})

# Remove and return the last item
print(od.popitem())

# Current state of the OrderedDict
print(od)

# Remove and return the first item
print(od.popitem(last=False))

# Current state of the OrderedDict
print(od)

Output:

('c', 3)
OrderedDict([('a', 1), ('b', 2)])
('a', 1)
OrderedDict([('b', 2)])

3. Standard Dictionary Methods

The OrderedDict supports all methods available in regular dictionaries, such as get(), keys(), values(), and items().

od = OrderedDict({'x': 10, 'y': 20, 'z': 30})

# Access values using keys
print(od.get('x'))  # Output: 10

# Get all keys
print(list(od.keys()))  # Output: ['x', 'y', 'z']

# Get all values
print(list(od.values()))  # Output: [10, 20, 30]

# Get all key-value pairs
print(list(od.items()))  # Output: [('x', 10), ('y', 20), ('z', 30)]

Output:

10
['x', 'y', 'z']
[10, 20, 30]
[('x', 10), ('y', 20), ('z', 30)]

Comparison with Regular Dictionary

Starting from Python 3.7, insertion order is also maintained by regular dictionaries. However, it boasts some features over OrderedDicts as well, such as:

• Custom behavior for popitem() and move_to_end().
• Explicit guarantees of order in all versions of Python.

Example: Using OrderedDict for LRU Cache

An LRU (Least Recently Used) Cache is a data structure that removes the least recently accessed items when it exceeds its capacity.

Here’s how you can use OrderedDict to implement an LRU Cache:

from collections import OrderedDict

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

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

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

# Example usage
cache = LRUCache(2)
cache.put('a', 1)
cache.put('b', 2)
print(cache.get('a'))  # Output: 1
cache.put('c', 3)      # Removes 'b' as it is the least recently used
print(cache.get('b'))  # Output: -1

Output:

1
-1

Summary

• What’s special about OrderedDict?
  • Maintains insertion order.
  • It contains additional methods, such as move_to_end() and popitem(), for ordering manipulation.
  • Helpful in LRU cache use cases or in algorithms where the order needs to be controlled explicitly.
• When to Use OrderedDict?
  • You need order-sensitive operations or have a requirement to support Python versions lower than 3.7.