[Python-3000] ordered dict for p3k collections?

[Jason Orendorff]

One situation where a sorteddict would win is finding upper and lower
bounds.  This especially matters if you want to iterate over a
specific range of keys: "show me all entries between 1 Jan 2007 and 1
Feb 2007" is O(N) in the number of entries in that range, not the
entire data set.

I think people ask for things like this because they have a high-level
need like "read 3 log files, jam all the data into a single data
structure, and extract time slices from that" for which no
particularly obivous combination of lists and dicts seems to jump out
at you.  Then they hit on an idea like sorteddict that looks like it
might get them 60% of the way there and seems like a simple, obvious
building block that belongs in the stdlib.  That's my own experience,
anyway.

Is sorteddict really such a great building block?  I dunno.  It seems
like that might or might not be true.  These situations seem to come
up pretty rarely in Python's problem domain, so it's hard to get a
feel for it.

I do know from recent personal experience that system-level code often
wants custom data structures, and having spent a decade with Python
lists and dictionaries, I'm out of shape.  :)

-j