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

This is a class that acts like a dictionary, except that it maintains insert order. This can be useful when you wish to associate two objects in a key-value manner and would like to use a dictionary interface to access the elements, but you need to remember what order the elements were added

Python, 40 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
class OrderedDictionary:

    def __init__(self):

        self._keys=[]
        self._values=[]

    def __len__ (self):
        return len (sef.keys)

    def __getitem__ (self, key):

        if self.has_key (key):
            return self._values[self._keys.index(key)]
        else:
            return None
    def __setitem__ (self, key, value):
        if self.has_key (key):
            self._values [self._keys.index(key)] = value
        else:
            self._keys.append(key)
            self._values.append(value)

    def __delitem__(self, key):
        val = self[key]
        
        self._keys.remove(key)
        self._values.remove (val)

    def has_key (self, aKey):
        return aKey in self._keys

    def keys (self):
        return self._keys

    def values (self):
        return self._values

    def items (self):
        return map (None, self._keys, self._values)

    
        
    
        

4 comments

Dean Hall 22 years, 10 months ago  # | flag

not entirely unlike a dict. This is a nice class that people will find useful, but it needs some work.

I see a potential ERROR in __delitem__. The list.remove() command removes the first matching item in the list. So if two items have the same value, trouble will ensue if you try to remove the second of these two items. The key of the second item will be removed and the value of the first item will be removed. This will distort the key,value alignment of the dict for all items between the first and second item mentioned.

SOLUTION: find the index of the key you are deleting, delete the key, and then delete the value at the same index.

Also, a WARNING:

__getitem__ returns "None" when a key is not present. This is instead of raising a KeyError like a regular dict.

Hamish Lawson 22 years, 10 months ago  # | flag

Using index() may be time-expensive. Using index() to locate a value in the _values list may be time-expensive if there are a large number of items. It may be better for the class to use its own dictionary to store the items (albeit at the cost of space), with the _keys list keeping track of the order.

Hamish Lawson 22 years, 10 months ago  # | flag

Correction. Of course I meant the _keys list rather than the _values list!

Jason Tudisco 16 years, 11 months ago  # | flag

Typos. def __len__ (self): return len(self._keys)

Created by Jay O'Connor on Thu, 15 Mar 2001 (PSF)
Python recipes (4591)
Jay O'Connor's recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks