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

A dictionary in which the insertion order of items is preserved.

Based on Doug Winter's recipe http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/438823

Python, 72 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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class OrderedDict(dict):
    """
    A dictionary in which the insertion order of items is preserved.
    """
    def __init__(self, d={}, **kw):
        self._keys = d.keys() + kw.keys()
        dict.__init__(self, d, **kw)

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

    def __setitem__(self, key, item):
        # a peculiar sharp edge from copy.deepcopy
        # we'll have our set item called without __init__
        if not hasattr(self, '_keys'):
            self._keys = [key,]
        if key not in self:
            self._keys.append(key)
        dict.__setitem__(self, key, item)

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

    def popitem(self):
        if len(self._keys) == 0:
            raise KeyError('dictionary is empty')
        else:
            key = self._keys[-1]
            val = self[key]
            del self[key]
            return key, val

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

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

    def iterkeys(self):
        return iter(self._keys)

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

    def itervalues(self):
        for k in self._keys:
            yield self[k]

    def values(self):
        return list(self.itervalues())

    def iteritems(self):
        for k in self._keys:
            yield k, self[k]

    def items(self):
        return list(self.iteritems())

    def __iter__(self):
        return self.iterkeys()

    def index(self, key):
        if not self.has_key(key):
            raise KeyError(key)
        return self._keys.index(key)

There are many implementations1 of ordered dictionary, but none of them can used in places of dictionary.

1 comment

Created by Anand Chitipothu on Thu, 7 Jun 2007 (PSF)
Python recipes (4591)
Anand Chitipothu's recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks