# Sorted Set

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 set implementations:

- `SortedSet`

# SortedSet

class `sortedcontainers.``SortedSet`(iterable=None, key=None)

  Bases: `collections.abc.MutableSet`, `collections.abc.Sequence`

  Sorted set is a sorted mutable set.

  Sorted set values are maintained in sorted order. The design of sorted set is simple: sorted set uses a set for set-operations and maintains a sorted list of values.

  Sorted set values must be hashable and comparable. The hash and total ordering of values must not change while they are stored in the sorted set.

  Mutable set methods:

  - `SortedSet.__contains__()`
  - `SortedSet.__iter__()`
  - `SortedSet.__len__()`
  - `SortedSet.add()`
  - `SortedSet.discard()`

  Sequence methods:

  - `SortedSet.__getitem__()`
  - `SortedSet.__delitem__()`
  - `SortedSet.__reversed__()`

  Methods for removing values:

  - `SortedSet.clear()`
  - `SortedSet.pop()`
  - `SortedSet.remove()`

  Set-operation methods:

  - `SortedSet.difference()`
  - `SortedSet.difference_update()`
  - `SortedSet.intersection()`
  - `SortedSet.intersection_update()`
  - `SortedSet.symmetric_difference()`
  - `SortedSet.symmetric_difference_update()`
  - `SortedSet.union()`
  - `SortedSet.update()`

  Methods for miscellany:

  - `SortedSet.copy()`
  - `SortedSet.count()`
  - `SortedSet.__repr__()`
  - `SortedSet._check()`

  Sorted list methods available:

  - `SortedList.bisect_left()`
  - `SortedList.bisect_right()`
  - `SortedList.index()`
  - `SortedList.irange()`
  - `SortedList.islice()`
  - `SortedList._reset()`

  Additional sorted list methods available, if key-function used:

  - `SortedKeyList.bisect_key_left()`
  - `SortedKeyList.bisect_key_right()`
  - `SortedKeyList.irange_key()`

  Sorted set comparisons use subset and superset relations. Two sorted sets are equal if and only if every element of each sorted set is contained in the other (each is a subset of the other). A sorted set is less than another sorted set if and only if the first sorted set is a proper subset of the second sorted set (is a subset, but is not equal). A sorted set is greater than another sorted set if and only if the first sorted set is a proper superset of the second sorted set (is a superset, but is not equal).

  `__init__`(iterable=None, key=None)

    Initialize sorted set instance.

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

    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, none, compares values directly.

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

        >>> ss = SortedSet([3, 1, 2, 5, 4])
        >>> ss
        SortedSet([1, 2, 3, 4, 5])
        >>> from operator import neg
        >>> ss = SortedSet([3, 1, 2, 5, 4], neg)
        >>> ss
        SortedSet([5, 4, 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.

    Sorted set compares values directly when the key function is none.

  `__contains__`(value)

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

    `ss.__contains__(value)` <==> `value in ss`

    Runtime complexity: O(1)

        >>> ss = SortedSet([1, 2, 3, 4, 5])
        >>> 3 in ss
        True

    Parameters: | value – search for value in sorted set
    Returns: | true if value in sorted set

  `__iter__`()

    Return an iterator over the sorted set.

    `ss.__iter__()` <==> `iter(ss)`

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

  `__len__`()

    Return the size of the sorted set.

    `ss.__len__()` <==> `len(ss)`

    Returns: | size of sorted set

  `add`(value)

    Add value to sorted set.

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

        >>> ss = SortedSet()
        >>> ss.add(3)
        >>> ss.add(1)
        >>> ss.add(2)
        >>> ss
        SortedSet([1, 2, 3])

    Parameters: | value – value to add to sorted set

  `discard`(value)

    Remove value from sorted set if it is a member.

    If value is not a member, do nothing.

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

        >>> ss = SortedSet([1, 2, 3, 4, 5])
        >>> ss.discard(5)
        >>> ss.discard(0)
        >>> ss == set([1, 2, 3, 4])
        True

    Parameters: | value – value to discard from sorted set

  `__getitem__`(index)

    Lookup value at index in sorted set.

    `ss.__getitem__(index)` <==> `ss[index]`

    Supports slicing.

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

        >>> ss = SortedSet('abcde')
        >>> ss[2]
        'c'
        >>> ss[-1]
        'e'
        >>> ss[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 set.

    `ss.__delitem__(index)` <==> `del ss[index]`

    Supports slicing.

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

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

    Parameters: | index – integer or slice for indexing
    Raises: | IndexError – if index out of range

  `__reversed__`()

    Return a reverse iterator over the sorted set.

    `ss.__reversed__()` <==> `reversed(ss)`

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

  `clear`()

    Remove all values from sorted set.

    Runtime complexity: O(n)

  `pop`(index=-1)

    Remove and return value at index in sorted set.

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

    Negative indices are supported.

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

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

    Parameters: | index (int) – index of value (default -1)
    Returns: | value
    Raises: | IndexError – if index is out of range

  `remove`(value)

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

    If value is not a member, raise `KeyError`.

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

        >>> ss = SortedSet([1, 2, 3, 4, 5])
        >>> ss.remove(5)
        >>> ss == set([1, 2, 3, 4])
        True
        >>> ss.remove(0)
        Traceback (most recent call last):
          ...
        KeyError: 0

    Parameters: | value – value to remove from sorted set
    Raises: | KeyError – if value is not in sorted set

  `difference`(*iterables)

    Return the difference of two or more sets as a new sorted set.

    The difference method also corresponds to operator `-`.

    `ss.__sub__(iterable)` <==> `ss - iterable`

    The difference is all values that are in this sorted set but not the other iterables.

        >>> ss = SortedSet([1, 2, 3, 4, 5])
        >>> ss.difference([4, 5, 6, 7])
        SortedSet([1, 2, 3])

    Parameters: | iterables – iterable arguments
    Returns: | new sorted set

  `difference_update`(*iterables)

    Remove all values of iterables from this sorted set.

    The difference_update method also corresponds to operator `-=`.

    `ss.__isub__(iterable)` <==> `ss -= iterable`

        >>> ss = SortedSet([1, 2, 3, 4, 5])
        >>> _ = ss.difference_update([4, 5, 6, 7])
        >>> ss
        SortedSet([1, 2, 3])

    Parameters: | iterables – iterable arguments
    Returns: | itself

  `intersection`(*iterables)

    Return the intersection of two or more sets as a new sorted set.

    The intersection method also corresponds to operator `&`.

    `ss.__and__(iterable)` <==> `ss & iterable`

    The intersection is all values that are in this sorted set and each of the other iterables.

        >>> ss = SortedSet([1, 2, 3, 4, 5])
        >>> ss.intersection([4, 5, 6, 7])
        SortedSet([4, 5])

    Parameters: | iterables – iterable arguments
    Returns: | new sorted set

  `intersection_update`(*iterables)

    Update the sorted set with the intersection of iterables.

    The intersection_update method also corresponds to operator `&=`.

    `ss.__iand__(iterable)` <==> `ss &= iterable`

    Keep only values found in itself and all iterables.

        >>> ss = SortedSet([1, 2, 3, 4, 5])
        >>> _ = ss.intersection_update([4, 5, 6, 7])
        >>> ss
        SortedSet([4, 5])

    Parameters: | iterables – iterable arguments
    Returns: | itself

  `symmetric_difference`(other)

    Return the symmetric difference with other as a new sorted set.

    The symmetric_difference method also corresponds to operator `^`.

    `ss.__xor__(other)` <==> `ss ^ other`

    The symmetric difference is all values tha are in exactly one of the sets.

        >>> ss = SortedSet([1, 2, 3, 4, 5])
        >>> ss.symmetric_difference([4, 5, 6, 7])
        SortedSet([1, 2, 3, 6, 7])

    Parameters: | other – other iterable
    Returns: | new sorted set

  `symmetric_difference_update`(other)

    Update the sorted set with the symmetric difference with other.

    The symmetric_difference_update method also corresponds to operator `^=`.

    `ss.__ixor__(other)` <==> `ss ^= other`

    Keep only values found in exactly one of itself and other.

        >>> ss = SortedSet([1, 2, 3, 4, 5])
        >>> _ = ss.symmetric_difference_update([4, 5, 6, 7])
        >>> ss
        SortedSet([1, 2, 3, 6, 7])

    Parameters: | other – other iterable
    Returns: | itself

  `union`(*iterables)

    Return new sorted set with values from itself and all iterables.

    The union method also corresponds to operator `|`.

    `ss.__or__(iterable)` <==> `ss | iterable`

        >>> ss = SortedSet([1, 2, 3, 4, 5])
        >>> ss.union([4, 5, 6, 7])
        SortedSet([1, 2, 3, 4, 5, 6, 7])

    Parameters: | iterables – iterable arguments
    Returns: | new sorted set

  `update`(*iterables)

    Update the sorted set adding values from all iterables.

    The update method also corresponds to operator `|=`.

    `ss.__ior__(iterable)` <==> `ss |= iterable`

        >>> ss = SortedSet([1, 2, 3, 4, 5])
        >>> _ = ss.update([4, 5, 6, 7])
        >>> ss
        SortedSet([1, 2, 3, 4, 5, 6, 7])

    Parameters: | iterables – iterable arguments
    Returns: | itself

  `copy`()

    Return a shallow copy of the sorted set.

    Runtime complexity: O(n)

    Returns: | new sorted set

  `count`(value)

    Return number of occurrences of value in the sorted set.

    Runtime complexity: O(1)

        >>> ss = SortedSet([1, 2, 3, 4, 5])
        >>> ss.count(3)
        1

    Parameters: | value – value to count in sorted set
    Returns: | count

  `__repr__`()

    Return string representation of sorted set.

    `ss.__repr__()` <==> `repr(ss)`

    Returns: | string representation

  `_check`()

    Check invariants of sorted set.

    Runtime complexity: O(n)