An ordered dictionary for the Python library?

[Duncan Booth]

Steven D'Aprano <steve at REMOVE-THIS-cybersource.com.au> wrote:

> In fact, I'm not sure what people mean by ordered dicts. I assume they
> mean the keys are ordered, not the values. But ordered by what?
> Insertion order? Modification order? Alphabetical order? 

All of the above at different times. Usually I think they mean original 
insertion order, I'd more often like modification order though.

Insertion order can certainly be useful: any situation where you currently 
keep items in a list because the original order is important but also copy 
them into a dictionary or set because you need fast lookup. 
e.g. if you want only unique items out of a list but need to preserve order 
of first occurrence.

Another example would be uml->code round tripping: you parse in an existing 
file containing method definitions, then update the method definitions from 
a UML model and write the file out again: ArchGenXML does exactly that, but 
last I looked the methods were written out in whatever order the dictionary 
stored them which really messes up version control. It really should 
preserve the order that methods appeared in the file.

Modification order would be great for a cache. Touch items whenever they 
are referenced and then whenever the cache gets too big just pop the oldest 
until you get back to the desired size.

Alphabetical or other sorted order when you want to get smallest/largest or 
next smaller/larger then a specific item. I don't agree you necessarily 
mean ordered by key rather than value, I think you could specify any 
sortkey and expect updating the value to restore the ordering. Maybe if you 
are recording some stats and want to regularly output the top 10?