An ordered dictionary for the Python library?

[Mark Summerfield]

I forgot one item in the proposed API:

ordereddict.delete(index : int)

Also, the API for keys() should be

ordereddict.keys(firstindex : int = None, secondindex : int = None)

If called with no args, returns list of all keys (in key order of
course); if one arg is given, returns keys with indexes in range(0,
firstindex); if two args are given, returns keys with indexes in
range(firstindex, secondindex).

Below is a stripped-down implementation in pure python that is just 84
lines long.
(I have a proper version with blank lines and doctests which is 482
lines but I thought that was a bit long to post.)

It should work as a drop-in replacement for dict (apart from
performance), but with the keys ordered by <, so that every list or
iterator that it returns is always in key order.

The get(), has_key(), __contains__(), len(), and __getitem__() methods
are not reimplemented because the base class versions work fine.

I'm only posting it to give a better feel for the API---if someone did
a better (faster) implementation (e.g., in C), that'd be great, but
best to get consensus on an API first I think (if consensus is
possible at all!).

import bisect
class ordereddict(dict):
    def __init__(self, *args, **kwargs):
        dict.__init__(self, *args, **kwargs)
        self.__keys = sorted(dict.keys(self))
    def update(self, *args, **kwargs):
        dict.update(self, *args, **kwargs)
        self.__keys = sorted(dict.keys(self))
    @classmethod
    def fromkeys(cls, iterable, value=None):
        dictionary = cls()
        for key in iterable:
            dictionary[key] = value
        return dictionary
    def key(self, index):
        return self.__keys[index]
    def item(self, index):
        key = self.__keys[index]
        return key, self[key]
    def value(self, index):
        return self[self.__keys[index]]
    def set_value(self, index, value):
        self[self.__keys[index]] = value
    def delete(self, index):
        key = self.__keys[index]
        del self.__keys[index]
        dict.__delitem__(self, key)
    def copy(self):
        dictionary = ordereddict(dict.copy(self))
        dictionary.__keys = self.__keys[:]
        return dictionary
    def clear(self):
        self.__keys = []
        dict.clear(self)
    def setdefault(self, key, value):
        if key not in self:
            bisect.insort_left(self.__keys, key)
        return dict.setdefault(self, key, value)
    def pop(self, key, value=None):
        if key not in self:
            return value
        i = bisect.bisect_left(self.__keys, key)
        del self.__keys[i]
        return dict.pop(self, key, value)
    def popitem(self):
        item = dict.popitem(self)
        i = bisect.bisect_left(self.__keys, item[0])
        del self.__keys[i]
        return item
    def keys(self, firstindex=None, secondindex=None):
        if firstindex is not None and secondindex is None:
            secondindex = firstindex
            firstindex = 0
        else:
            if firstindex is None:
                firstindex = 0
            if secondindex is None:
                secondindex = len(self)
        return self.__keys[firstindex:secondindex]
    def values(self):
        return [self[key] for key in self.__keys]
    def items(self):
        return [(key, self[key]) for key in self.__keys]
    def __iter__(self):
        return iter(self.__keys)
    def iterkeys(self):
        return iter(self.__keys)
    def itervalues(self):
        for key in self.__keys:
            yield self[key]
    def iteritems(self):
        for key in self.__keys:
            yield key, self[key]
    def __delitem__(self, key):
        i = bisect.bisect_left(self.__keys, key)
        del self.__keys[i]
        dict.__delitem__(self, key)
    def __setitem__(self, key, value):
        if key not in self:
            bisect.insort_left(self.__keys, key)
        dict.__setitem__(self, key, value)
    def __repr__(self):
        return "ordereddict({%s})" % ", ".join(
               ["%r: %r" % (key, self[key]) for key in self.__keys])