An ordered dictionary for the Python library?

[Mark Summerfield]

On 12 Sep, 13:46, Michele Simionato <michele.simion... at gmail.com>
wrote:
> On Sep 12, 2:42 pm, Steven D'Aprano <st... at REMOVE-THIS-
>
> cybersource.com.au> wrote:
> > On Wed, 12 Sep 2007 07:33:45 +0000, Mark Summerfield 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?
>
> Insertion order.
>
>  M.S.


Actually I meant by key order, so insertion order doesn't matter at
all. If you need a dictionary-like data structure that respects
insertion order you could use a list of (key, value) tuples.

Another respondent asked about use cases.

I have found time and again that I needed (key, value) pairs where the
key is some string that provides a representation for human readers
and the value is some internal key (e.g., database ID) that the system
uses internally. In these cases I often need to present the user with
a list of items from which to choose and want to present them in
sorted order. Naturally, I could use an ordinary dict and then do
this:

for string in sorted(d.keys()):
    process(string)

But what happens when I need to do this a *lot* and when the number of
items is hundreds or a few thousands? I'm having to sort again and
again, since it is often the case that the items in the list changes
during the runtime of the application. So my solution in C++ is to use
an ordered dictionary (a map in C++ jargon), which in Python means I
can simply write:

for string in od.keys():
    process(string)

Another situation where this is useful is if you need to hold lists of
strings preserving case but want them to be presented case-
insensitively. Here, you populate the ordered dictionary like this:

for string in somelist:
    od[string.lower()] = string

Now you can iterate over od in case-insensitive order and yet still
have access to the case-sensitive original, and never have to
explicitly sort the strings.

I think it comes down to the nail and hammer issue: if you have a
hammer all problems look nail shaped. In Python we have dict and list
so everything looks suitable for those data structures. But having had
a wrench (ordered dictionaries) in C++, I find that some problems need
a wrench. I think that once Python programmers have access to an
ordered dictionary some proportion of them will find it painful to
program without it, so I really think it belongs in the standard
library.