<div class="gmail_quote">On Tue, Aug 2, 2011 at 5:53 PM, Chris Rebert <span dir="ltr"><<a href="mailto:clp2@rebertia.com">clp2@rebertia.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="im">If you /really/ need a sorted mapping datatype, google for</div>
"sorteddict" (which is quite distinct from OrderedDict).<br>
Or look for a binary search tree or skip list implementation of some<br>
sort; but these aren't commonly used in Python, so it may be hard to<br>
find a good one.<br></blockquote><div><br></div><div>The blist package (I'm the author) provides a list-like type that has O(log n) insertions and deletions.  It provides a sorteddict type that uses the blist type under-the-hood.</div>
<div><br></div><div>blist's "sorteddict" supports the "key" parameter (which works like list.sort's key parameter), which the original poster could use to maintain the keys in reverse order.</div>
<div><br></div><div><a href="http://pypi.python.org/pypi/blist/">http://pypi.python.org/pypi/blist/</a></div><div><br></div><div>There's no overhead to learn how to use the new types.  A blist works exactly like a list but with different performance characteristics, and a sorteddict works just like a dict but keeps the keys sorted.</div>
</div><br>-- <br>Daniel Stutzbach<br>