[Python-ideas] ordered dict

[Josiah Carlson]

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]:
> 	do_something_with(value)
> 
> 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'
    True

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).
Etcetera.

In many cases, using a sorted list gets you what you want, is almost as
fast, and has the benefit of using less memory.


 - Josiah