Customizing sequence types

[Terry Reedy]

Mr.SpOOn wrote:
> On Sun, Nov 16, 2008 at 7:15 PM, Arnaud Delobelle

>> You should probably use the `bisect` module
>> (http://docs.python.org/library/bisect.html) for searching and
>> inserting into the list as it takes advantage of and ensures that the
>> list keeps sorted. It also means that __contains__ and some other
>> operations become O(log N) rather than O(N).
> 
> This seems good too, but I'd always have to check the presence of an
> element before inserting a new one and it's still not clear to me how
> to do it.

Read the doc on the bisect module.  The first or second function is what 
you need.  If you read bisect.py in /Lib, you will discover that only 
two of the 6 possible comparisons are used, so you only need to define 
those two if you want.

The choice between using set and sorted versus list and bisect depends 
on how frequently you do which operations.