> > 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)
--
http://mail.python.org/mailman/listinfo/python-list
