Title: Ordered Dictionary
Submitter: David Benjamin (other recipes)
Last Updated: 2002/01/21
Version no: 1.2
Category: Extending

Description:

This dictionary class extends UserDict to record the order in which items are added. Calling keys(), values(), items(), etc. will return results in this order. This works similarly to the array type in PHP.

Source: Text Source

from UserDict import UserDict

class odict(UserDict):
    def __init__(self, dict = None):
        self._keys = []
        UserDict.__init__(self, dict)

    def __delitem__(self, key):
        UserDict.__delitem__(self, key)
        self._keys.remove(key)

    def __setitem__(self, key, item):
        UserDict.__setitem__(self, key, item)
        if key not in self._keys: self._keys.append(key)

    def clear(self):
        UserDict.clear(self)
        self._keys = []

    def copy(self):
        dict = UserDict.copy(self)
        dict._keys = self._keys[:]
        return dict

    def items(self):
        return zip(self._keys, self.values())

    def keys(self):
        return self._keys

    def popitem(self):
        try:
            key = self._keys[-1]
        except IndexError:
            raise KeyError('dictionary is empty')

        val = self[key]
        del self[key]

        return (key, val)

    def setdefault(self, key, failobj = None):
        UserDict.setdefault(self, key, failobj)
        if key not in self._keys: self._keys.append(key)

    def update(self, dict):
        UserDict.update(self, dict)
        for key in dict.keys():
            if key not in self._keys: self._keys.append(key)

    def values(self):
        return map(self.get, self._keys)

Discussion:

Often it is useful to use a dictionary to store information where the order of that information matters. In Python, one must usually keep a list of keys and pass the list along with the dictionary to any functions that need to maintain this order. This implementation stores the list of keys internally and overrides the usual accessor methods to keep the list up to date with each operation.

Example:

>>> d = odict()
>>> d['a'] = 1
>>> d['b'] = 2
>>> d['c'] = 3
>>> d.items()
[('a', 1), ('b', 2), ('c', 3)]

popitem() has been fixed in this version to throw the correct exception on an empty dictionary.

Note that all operations on the key list are O(n).