sortedcontainers.txt

sortedcontainer:
	tree like structure




# SortedList:

python add(value) : A function that takes one element as parameter and inserts it into the list by maintaining sorted order. Runtime Complexity: O(log(n))

python update(iterable): A function that takes an iterable as input and updates the SortedList adding all the values from the iterable Runtime complexity: O(k*log(n)).

python clear(): Remove all values from sorted list. Runtime complexity: O(n).

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


from sortedcontainers import SortedList
sl = SortedList(['e', 'a', 'c', 'd', 'b'])
sl.add('aa')

print(sl)
SortedList(['a', 'aa', 'b', 'c', 'd', 'e'])

sl*=2
SortedList(['a', 'a', 'aa', 'aa', 'b', 'b', 'c', 'c', 'd', 'd', 'e', 'e'])

sl.count('a')
2

sl.discard('a') ## only discard ONE 'a'

elements = [10, 9, 8, 7, 6]  
sl.update(elements)



# SortedSet
add(value) : A function that takes one element as parameter and inserts it into the set by maintaining sorted order. Runtime Complexity: O(log(n))

clear(): Remove all values from sorted set. Runtime complexity: O(n)

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

from sortedcontainers import SortedSet
ss = SortedSet('abracadabra')
ss
SortedSet(['a', 'b', 'c', 'd', 'r'])
ss.bisect_left('c')
2


# SortedDict
setdefault(key, default = None) : Return value for item identified by key in sorted dict. If key is in the sorted dict then return its value. If key is not in the sorted dict then insert key with value default and return default. Runtime Complexity: O(log(n))

clear(): Remove all values from sorted dict. Runtime complexity: O(n)

get(key, default): Return the value for key if key is in the dictionary, else default.


from sortedcontainers import SortedDict
sd = SortedDict({'c': 3, 'a': 1, 'b': 2})
sd
SortedDict({'a': 1, 'b': 2, 'c': 3})

sd.popitem(index=-1)
('c', 3)

sd.setdefault('g')
>>> sd
SortedDict({'a': 8, 'aa': 2, 'b': 2, 'c': 3, 'g': None})

>>> sd.setdefault('a')
8