Sorted associative container in Python?

[Tim Peters]

[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.

See

    http://www.zope.org/Wikis/ZODB/guide/node6.html

for an introduction to the BTree types implemented (as C extensions) in Zope
Corp's ZODB (a persistent object-oriented database; ZODB's BTrees play very
nicely in that context, but can also be used as in-memory data structures
with no connection to a database).  Your #1 and #2 are satisfied
straightforwardly by BTrees; your #3 bristles with potential difficulties,
as explained on the referenced page.