No trees in the stdlib?

greg greg at
Fri Jun 26 21:43:40 EDT 2009

João Valverde wrote:

> What's lacking is an associative array that preserves ordering, doesn't 
> require a hash function and has fast insertions and deletions in 
> O(log(n)).

Careful here -- you can't get away from the need for
hashability just by using a tree. Even if you don't
need to actually hash the values, it's still important
that the criterion for ordering between objects doesn't
change while they're in the tree, otherwise they'll
be in the wrong place and won't be found by subsequent

 > I'm genuinely surprised to know
> there are no data structures that efficiently support such a common need 
> in Python.

Is it really all that common? If it truly were common,
there probably *would* be something for it in the
stdlib by now.

What sort of things are you doing that you want such
a structure for? Maybe we can suggest a way of using
the existing data structures to achieve the same


More information about the Python-list mailing list