sorteddict PEP proposal [started off as orderedict]

[Hamilton, William]

> From: Paul Hankin
> 
> 
> Here's a first go. Sorting occurs when the keys are iterated over,
> making it fast (almost as a dict) for construction, insertion, and
> deletion, but slow if you're iterating a lot. You should look at some
> use cases to decide if this approach is best, or if a sorted
> datastructure should be used instead, but my instinct is that this is
> a decent approach. Certainly, you're unlikely to get a simpler
> implementation :)
> 
> class sorteddict(dict):
>     "A sorted dictionary"
>     def __init__(self, arg=None, cmp=None, key=None, reverse=False):
>         if arg:
>             super(sorteddict, self).__init__(arg)
>         else:
>             super(sorteddict, self).__init__()
>         self._cmp = cmp
>         self._key = key
>         self._reverse = reverse
>     def keys(self):
>         return sorted(super(sorteddict, self).keys(), cmp=self._cmp,
>             key=self._key, reverse=self._reverse)
>     def iter_keys(self):
>         return (s for s in self.keys())
>     def items(self):
>         return [(key, self[key]) for key in self.keys()]
>     def iter_items(self):
>         return ((key, self[key]) for key in self.keys())
>     def values(self):
>         return [self[key] for key in self.keys()]
>     def iter_values(self):
>         return (self[key] for key in self.keys())
>     def __str__(self):
>         return '{' + ', '.join('%s: %s' % (repr(k), repr(v))
>             for k, v in self.iter_items()) + '}'
>     def __repr__(self):
>         return str(self)
>     def __iter__(self):
>         return self.iter_keys()


You could speed up keys() at the cost of memory if you maintained a list
of keys in the instance.  Doing so would let you use an "unsorted" flag
that gets set when a new key is added and checked when keys() is called.
If the flag is unset, just return a copy of the list.  Otherwise, sort
the list in place, return a copy, and unset the flag.  (Copies because
you don't want the master key list to be modified by code using the
class.)

The use case for this seems to be when you have a dictionary that you
need to often work through in sorted order.  Sorting the keys every time
keys() is called isn't an improvement over using a regular dict and
sorting the keys normally.  So the extra memory cost of maintaining an
internal keys list looks reasonable to me.



--
-Bill Hamilton