# 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: `collections.abc.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 with 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: `sortedcontainers.sortedlist.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 with 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 `sortedcontainers.sortedlist.SortedKeyList`