Sorted List

Sorted Containers is an Apache2 licensed Python sorted collections library, written in pure-Python, and fast as C-extensions. The introduction is the best way to get started.

Sorted list implementations:

• SortedList

• SortedKeyList

SortedList

class sortedcontainers.SortedList(iterable=None, key=None)

Bases: MutableSequence

Sorted list is a sorted mutable sequence.

Sorted list values are maintained in sorted order.

Sorted list values must be comparable. The total ordering of values must not change while they are stored in the sorted list.

Methods for adding values:

• SortedList.add()

• SortedList.update()

• SortedList.__add__()

• SortedList.__iadd__()

• SortedList.__mul__()

• SortedList.__imul__()

Methods for removing values:

• SortedList.clear()

• SortedList.discard()

• SortedList.remove()

• SortedList.pop()

• SortedList.__delitem__()

Methods for looking up values:

• SortedList.bisect_left()

• SortedList.bisect_right()

• SortedList.count()

• SortedList.index()

• SortedList.__contains__()

• SortedList.__getitem__()

Methods for iterating values:

• SortedList.irange()

• SortedList.islice()

• SortedList.__iter__()

• SortedList.__reversed__()

Methods for miscellany:

• SortedList.copy()

• SortedList.__len__()

• SortedList.__repr__()

• SortedList._check()

• SortedList._reset()

Sorted lists use lexicographical ordering semantics when compared to other sequences.

Some methods of mutable sequences are not supported and will raise not-implemented error.

static __new__(cls, iterable=None, key=None)

Create new sorted list or sorted-key list instance.

Optional key-function argument will return an instance of subtype SortedKeyList.

>>> sl = SortedList()
>>> isinstance(sl, SortedList)
True
>>> sl = SortedList(key=lambda x: -x)
>>> isinstance(sl, SortedList)
True
>>> isinstance(sl, SortedKeyList)
True

Parameters:

• iterable – initial values (optional)

• key – function used to extract comparison key (optional)

Returns:

sorted list or sorted-key list instance

__init__(iterable=None, key=None)

Initialize sorted list instance.

Optional iterable argument provides an initial iterable of values to initialize the sorted list.

Runtime complexity: O(n*log(n))

>>> sl = SortedList()
>>> sl
SortedList([])
>>> sl = SortedList([3, 1, 2, 5, 4])
>>> sl
SortedList([1, 2, 3, 4, 5])

Parameters:

iterable – initial values (optional)

add(value)

Add value to sorted list.

Runtime complexity: O(log(n)) – approximate.

>>> sl = SortedList()
>>> sl.add(3)
>>> sl.add(1)
>>> sl.add(2)
>>> sl
SortedList([1, 2, 3])

Parameters:

value – value to add to sorted list

update(iterable)

Update sorted list by adding all values from iterable.

Runtime complexity: O(k*log(n)) – approximate.

>>> sl = SortedList()
>>> sl.update([3, 1, 2])
>>> sl
SortedList([1, 2, 3])

Parameters:

iterable – iterable of values to add

clear()

Remove all values from sorted list.

Runtime complexity: O(n)

discard(value)

Remove value from sorted list if it is a member.

If value is not a member, do nothing.

Runtime complexity: O(log(n)) – approximate.

>>> sl = SortedList([1, 2, 3, 4, 5])
>>> sl.discard(5)
>>> sl.discard(0)
>>> sl == [1, 2, 3, 4]
True

Parameters:

value – value to discard from sorted list

remove(value)

Remove value from sorted list; value must be a member.

If value is not a member, raise ValueError.

Runtime complexity: O(log(n)) – approximate.

>>> sl = SortedList([1, 2, 3, 4, 5])
>>> sl.remove(5)
>>> sl == [1, 2, 3, 4]
True
>>> sl.remove(0)
Traceback (most recent call last):
  ...
ValueError: 0 not in list

Parameters:

value – value to remove from sorted list

Raises:

ValueError – if value is not in sorted list

pop(index=-1)

Remove and return value at index in sorted list.

Raise IndexError if the sorted list is empty or index is out of range.

Negative indices are supported.

Runtime complexity: O(log(n)) – approximate.

>>> sl = SortedList('abcde')
>>> sl.pop()
'e'
>>> sl.pop(2)
'c'
>>> sl
SortedList(['a', 'b', 'd'])

Parameters:

index (int) – index of value (default -1)

Returns:

