[Python-ideas] Optional key to `bisect`'s functions?

[Daniel Stutzbach]

On Wed, Feb 8, 2012 at 4:25 PM, Guido van Rossum <guido at python.org> wrote:

> Also note that "many times" is actually O(log N) per insertion, which
> isn't so bad. The main use case for bisect() is to manage a list that sees
> updates *and* iterations -- otherwise building the list unsorted and
> sorting it at the end would make more sense. The key= option provides a
> balance between the cost/elegance for updates and for iterations.
>

Maintaining a sorted list using Python's list type is a trap.  The bisect
is O(log n), but insertion and deletion are still O(n).

A SortedList class that provides O(log n) insertions is useful from time to
time.  There are several existing implementations available (I wrote one of
them, on top of my blist type), each with their pros and cons.

-- 
Daniel Stutzbach
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20120209/cfe76a42/attachment.html>