Welcome, guest | Sign In | My Account | Store | Cart

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, 52 lines
 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)

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).

8 comments

Hamish Lawson 19 years, 10 months ago  # | flag

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)
David Benjamin (author) 19 years, 10 months ago  # | flag

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

Wolfgang Grafen 19 years, 9 months ago  # | flag

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)

Jon Nelson 18 years, 11 months ago  # | flag

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)
José Esteves 18 years, 11 months ago  # | flag

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.

Brian Hawthorne 17 years ago  # | flag

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)
Charlie Taylor 15 years, 4 months ago  # | flag

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

ruedi w 13 years, 10 months ago  # | flag

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

Created by David Benjamin on Tue, 15 Jan 2002 (PSF)
Python recipes (4591)
David Benjamin's recipes (2)

Required Modules

Other Information and Tasks