value

Raises:

IndexError – if index is out of range

bisect_left(value)

Return an index to insert value in the sorted list.

If the value is already present, the insertion point will be before (to the left of) any existing values.

Similar to the bisect module in the standard library.

Runtime complexity: O(log(n)) – approximate.

>>> sl = SortedList([10, 11, 12, 13, 14])
>>> sl.bisect_left(12)
2

Parameters:

value – insertion index of value in sorted list

Returns:

index

bisect_right(value)

Return an index to insert value in the sorted list.

Similar to bisect_left, but if value is already present, the insertion point will be after (to the right of) any existing values.

Similar to the bisect module in the standard library.

Runtime complexity: O(log(n)) – approximate.

>>> sl = SortedList([10, 11, 12, 13, 14])
>>> sl.bisect_right(12)
3

Parameters:

value – insertion index of value in sorted list

Returns:

index

count(value)

Return number of occurrences of value in the sorted list.

Runtime complexity: O(log(n)) – approximate.

>>> sl = SortedList([1, 2, 2, 3, 3, 3, 4, 4, 4, 4])
>>> sl.count(3)
3

Parameters:

value – value to count in sorted list

Returns:

count

index(value, start=None, stop=None)

Return first index of value in sorted list.

Raise ValueError if value is not present.

Index must be between start and stop for the value to be considered present. The default value, None, for start and stop indicate the beginning and end of the sorted list.

Negative indices are supported.

Runtime complexity: O(log(n)) – approximate.

>>> sl = SortedList('abcde')
>>> sl.index('d')
3
>>> sl.index('z')
Traceback (most recent call last):
  ...
ValueError: 'z' is not in list

Parameters:

• value – value in sorted list

• start (int) – start index (default None, start of sorted list)

• stop (int) – stop index (default None, end of sorted list)

Returns:

index of value

Raises:

ValueError – if value is not present

irange(minimum=None, maximum=None, inclusive=(True, True), reverse=False)

Create an iterator of values between minimum and maximum.

Both minimum and maximum default to None which is automatically inclusive of the beginning and end of the sorted list.

The argument inclusive is a pair of booleans that indicates whether the minimum and maximum ought to be included in the range, respectively. The default is (True, True) such that the range is inclusive of both minimum and maximum.

When reverse is True the values are yielded from the iterator in reverse order; reverse defaults to False.

>>> sl = SortedList('abcdefghij')
>>> it = sl.irange('c', 'f')
>>> list(it)
['c', 'd', 'e', 'f']

Parameters:

• minimum – minimum value to start iterating

• maximum – maximum value to stop iterating

• inclusive – pair of booleans

• reverse (bool) – yield values in reverse order

Returns:

iterator

islice(start=None, stop=None, reverse=False)

Return an iterator that slices sorted list from start to stop.

The start and stop index are treated inclusive and exclusive, respectively.

Both start and stop default to None which is automatically inclusive of the beginning and end of the sorted list.

When reverse is True the values are yielded from the iterator in reverse order; reverse defaults to False.

>>> sl = SortedList('abcdefghij')
>>> it = sl.islice(2, 6)
>>> list(it)
['c', 'd', 'e', 'f']

Parameters:

• start (int) – start index (inclusive)

• stop (int) – stop index (exclusive)

• reverse (bool) – yield values in reverse order

Returns:

iterator

__iter__()

Return an iterator over the sorted list.

sl.__iter__() <==> iter(sl)

Iterating the sorted list while adding or deleting values may raise a RuntimeError or fail to iterate over all values.

__reversed__()

Return a reverse iterator over the sorted list.

sl.__reversed__() <==> reversed(sl)

Iterating the sorted list while adding or deleting values may raise a RuntimeError or fail to iterate over all values.

__contains__(value)

Return true if value is an element of the sorted list.

sl.__contains__(value) <==> value in sl

Runtime complexity: O(log(n))

>>> sl = SortedList([1, 2, 3, 4, 5])
>>> 3 in sl
True

Parameters:

value – search for value in sorted list

Returns:

true if value in sorted list

__getitem__(index)

Lookup value at index in sorted list.

sl.__getitem__(index) <==> sl[index]

Supports slicing.

Runtime complexity: O(log(n)) – approximate.

>>> sl = SortedList('abcde')
>>> sl[1]
'b'
>>> sl[-1]
'e'
>>> sl[2:5]
['c', 'd', 'e']

