Insert a custom object in a sorted list

Question

I implemented an object with a numerical attribute. I want to keep a list of those objects sorted according to that attribute, without need to run a sort method at each insertion. I took a look to bisect module, but I do not know if I can use it also with an object. What is the best way to do that?

Have you looked into http://code.activestate.com/recipes/577197-sortedcollection/. This recipe is linked in bisect module itself. — sagarchalise, Nov 10 '14 at 09:41
Do you actually need the entire list to be sorted, or do you just want to easily access the smallest (or largest)? If so you might want to consider using a heap instead (see Python's heapq module). — Duncan, Nov 10 '14 at 09:48
Possible duplicate of [How to use bisect.insort\_left with a key?](https://stackoverflow.com/questions/27672494/how-to-use-bisect-insort-left-with-a-key) — Ciro Santilli OurBigBook.com, Nov 24 '17 at 16:43

score 25 · Accepted Answer · answered Nov 10 '14 at 09:48

You can do this for your custom object if you implement the __lt__ method, because this is what bisect will use to compare your object.

>>> class Foo(object):
...     def __init__(self, val):
...         self.prop = val # The value to compare
...     def __lt__(self, other):
...         return self.prop < other.prop
...     def __repr__(self):
...         return 'Foo({})'.format(self.prop)
...
>>> sorted_foos = sorted([Foo(7), Foo(1), Foo(3), Foo(9)])
>>> sorted_foos
[Foo(1), Foo(3), Foo(7), Foo(9)]
>>> bisect.insort_left(sorted_foos, Foo(2))
>>> sorted_foos
[Foo(1), Foo(2), Foo(3), Foo(7), Foo(9)]

score 3 · Answer 2 · answered Nov 10 '14 at 09:53

You may provide a custom implementation of list that override the insert method that make a binary insertion. hose the time to insert an element come from O(1) to O(log2(n)) where n is the number of element in the list.

You may also use an already implemented implementation such as sorted containers [http://www.grantjenks.com/docs/sortedcontainers/].

Anyway, whatever solution you use, you MUST implement comparators methods on your objects ( greater than (__gt__) and lesser than (__lt__) ) that use this numerical attribute to define an order on your objects. Without order, there is no sorting possible.

Here an example :

from sortedcontainers import SortedList

class OrderedObject():

    def __init__(self, id, value):
        self.id = id
        self.value = value

    def __gt__(self, other):
        if not isinstance(other,OrderedObject):
            raise Exception("OrderedObject are only comparable to OrderedObject, not to {0}".format(type(other)))
        else:
            return self.value.__gt__(other.value)

    def __lt__(self, other):
        if not isinstance(other,OrderedObject):
            raise Exception("OrderedObject are only comparable to OrderedObject, not to {0}".format(type(other)))
        else:
            return self.value.__lt__(other.value)

    def __repr__(self):
        return "<OrderedObject({0}, {1})>".format(self.id, self.value)

if __name__ == "__main__":
    a = OrderedObject('foo', 1)
    b = OrderedObject('bar', 2)
    c = OrderedObject('-*-', 3)

    mylist = [b,c,a]
    print(mylist)
    mylist.sort()
    print(mylist)

    mylist = SortedList()
    mylist.add(b)
    mylist.add(c)
    mylist.add(a)
    print(mylist)

This give the following results :

[<OrderedObject(bar, 2)>, <OrderedObject(-*-, 3)>, <OrderedObject(foo, 1)>]
[<OrderedObject(foo, 1)>, <OrderedObject(bar, 2)>, <OrderedObject(-*-, 3)>]
SortedList([<OrderedObject(foo, 1)>, <OrderedObject(bar, 2)>, <OrderedObject(-*-, 3)>])

NB : I'm not affiliated to sorted container library in any way

score 1 · Answer 3 · answered Nov 10 '14 at 09:42

1

bisect doesn't support keys; read this: http://bugs.python.org/issue4356 and they don't plan to support that either for performance reasons. But I think it should work if you use __gt__, __lt__ etc.

answered Nov 10 '14 at 09:42

adarsh

6,738
4
30
52

bisect officially supports keys from 3.10: https://docs.python.org/3/library/bisect.html – ciurlaro Feb 15 '22 at 10:21

score 0 · Answer 4 · answered Nov 10 '14 at 09:43

You can decrease amount of sorts by:

Introducing special variable that will show you if your list is sorted AND
Sort list when you need to get data from it if your special variable tells you that your list has been modified.

Modification for your special variable should be performed on inserting new data.

Insert a custom object in a sorted list

4 Answers4