An ordered dictionary for the Python library?

[Russell E. Owen]

In article <13efnmi4n959a59 at corp.supernews.com>,
 Steven D'Aprano <steve at REMOVE-THIS-cybersource.com.au> wrote:

> On Wed, 12 Sep 2007 07:33:45 +0000, Mark Summerfield wrote:
> 
> > I feel that Python lacks one useful data structure: an ordered
> > dictionary.
> > 
> > I find such data structures v. useful in C++.
> [snip]
> 
> 
> Personally, I've never missed an ordered dict. What do people use them 
> for?
> 
> 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?

Opinions vary, but I think of it this way:
- A sorted dict keeps its keys sorted. This has an obvious alternative 
just sort the keys later (though I can imagine cases where it would be 
nicer not to).

- An ordered dict remembers the order of insertion. This is useful when 
you want to retain the order of insertion yet you also want fast lookup 
of individual items. Unlike a sorted dict, there is no trivial 
alternative (though you can argue about "trivial") and I really wish 
there was. There are several free versions available.

-- Russell