Parameters:

index – integer or slice for indexing

Returns:

value or list of values

Raises:

IndexError – if index out of range

__delitem__(index)

Remove value at index from sorted list.

sl.__delitem__(index) <==> del sl[index]

Supports slicing.

Runtime complexity: O(log(n)) – approximate.

>>> sl = SortedList('abcde')
>>> del sl[2]
>>> sl
SortedList(['a', 'b', 'd', 'e'])
>>> del sl[:2]
>>> sl
SortedList(['d', 'e'])

Parameters:

index – integer or slice for indexing

Raises:

IndexError – if index out of range

__add__(other)

Return new sorted list containing all values in both sequences.

sl.__add__(other) <==> sl + other

Values in other do not need to be in sorted order.

Runtime complexity: O(n*log(n))

>>> sl1 = SortedList('bat')
>>> sl2 = SortedList('cat')
>>> sl1 + sl2
SortedList(['a', 'a', 'b', 'c', 't', 't'])

Parameters:

other – other iterable

Returns:

new sorted list

__iadd__(other)

Update sorted list with values from other.

sl.__iadd__(other) <==> sl += other

Values in other do not need to be in sorted order.

Runtime complexity: O(k*log(n)) – approximate.

>>> sl = SortedList('bat')
>>> sl += 'cat'
>>> sl
SortedList(['a', 'a', 'b', 'c', 't', 't'])

Parameters:

other – other iterable

Returns:

existing sorted list

__mul__(num)

Return new sorted list with num shallow copies of values.

sl.__mul__(num) <==> sl * num

Runtime complexity: O(n*log(n))

>>> sl = SortedList('abc')
>>> sl * 3
SortedList(['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c'])

Parameters:

num (int) – count of shallow copies

Returns:

new sorted list

__imul__(num)

Update the sorted list with num shallow copies of values.

sl.__imul__(num) <==> sl *= num

Runtime complexity: O(n*log(n))

>>> sl = SortedList('abc')
>>> sl *= 3
>>> sl
SortedList(['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c'])

Parameters:

num (int) – count of shallow copies

Returns:

existing sorted list

__eq__(other)

Return true if and only if sorted list is equal to other.

sl.__eq__(other) <==> sl == other

Comparisons use lexicographical order as with sequences.

Runtime complexity: O(n)

Parameters:

other – other sequence

Returns:

true if sorted list is equal to other

__ne__(other)

Return true if and only if sorted list is not equal to other.

sl.__ne__(other) <==> sl != other

Comparisons use lexicographical order as with sequences.

Runtime complexity: O(n)

Parameters:

other – other sequence

Returns:

true if sorted list is not equal to other

__lt__(other)

Return true if and only if sorted list is less than other.

sl.__lt__(other) <==> sl < other

Comparisons use lexicographical order as with sequences.

Runtime complexity: O(n)

Parameters:

other – other sequence

Returns:

true if sorted list is less than other

__le__(other)

Return true if and only if sorted list is less than or equal to other.

sl.__le__(other) <==> sl <= other

Comparisons use lexicographical order as with sequences.

Runtime complexity: O(n)

Parameters:

other – other sequence

Returns:

true if sorted list is less than or equal to other

__gt__(other)

Return true if and only if sorted list is greater than other.

sl.__gt__(other) <==> sl > other

Comparisons use lexicographical order as with sequences.

Runtime complexity: O(n)

Parameters:

other – other sequence

Returns:

true if sorted list is greater than other

__ge__(other)

Return true if and only if sorted list is greater than or equal to other.

sl.__ge__(other) <==> sl >= other

Comparisons use lexicographical order as with sequences.

Runtime complexity: O(n)

Parameters:

other – other sequence

Returns:

true if sorted list is greater than or equal to other

copy()

Return a shallow copy of the sorted list.

Runtime complexity: O(n)

Returns:

new sorted list

__len__()

Return the size of the sorted list.

sl.__len__() <==> len(sl)

Returns:

size of sorted list

__repr__()

Return string representation of sorted list.

sl.__repr__() <==> repr(sl)

Returns:

string representation

_check()

Check invariants of sorted list.

Runtime complexity: O(n)

_reset(load)

Reset sorted list load factor.

The load specifies the load-factor of the list. The default load factor of 1000 works well for lists from tens to tens-of-millions of values. Good practice is to use a value that is the cube root of the list size. With billions of elements, the best load factor depends on your usage. It’s best to leave the load factor at the default until you start benchmarking.

