Sorted dictionary

[Raymond Hettinger]

On Jan 20, 5:02 pm, "Jan Kaliszewski" <z... at chopin.edu.pl> wrote:
> Hello,
>
> Inspired by some my needs as well as some discussions in the net, I've  
> implemented a sorted dictionary (i.e. a dict that returns keys, values and  
> items always sorted by keys):
>
> http://code.activestate.com/recipes/576998/
>
> Maybe it'll appear to be useful for somebody... And I'm curious about your  
> opinions.

Using an underlying list to track sorted items
means that insertion and deletion take O(n) time.
That could be reduced to O(log n) time by using
a blist or skiplist as the underlying structure
for maintaining a sort.

The other alternative is to just append items to the list
and sort the list on demand.  Since the Timsort takes advantage
of existing order, the process will approach O(n) if sorting
after every few updates.  This is close the O(n) time it takes
to iterate the list in the first place:

   s = SortedDict(items)
   list(s)               # O(n log n) to sort and O(n) to iterate
   s[newkey] = newval
   list(s)               # close to O(n)

my two cents,


Raymond