[Python-ideas] ordered dict
jcarlson at uci.edu
Fri Apr 20 18:23:54 CEST 2007
Mathias Panzenböck <grosser.meister.morti at gmx.net> wrote:
> Some kind of ordered dictionary would be nice to have in the
> standard library. e.g. a AVL tree or something like that.
> It would be nice so we can do things like that:
> for value in tree[:end_key]:
> del tree[:end_key]
> 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?
This has been brought up many times. The general consensus has been
'you don't get what you think you get'.
>>> u'a' < 'b' < () < u'a'
That is to say, there isn't a total ordering on objects that would make
sense as a sorted key,value dictionary. In Python 3.0, objects that
don't make sense to compare won't be comparable, so list.sort() and/or
an AVL tree may make sense again.
However, the problem with choosing to use an AVL (Red-Black, 2-3, etc.)
tree is deciding semantics. Do you allow duplicate keys? Do you allow
insertion and removal by position? Do you allow the fetching of the
key/value at position X? Do you allow the fetching of the position for
key X? Insertion before/after (bisect_left, bisect_right equivalents).
In many cases, using a sorted list gets you what you want, is almost as
fast, and has the benefit of using less memory.
More information about the Python-ideas