See Implementation Details and Performance at Scale for more information.

Runtime complexity: O(n)

Parameters:

load (int) – load-factor for sorted list sublists

append(value)

Raise not-implemented error.

Implemented to override MutableSequence.append which provides an erroneous default implementation.

Raises:

NotImplementedError – use sl.add(value) instead

extend(values)

Raise not-implemented error.

Implemented to override MutableSequence.extend which provides an erroneous default implementation.

Raises:

NotImplementedError – use sl.update(values) instead

insert(index, value)

Raise not-implemented error.

Raises:

NotImplementedError – use sl.add(value) instead

reverse()

Raise not-implemented error.

Sorted list maintains values in ascending sort order. Values may not be reversed in-place.

Use reversed(sl) for an iterator over values in descending sort order.

Implemented to override MutableSequence.reverse which provides an erroneous default implementation.

Raises:

NotImplementedError – use reversed(sl) instead

__setitem__(index, value)

Raise not-implemented error.

sl.__setitem__(index, value) <==> sl[index] = value

Raises:

NotImplementedError – use del sl[index] and sl.add(value) instead

SortedKeyList

class sortedcontainers.SortedKeyList(iterable=None, key=<function identity>)

Bases: SortedList

Sorted-key list is a subtype of sorted list.

The sorted-key list maintains values in comparison order based on the result of a key function applied to every value.

All the same methods that are available in SortedList are also available in SortedKeyList.

Additional methods provided:

• SortedKeyList.key

• SortedKeyList.bisect_key_left()

• SortedKeyList.bisect_key_right()

• SortedKeyList.irange_key()

Some examples below use:

>>> from operator import neg
>>> neg
<built-in function neg>
>>> neg(1)
-1

__init__(iterable=None, key=<function identity>)

Initialize sorted-key list instance.

Optional iterable argument provides an initial iterable of values to initialize the sorted-key list.

Optional key argument defines a callable that, like the key argument to Python’s sorted function, extracts a comparison key from each value. The default is the identity function.

Runtime complexity: O(n*log(n))

>>> from operator import neg
>>> skl = SortedKeyList(key=neg)
>>> skl
SortedKeyList([], key=<built-in function neg>)
>>> skl = SortedKeyList([3, 1, 2], key=neg)
>>> skl
SortedKeyList([3, 2, 1], key=<built-in function neg>)

Parameters:

• iterable – initial values (optional)

• key – function used to extract comparison key (optional)

key

Function used to extract comparison key from values.

bisect_key_left(key)

Return an index to insert key in the sorted-key list.

If the key is already present, the insertion point will be before (to the left of) any existing keys.

Similar to the bisect module in the standard library.

Runtime complexity: O(log(n)) – approximate.

>>> from operator import neg
>>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg)
>>> skl.bisect_key_left(-1)
4

Parameters:

key – insertion index of key in sorted-key list

Returns:

index

bisect_key_right(key)

Return an index to insert key in the sorted-key list.

Similar to bisect_key_left, but if key is already present, the insertion point will be after (to the right of) any existing keys.

Similar to the bisect module in the standard library.

Runtime complexity: O(log(n)) – approximate.

>>> from operator import neg
>>> skl = SortedList([5, 4, 3, 2, 1], key=neg)
>>> skl.bisect_key_right(-1)
5

Parameters:

key – insertion index of key in sorted-key list

Returns:

index

irange_key(min_key=None, max_key=None, inclusive=(True, True), reverse=False)

Create an iterator of values between min_key and max_key.

Both min_key and max_key default to None which is automatically inclusive of the beginning and end of the sorted-key list.

The argument inclusive is a pair of booleans that indicates whether the minimum and maximum ought to be included in the range, respectively. The default is (True, True) such that the range is inclusive of both minimum and maximum.

When reverse is True the values are yielded from the iterator in reverse order; reverse defaults to False.

>>> from operator import neg
>>> skl = SortedKeyList([11, 12, 13, 14, 15], key=neg)
>>> it = skl.irange_key(-14, -12)
>>> list(it)
[14, 13, 12]

Parameters:

• min_key – minimum key to start iterating

• max_key – maximum key to stop iterating

• inclusive – pair of booleans

• reverse (bool) – yield values in reverse order

Returns:

iterator

sortedcontainers.SortedListWithKey

alias of SortedKeyList