[Python-ideas] ordered dict

[Terry Reedy]

"Mathias Panzenböck" <grosser.meister.morti at gmx.net> 
wrote in message news:4628DF1F.3060803 at gmx.net...
| Some kind of ordered dictionary would be nice to have in the
| standard library.

This has come up frequently, with 'ordered' having two quite different 
meanings.

1. Order of entry into the dictionary (for use with class definitions, for 
instance(though don't ask me why!).  When a given key is entered just once, 
this is relatively easy: just append to a subsidiary list.  I believe this 
is being at least considered for 3.0.

2. Order in the sorting or collation sense, which I presume you mean.  To 
reduce confusion, call this a sorted dictionary, as others have done.

Regardless, this has the problem that potential keys are not always 
comparable.  This will become worse when most cross-type comparisons are 
disallowed in 3.0.  So pershaps the __init__ method should require a tuple 
of allowed key types.

| e.g. a AVL tree or something like that.
...
| A alternative would be just to sort the keys of a dict but
| that's O( n log n ) for each sort. Depending on what's the more
| often occurring case (lookup, insert, get key-range, etc.) a
| other kind of dict object would make sense.
|
| What do you think?

If not already present in PyPI, someone could code an implementation and 
add it there.  When such has be tested and achieved enough usage, then it 
might be proposed for addition to the collections module.

Terry Jan Reedy