Sorted associative container in Python?

[Roy Smith]

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.