Customizing sequence types

[Arnaud Delobelle]

Terry Reedy <tjreedy at udel.edu> writes:

> 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.

You can choose, but maybe you could use both?  Use a set for checking
membership and a list for checking order.  Keep them synchronized.

e.g.

class Hybrid(object):
    def __init__(self, val=[]):
        self.as_list = list(val)
        self.as_set = set(val)
    def __contains__(self, x):
        return x in self.as_set
    def append(self, x):
        if x not in self.as_set:
            self.as_set.add(x)
            self.as_list.append(x)
    def __iter__(self):
        return iter(self.as_list)
    # etc...

-- 
Arnaud