Mathias Panzenböck <grosser.meister.morti@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