SortedList

class SortedList(iterable=None, load=1000)

A SortedList provides most of the same methods as a list, but keeps the items in sorted order. To add an element to the SortedList, use add. To add several elements, use update. To remove an element, use discard, remove, or del L[i].

An optional iterable provides an initial series of items to populate the SortedList.

An optional 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 elements. Good practice is to use a value that is the square or 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 for more information.

SortedList implements the MutableSequence Abstract Base Class type.

x in L

Return True if and only if x is an element in the list.

Return type:bool
del L[i]

Remove the element located at index i from the list.

del L[i:j]

Remove the elements from i to j from the list. Also note that step is supported in slice syntax.

L == L2, L != L2, L < L2, L <= L2, L > L2, L >= L2

Compare two lists. For full details see Comparisons in the Python language reference.

Return type:bool
L[i]

Return the element at position i.

Return type:item
L[i:j]

Return a new list containing the elements from i to j. Also note that step is supported in slice syntax.

Return type:list
L *= k

Increase the length of the list by a factor of k, by inserting k-1 additional shallow copies of each item in the list.

iter(L)

Create an iterator over the list.

Return type:iterator
len(L)

Return the number of elements in the list.

Return type:int
L * k or k * L

Return a new sorted list containing k shallow copies of each item in L.

Return type:SortedList
L + k

Return a new sorted list containing all the elements in L and k. Elements in k do not need to be properly ordered with respect to L.

Return type:SortedList
L += k

Update L to include all values in k. Elements in k do not need to be properly ordered with respect to L.

reversed(L)

Create an iterator to traverse the list in reverse.

Return type:iterator
L[i] = x

Replace the item at position i of L with x. Supports slice notation. Raises a ValueError if the sort order would be violated. When used with a slice and iterable, the ValueError is raised before the list is mutated if the sort order would be violated by the operation.

L[i:j] = iterable

Replace the items at positions i through j with the contents of iterable. Also note that step is supported in slice syntax.

L.add(value)

Add the element value to the list.

L.bisect_left(value)

Similar to the bisect module in the standard library, this returns an appropriate index to insert value in L. If value is already present in L, the insertion point will be before (to the left of) any existing entries.

L.bisect(value)

Same as bisect_right.

L.bisect_right(value)

Same as bisect_left, but if value is already present in L, the insertion point will be after (to the right of) any existing entries.

L.count(value)

Return the number of occurrences of value in the list.

Return type:int
L.copy()

Return a shallow copy of the sorted list.

Return type:SortedList
L.discard(value)

Remove the first occurrence of value. If value is not a member, does nothing.

L.index(value[, start[, stop]])

Return the smallest k such that L[k] =  = x and i <  = k < j . Raises ValueError if value is not present. stop defaults to the end of the list. start defaults to the beginning. Negative indexes are supported, as for slice indices.

Return type:int
L.pop([index])

Remove and return item at index (default last). Raises IndexError if list is empty or index is out of range. Negative indexes are supported, as for slice indices.

Return type:item
L.remove(value)

Remove first occurrence of value. Raises ValueError if value is not present.

L.update(iterable)

Grow the list by inserting all elements from the iterable.

L.clear()

Remove all the elements from the list.

L.append(value)

Append the element value to the list. Raises a ValueError if the value would violate the sort order.

L.extend(iterable)

Extend the list by appending all elements from the iterable. Raises a ValueError if the sort order would be violated.

L.insert(index, value)

Insert the element value into the list at index. Raises a ValueError if the value at index would violate the sort order.

L.as_list()

Very efficiently convert the SortedList to a class:list.

Return type:list

SortedContainers provides sorted container types, written in pure-Python and fast as C-extensions.

Give Support

If you or your organization uses SortedContainers, consider financial support:

Give to Sorted Containers

Related Topics

This Page