ActiveState Powered by ActiveState

Recipe 107747: Ordered Dictionary

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.

Python 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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).

Comments

  1. 1. At 10:46 a.m. on 18 jan 2002, Hamish Lawson said:

    Bug in __init__ regarding _keys. If UserDict.__init__ is actually passed a dictionary from __init__, then it will attempt to call update; but _keys isn't yet defined, and so an error will be raised. Therefore _keys must be defined first:

    def __init__(self, dict = None):
    self._keys = []
    UserDict.__init__(self, dict)
  2. 2. At 11:11 a.m. on 21 jan 2002, David Benjamin (the author) said:

    Bug in __init__ regarding _keys. I made the above change to the source. Thanks for catching this.

  3. 3. At 6:25 a.m. on 13 feb 2002, Wolfgang Grafen said:

    Ordered Dictionary at Parnassus. There is a more complete module addressing this topic under http://home.arcor.de/wolfgang.grafen/Python/Modules/Modules.html called seqdict.

    • seqdict keeps one value for one key

    • mseqdict keeps multiple values per key and is the closest emulation of areal world dictionary.

    (Search Parnassus for seqdict)

  4. 4. At 10:47 a.m. on 19 dec 2002, Jon Nelson said:

    Serious bug in copy(). There is a serious problem with copy() The returned object instance is one of UserDict not of odict. I use:

    def copy(self):
  newInstance = odict()
  newInstance.update(self)
  return newInstance

    and for update:

    def update(self, dict):
  for (key,val) in dict.items():
    self.__setitem__(key,val)
  5. 5. At 11:41 a.m. on 1 jan 2003, José Esteves said:

    keys() should return a copy of self._keys. It would be better to have

    def keys (self):
  return self._keys[:]

    to prevent changes to self._keys by callers of the keys() method.

  6. 6. At 6:01 p.m. on 2 dec 2004, Brian Hawthorne said:

    Bug in setdefault. setdefault returns the value (new or existing) for the given key.

    here is a correct setdefault:

    def setdefault(self, key, failobj = None):
    if key not in self._keys: self._keys.append(key)
    return UserDict.setdefault(self, key, failobj)
  7. 7. At 1:05 a.m. on 6 aug 2006, Charlie Taylor said:

    Extending to Sorted Dictionary. I needed a Sorted Dictionary and this Ordered Dictionary made a great starting point.

    I substituted: bisect.insort(self._keys,key) for: self._keys.append(key)

    in a few places and I was there.

    Thanks for the help

  8. 8. At 3:17 a.m. on 7 feb 2008, ruedi w said:

    variations in base class. you may want to derive from IterableUserDict to allow for things like [k for k in mydict].

    or in python >=2.2: derive directly from dict.

    if you cant decide, build a mixin using super() or a wrapper - this gives the ability to order any dict-like object

Sign in to comment