Sorted associative container in Python?

[Dave Benjamin]

In article <roy-A36B0E.08371022052003 at reader1.panix.com>, Roy Smith wrote:
> C++ STL's map is a sorted associative container, with the following 
> properties:
> 
> 1) You can iterate over the entries in key-sorted order in linear time.
> 2) You can access any given key in log time.
> 3) Keys can be arbitrary type values.
> 
> What's the best way to do that in Python?  A dictionary gives you #2 (or 
> maybe even constant time?) and #3, but fails #1.  A list fails #3.

See my "odict" recipe at:
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/107747

Please note that there are a couple of bugs that readers have discovered and
I have not yet fixed them in the example. It extends UserDict (I wrote it
before I started using Python 2.2) and uses a list to keep track of keys. I
tried to be thorough about the interface.

HTH,
Dave