sortedcontainers是一个用pure-python实现的拓展库，其内有SortedList、SortedDict、SortedSet等等，可以直接在力扣中使用

本文摘抄、总结于官方文档：http://www.grantjenks.com/docs/sortedcontainers/

Instruction

Sorted Containers is an Apache2 licensed sorted collections library, written in pure-Python, and fast as C-extensions.

Python’s standard library is great until you need a sorted collections type. Many will attest that you can get really far without one, but the moment you really need a sorted list, sorted dict, or sorted set, you’re faced with a dozen different implementations, most using C-extensions without great documentation and benchmarking.

In Python, we can do better. And we can do it in pure-Python!

Quickstart

Installing Sorted Containers is simple with pip:

$ pip install sortedcontainers

You can access documentation in the interpreter with Python’s built-in help function. The help works on modules, classes and methods in Sorted Containers.

>>> import sortedcontainers
>>> help(sortedcontainers)
>>> from sortedcontainers import SortedDict
>>> help(SortedDict)
>>> help(SortedDict.popitem)

SortedList

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

• 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.

iterable

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

init & key

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

add(value)

时间复杂度近似O(logn)

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

update(iterable)

时间复杂度近似O(k*logn)

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

clear()

Remove all values from sorted list.

时间复杂度O(n)

discard(value)

Remove value from sorted list if it is a member.

If value is not a member, do nothing.

时间复杂度近似O(logn)

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

remove(value)

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

If value is not a member, raise ValueError.

时间复杂度近似O(logn)

>>> 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

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.

时间复杂度近似O(logn)

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

bisect_left(value)

Similar to the bisect module in the standard library.

时间复杂度近似O(logn)

同理bisect_right(value)

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

count(value)

时间复杂度近似O(logn)

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

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

Return first index of value in sorted list.

Raise ValueError if value is not present.

时间复杂度近似O(logn)

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

SortedDict

class sortedcontainers.SortedDict(*args, **kwargs)

• Sorted dict is a sorted mutable mapping.
• Sorted dict keys are maintained in sorted order. The design of sorted dict is simple: sorted dict inherits from dict to store items and maintains a sorted list of keys.
• Sorted dict keys must be hashable and comparable. The hash and total ordering of keys must not change while they are stored in the sorted dict.

init

Sorted dict keys must be hashable, per the requirement for Python’s dictionaries. Keys (or the result of the key-function) must also be comparable, per the requirement for sorted lists.

>>> d = {'alpha': 1, 'beta': 2}
>>> SortedDict([('alpha', 1), ('beta', 2)]) == d
True
>>> SortedDict({'alpha': 1, 'beta': 2}) == d
True
>>> SortedDict(alpha=1, beta=2) == d
True

setdefault(key, default=None)

时间复杂度近似O(logn)

>>> sd = SortedDict()
>>> sd.setdefault('a', 1)
1
>>> sd.setdefault('a', 10)
1
>>> sd
SortedDict({'a': 1})

clear()

Remove all values from sorted dict.

时间复杂度O(n)

pop(key, default=)

Remove and return value for item identified by key.

If the key is not found then return default if given. If default is not given then raise KeyError.

时间复杂度近似O(logn)

>>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
>>> sd.pop('c')
3
>>> sd.pop('z', 26)
26
>>> sd.pop('y')
Traceback (most recent call last):
  ...
KeyError: 'y'

popitem(index=-1)

Remove and return (key, value) pair at index from sorted dict.

Optional argument index defaults to -1, the last item in the sorted dict. Specify index=0 for the first item in the sorted dict.

If the sorted dict is empty, raises KeyError.

If the index is out of range, raises IndexError.

时间复杂度近似O(logn)

>>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
>>> sd.popitem()
('c', 3)
>>> sd.popitem(0)
('a', 1)
>>> sd.popitem(100)
Traceback (most recent call last):
  ...
IndexError: list index out of range

peekitem(index=-1)

Return (key, value) pair at index in sorted dict.

Optional argument index defaults to -1, the last item in the sorted dict. Specify index=0 for the first item in the sorted dict.

Unlike [SortedDict.popitem()] the sorted dict is not modified.

If the index is out of range, raises IndexError.

时间复杂度近似O(logn)

>>> sd = SortedDict({'a': 1, 'b': 2, 'c': 3})
>>> sd.peekitem()
('c', 3)
>>> sd.peekitem(0)
('a', 1)
>>> sd.peekitem(100)
Traceback (most recent call last):
  ...
IndexError: list index out of range

SortedSet

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

• 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.

init

__init__(iterable=None, key=None)

>>> 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>)

add(value)

Add value to sorted set.

时间复杂度近似O(logn)

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

discard(value)

Remove value from sorted set if it is a member.

If value is not a member, do nothing.

时间复杂度近似O(logn)

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

remove(value)

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

If value is not a member, raise KeyError.

时间复杂度近似O(logn)

>>> 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

clear()

Remove all values from sorted set.

时间复杂度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.

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

count(value)

Return number of occurrences of value in the sorted set.

时间复杂度O(1)

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

difference(*iterables)

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

The difference method also corresponds to operator -.

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

difference_update(*iterables)

Remove all values of iterables from this sorted set.

The difference_update method also corresponds to operator -=.

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

intersection(*iterables)

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

The intersection method also corresponds to operator &.

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

intersection_update(*iterables)

The intersection_update method also corresponds to operator &=.

symmetric_difference(other)

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

The symmetric_difference method also corresponds to operator ^.

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

symmetric_difference_update(other)

The symmetric_difference_update method also corresponds to operator ^=.

union(*iterables)

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

The union method also corresponds to operator |.

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

update(*iterables)

Update the sorted set adding values from all iterables.

The update method also corresponds to operator |=.

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