An ordered dictionary for the Python library?

[Mark Summerfield]

On 14 Sep, 10:49, Antoon Pardon <apar... at forel.vub.ac.be> wrote:
> On 2007-09-14, Mark Summerfield <m.n.summerfi... at googlemail.com> wrote:
>
>
>
> > On 14 Sep, 02:35, Jürgen Urner <jUr... at arcor.de> wrote:
> >> Puh, what a discussion... most common use case I can think of is
>
> >> >> d = {'a': 1, 'b': 2, 'c': 3}
> >> >> for key in d:
> >> >>     # do something that relies on order of keys as specified in the constructor
>
> >> It's a bit tireing having to type
>
> >> >> for key in sorted(d.keys()):
> >> >>     do_somethig_with(d[key])
>
> >> instead of a trustfully
>
> >> >> for value in d.values():
> >> >>     do_somethig_with(value)
>
> >> As far as I can see much cleaner. No black magic needed ++ sort the
> >> dict
> >> to another order and rely on the sort order being stable would be a
> >> really
> >> a nice thing to have.
>
> >> My 2 cents,  Jürgen
>
> > What I envisage is:
>
> > d = ordereddict(a=1, x=20, b=35, m=4)
> > # some time later
> > d["e"] = 15
> > # later still
> > d["b"] = 70
> > d.keys() # returns ['a', 'b', 'e', 'm', 'x']
> > d.values() # returns [1, 70, 15, 4, 20]
>
> which seems to be exactly what my avltree module mentioned earlier
> provides.
>
> >>> from avltree import Tree
> >>> d=Tree(a=1, x=20, b=35, m=4)
> >>> d["e"] = 15
> >>> d["b"] = 70
> >>> d.keys()
>
> ['a', 'b', 'e', 'm', 'x']>>> d.values()
>
> [1, 70, 15, 4, 20]

Antoon,

Your AVL tree looks impressive (although it has five times the lines
of my ordereddict), but it does not appear to support dict.update()'s
API (which was extended in 2.4), so you can't do: avl.update({'g':
20}, a=9, b=22).

Also, it does not provide the key(), value(), and item() methods that
the API I proposed can support (because in an ordereddict, index
positions make sense).

If there was consensus on an API and you, me, and others had different
implementations, we could always come up with some tests to compare
their relative performance, and put the fastest one(s) forward in a
PEP. (I don't care if my own code is used or not, it is the
functionality in Python's standard library that I want, whoever's code
it is.)