What would you guys think about adding a class that uses bisect internally so that the keyfunc() never gets called more than once per key?  This could be added to the docs as a cut-and-pastable recipe or it could be added to the module directly:

sd = SortedCollection(iterable, key=keyfunc)
s[i]                  --> getitem at position i
len(s)                --> length
sd.insert_left(item)  --> None
sd.insert_right(item) --> None
sd.find_left(key)     --> item
sd.find_right(key)    --> item
sd.keyfunc            --> the key function 
list(sd)              --> sorted list of items
list(reversed(sd))    --> reverse sorted list of items
s.clear()


The implementation would follow this pattern:

 def insert_left(self, item):
   key = self._keyfunc(item)
   i = bisect_left(self._keys, key)
   self._keys.insert(i, key)
   self._items.insert(i, item)

 def find_left(self, key):
   i = bisect_left(self._keys, key)
   return self._items[i]

 def __iter__(self):
   return iter(self._items)

 def __getitem__(self, i):
   return self._items[i]