Quoting Raymond Hettinger <[EMAIL PROTECTED]>: > [Robert Bossy] > > I thought it would be useful if insort and consorts* could accept the > > same options than list.sort, especially key and cmp. > > If you're going to do many insertions or searches, wouldn't it be > *much* more efficient to store your keys in a separate array? > > The sort() function guarantees that it calls the key function exactly > once for each member of the list. With and bisect/insort, successive > searches can call the key function over and over again with the same > value.
I factored your remark into the code. I actually don't have any particular question about it, that's just an acknowledgment. Though I feel that if one uses the default key, then an awkward list of twins is stored... from operator import itemgetter def identity(x): return x class Bisect: def __init__(self, it, key=identity, cmp=cmp): self.lst = [ (key(x),x,) for x in it ] self.lst.sort(cmp=cmp, key=itemgetter(0)) self.key = key self.cmp = cmp def insort_right(self, x, lo = 0, hi = None): if hi is None: hi = len(self.lst) xk = self.key(x) while lo < hi: mid = (lo + hi) // 2 if self.cmp(xk, self.lst[mid][0]) < 0: hi = mid else: lo = mid + 1 self.lst.insert(lo, (kx,x,)) # skipped insort_left, bisect_right, bisect_left # also skipped the container methods __len__, __getitem__, __iter__ Cheers, RB -- http://mail.python.org/mailman/listinfo/python-list