Proposed implementation for an Ordered Dictionary

[Colin J. Williams]

Raymond Hettinger wrote:
> [Paul Rubin]
>> Ehh, I guess I'm not surprised at the slowdown and extra complexity
>> from the second dict.  Oh well.  If the module really turns out to be
>> really used a lot, another (messy) approach would be to write a C
>> extension that uses a doubly linked list some day.
> 
> That seems like an ideal implementation to me.
> 
>   O(1): appending, popping, searching, and deletion
>   O(n): traversal
> 
> Raymond

Sometimes, it's useful to be able to 
obtain the data in the sorted sequence.

You might consider adding functionality 
like:

     def seqItems(self):
         '''To return the items, sorted 
by key. '''
         return [self[k] for k in 
self.seqKeys()]

     def seqKeys(self):
         ''' To return the keys sorted.  '''
         k= self.keys()
         k.sort()
         return k

     def seqValues(self):
         ''' To return the values, with 
their keys, sorted by value. '''
         v= [(it[1], it[0]) for it in 
self.items()]
         v.sort()
         return v

Colin W.