Module sortedcontainers

Il permet de maintenir des listes triées et de rechercher très rapidement l'existence d'un élément dans une liste

SortedList : c'est l'ordre lexicographique qui est utilisé (numérique sur les valeurs numériques) :

from sortedcontainers import SortedList
l = SortedList()
l.add(3)
l.add(7)

on peut aussi l'utiliser avec des objets plus complexes :

from sortedcontainers import SortedList
l = SortedList()
l.add([5, 1])
l.add([3, 4])

renvoie SortedList([[3, 4], [5, 1]])

l.index([3, 4]) : renvoie l'index, ici 2 (exception si valeur n'existe pas).
l.count([3, 4]) : renvoie le nombre de valeurs qui sont [3, 4] (peut être 0 si valeur n'existe pas)
l.discard([4, 4]) : enlève la valeur si elle existe, sinon, ne fait rien. Si valeur est répétée, une seule est enlevée.
l.remove([4, 4]) : enlève la valeur. Si elle n'existe pas, il y a exception. Si valeur est répétée, une seule est enlevée.
l.bisect_left([3, 5]) : renvoie l'index où l'élément serait rajouté (si l'élément est déjà présent, à sa gauche)
l.bisect_right([3, 5]) : renvoie l'index où l'élément serait rajouté (si l'élément est déjà présent, à sa droite)
l[2] : pour accéder au troisième élément.
par contre, on ne peut pas changer la valeur d'un élément : l[2] = ... est interdit ! Il faut faire un del l[2], puis rajouter un autre élément.

Si l = sortedcontainers.SortedList([3, 4, 6, 7, 8, 9, 10, 25, 14]) :

l.irange(minimum = 7) : renvoie un itérateur sur toutes les valeurs supérieures ou égales à 7.
l.irange(maximum = 7) : renvoie un itérateur sur toutes les valeurs inférieures ou égales à 7.
l.irange(minimum = 2, maximum = 8, inclusive = (True, False)) : renvoie un itérateur sur toutes les valeurs comprises entre 2 et 7, 7 exclu.
l.irange(minimum = 2, maximum = 8) : le défaut est inclusive pour les deux.
l.irange(minimum = None, maximum = 7, inclusive = (True, False), reverse = True) : renvoie un itérateur pour toutes les valeurs strictement inférieures à 7, et en renvoyant les valeurs dans le sens inverse.
si les éléments de la Sortedlist ne sont pas juste des nombres, mais par exemple des listes à 2 éléments : faire l.irange(minimum = [5, 7], maximum = [9, 2])

On peut aussi définir un ordre particulier, qui utilise alors en fait la classe dérivée SortedKeyList :

from sortedcontainers import SortedList
l = SortedList(key = lambda x: x[1])
l.add([3, 4])
l.add([5, 1])

renvoie cette fois-ci une SortedKeyList, classe dérivée de SortedList.

on peut utiliser tous les fonctions de SortedList.
l.bisect_key_left(4) : renvoie l'index où la clef serait positionnée (si elle existe déjà, à sa gauche).
l.bisect_key_right(4) : renvoie l'index où la clef serait positionnée (si elle existe déjà, à sa droite).

SortedDict : c'est un dictionnaire dont les clefs sont triées

from sortedcontainers import SortedDict
d = SortedDict()

d['b'] = 11 pour rajouter une clef-valeur.
d.setdefault('e', 12) : comme le setdefault avec un dictionnaire normal.
d.irange : même comportement sur les clefs du dictionnaires que sur une SortedList.
pour avoir la clef avant 'd' ou égale à 'd' : list(itertools.islice(d.irange(maximum = 'd', reverse = True), 1))
pour avoir la clef après 'd' ou égale à 'd' : list(itertools.islice(d.irange(minimum = 'd'), 1))

programmer en python, tutoriel python, graphes en python, Aymeric Duclert