[Python-ideas] ordered dict
tjreedy at udel.edu
Fri Apr 20 20:34:58 CEST 2007
"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
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
More information about the Python-ideas