Sorted associative container in Python?

[Duncan Booth]

Roy Smith <roy at panix.com> wrote in news:roy-
A36B0E.08371022052003 at reader1.panix.com:

> 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.
> 
The easiest way is to store the data in the dictionary, but maintain a 
separate sorted list of the keys. Depending on the ratio of updates to 
iterations you might either update the sorted list every time a new key is 
added to the dictionary, which makes dictionary update log n but your 
iteration is linear, or simply throw the sorted list away when changing the 
dicionary and rebuild it next time you iterate, this keeps the constant 
time updates and makes iteration nlogn, but if updates are rare, or happen 
together probably works out faster in practice.

-- 
Duncan Booth                                             duncan at rcp.co.uk
int month(char *p){return(124864/((p[0]+p[1]-p[2]&0x1f)+1)%12)["\5\x8\3"
"\6\7\xb\1\x9\xa\2\0\4"];} // Who said my code was obscure?