[Tutor] Sorted dictionaries

[Danny Yoo]

On Thu, 24 Jul 2003, Jeff Shannon wrote:

> > 1.  I need a sorted set data type and I noticed that there isn't one
> > in any of the python modules.  I also need just a regular set data
> > type, but I think I solved that by using a dictionary with both the
> > key and the value as the same object.  Do you know if there are any
> > Pyhton libraries that offer a sorted set implementation?
>
> Nothing standard.  I believe that Sets will become a built-in type in
> Python 2.3 (due out any day now), but I don't know whether they'll be
> sortable.  You could probably work out something that uses a dict to
> emulate a set, and keeps a sort()ed list of keys...  I'm sure I've seen
> discussion about sorted dictionaries before, but can't recall whether it
> was here or on comp.lang.python; a bit of trawling through archives and
> google groups might turn something up.


Here a link to that discussion:

    http://mail.python.org/pipermail/tutor/2002-November/018864.html


We can implement a "sorted" map using a data structure called a "Red-Black
Tree".  Chris Gonnerman has written a nice rbtree module:

    http://newcenturycomputers.net/projects/rbtree.html


Hope this helps!