Proposed implementation for an Ordered Dictionary

[Raymond Hettinger]

> > What about using a second dictionary (indexed by the incrementing
> > counter) instead of a list to record the insertion order?  Then you
> > have O(1) deletion, and traversal takes an O(n log n) sorting
> > operation.

> My first attempt used exactly that approach and it works fine
> though it does complicate the code quite a bit and slows down
> all of the common operations by a constant factor.

FWIW, here is the code for that approach.

--------------------------------------
from collections import MutableMapping

class OrderedDict(dict):

    def __init__(self, *args, **kwds):
        if len(args) > 1:
            raise TypeError('expected at 1 argument, got %d', len
(args))
        self.clear()
        self.update(*args, **kwds)

    def clear(self):
        self.__cached_sort = None
        self.__cnt = 0
        self.__order = {}
        dict.clear(self)

    def __setitem__(self, key, value):
        if key not in self:
            self.__cached_sort = None
            self.__cnt += 1
            self.__order[key] = self.__cnt
        dict.__setitem__(self, key, value)

    def __delitem__(self, key):
        if key in self:
            self.__cached_sort = None
            del self.__order[key]
        dict.__delitem__(self, key)

    def __sorted(self):
        # return keys in insertion order and cache the result
        if self.__cached_sort is None:
            self.__cached_sort = sorted(dict.keys(self),
                                        key=self.__order.__getitem__)
        return self.__cached_sort

    def __iter__(self):
        return iter(self.__sorted())

    def __reversed__(self):
        return iter(reversed(self.__sorted()))

    def popitem(self):
        # O(n) cost on the first pop and O(1) on successive pops
        if not self:
            raise KeyError
        key = self.__sorted().pop()
        del self.__order[key]
        value = dict.pop(self, key)
        return key, value

    # Methods with indirect access via the above methods

    setdefault = MutableMapping.setdefault
    update = MutableMapping.update
    pop = MutableMapping.pop
    keys = MutableMapping.keys
    values = MutableMapping.values
    items = MutableMapping.items

    def __repr__(self):
        return '{' + ', '.join(map('%r: %r'.__mod__, self.items())) +
'}'

    def copy(self):
        return self.__class__(self)

    @classmethod
    def fromkeys(cls, iterable, value=None):
        d = cls()
        for key in iterable:
            d[key] = value
        return d

    def __reduce__(self):
        # pickle an items list and any extra info in the instance dict
        items = list(self.items())
        inst_dict = vars(self).copy()
        for attr in vars(self.__class__):
            inst_dict.pop(attr, None)
        return (self.__class__, (items,), inst_dict)