[Python-3000] ordered dict for p3k collections?

[Charles D Hixson]

skip at pobox.com wrote:
>     Mark> With sorteddict you pay O(log N) for accessing, but you pay
>     Mark> nothing for sorting.
>
> Pay me now or pay me later, but maintaining a sorted sequence will always
> cost something.
>
> Skip
>   
Very frequently, however, I want frequent sorted access to a container.  
I.e. I will want something like "what's the next key bigger than nnn"  
(I said nnn because it often isn't a string).  In such cases a B+Tree or 
B*Tree is a much better answer than a hash table.  I'll grant that for 
the most common cases hash tables are superior...but not, by any means, 
for all cases.

There have been cases where I have maintained both a list and a dict for 
the same data.  (Well, the list was an index into the dict, but you get 
the idea.)   The dict was for fast access when I knew the key, and the 
list was for binary search when I knew things *about* the key.

An important note here is that the key to the dict/list was generally 
NOT a string in these situations.  If strings suffice, then I've 
generally found a hash table to work well enough, and frequently been 
superior.

OTOH, if you don't need continual access while you are building the 
list, then I agree with you.  The problem is that each time you sort a 
hash table you must pay for an entire sort, while adding a key or two to 
a B+Tree is relatively cheap.