Proposed implementation for an Ordered Dictionary

Colin J. Williams cjw at
Sat Feb 28 10:58:10 EST 2009

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 

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

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

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

Colin W.

More information about the Python-list mailing list