An ordered dictionary for the Python library?

[Chris Mellon]

On 9/12/07, Mark Summerfield <m.n.summerfield at googlemail.com> wrote:
> 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.
>

These sort of disagreements about what such a beast should "obviously"
do are a good part of the reason why one doesn't exist in the standard
library. A sorted dict is so trivial that it's not really seen as
necessary, since all you have to do is sort the keys(). An ordered
dict is generally better satisfied with a list, as you've seen.
There's implementations of all these for people who want something
wrapped up in the cookbook.


>But what happens when I need to do this a *lot* and when the number of
>items is hundreds or a few thousands?

keys = sorted(d.keys())
for k in key:
   ...

You've got two choices: either you insert more than you iterate, in
which case sorting at the point of iteration is the most efficient
option, or you iterate more than you insert, in which case sorting
after you insert is easy. There's no way that an ordered dict
implementation could satisfy both constraints. Can you honestly think
of a use case where the performance of your sorting is a bottleneck
*and* it's a suitably general case that a standard lib class should
optimize for that specific case? Even in this short thread we've seen
3 different ideas of what the dict should do.