<div class="gmail_quote">On Thu, Jan 21, 2010 at 2:27 AM, Raymond Hettinger <span dir="ltr"><<a href="mailto:python@rcn.com">python@rcn.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Using an underlying list to track sorted items<br>
means that insertion and deletion take O(n) time.<br>
That could be reduced to O(log n) time by using<br>
a blist or skiplist as the underlying structure<br>
for maintaining a sort.<br></blockquote></div><br>Indeed.  In fact, blist 1.1 (to be released within a month or so) will include sorteddict, sortedset, sortedlist, weaksortedset, and weaksortedlist types.<br><blockquote style="margin: 1.5em 0pt;">
--<br>
Daniel Stutzbach, Ph.D.<br>
President, <a href="http://stutzbachenterprises.com">Stutzbach Enterprises, LLC</a>
</blockquote>