La liste est composée de nodes. C'est une liste doublement chaînée.
Le node est un objet composé de trois membres : un element de type T (template) pour stocker une valeur, un pointeur sur le node suivant, un pointeur sur le node précédent.
L'objet liste est composé d'un pointeur sur node dummy et d'un type numérique pour stocker la taille de la liste.
Qu'est ce qu'un dummy node ? Quelle utilité ?
Ce node est initialisé à la création d'un objet liste, il ne contient aucune valeur. Une liste vide possède donc au moins ce node. Mais il n'est pas compté dans la taille. C'est un node fantôme. Le pointeur next de ce node pointe sur le premier node (élément) de la liste. Le pointeur prev de ce node pointe sur le dernier node de la liste.
Le dummy node marque la fin de la liste (contexte d'itération).
Il permet une implémentation simple du bidirectional iterator. Il permet de ne pas utiliser de pointeurs head et tail.
Les iterateurs sont des objets qui permettent d'itérer sur un container de manière simple, on peut les utiliser comme des pointeurs (increment, dereference, etc).
L'itérateur de list est de type bidirectional. On peut l'incrémenter et le décrémenter donc.
iterator et const_iterator sont deux classes (objets) différents.
La différence est que le const_iterator pointe sur un objet const, on ne peut donc pas modifier la valeur des elements du conteneur via ce type d'itérateur.
Un iterator doit pouvoir être converti implicitement en const_iterator. Pour ça, il suffit d'implémenter un constructeur par copie qui prends un iterator en paramètre pour le const_iterator.
Un const_iterator ne peut pas être converti en iterator.
Les iterator et const_iterator peuvent être comparés. Il faut donc fournir les overloads en question (== et !=).
Si l'objet list est const qualified, alors les fonctions begin() et end() vont retourner un const_iterator. D'où leur overload avec const_iterator en return type.
list::sort n'utilises pas std::sort mais implémentes le sien.
| N ints | Bubblesort | Quicksort | Mergesort | STL 👑 |
|---|---|---|---|---|
| 10 | 0.00 sec | 0.00 sec | 0.00 sec | 0.00 sec |
| 1000 | 3.65 sec | 0.00 sec | 0.00 sec | 0.00 sec |
| 3000 | 101.53 sec | 0.00 sec | 0.01 sec | 0.00 sec |
| 10000 | X | 0.01 sec | 0.01 sec | 0.01 sec |
| 100000 | X | 0.21 sec | 0.07 sec | 0.05 sec |
| 1000000 | X | 12.52 sec | stack overflow | 0.80 sec |
| 10000000 | X | > 2272.76 sec | stack overflow | 134.14 sec |
Notes :
Le temps a été calculé avec la commande time, il corresponds à N push + execution du tri.
Les valeurs ont été générées de manière random avec le range 0..3000. Donc les très longues listes comportaient énormément de doublons.
Mon quicksort est basique et non optimisé. Son code diffère de celui qu'on peut voir pour une liste doublement chainée puisque ici les nodes sont swappés directement, et non les valeurs, ce qui implique de mettre à jour les pointeurs sur node après chaque swap, etc. Il pourrait donc être plus rapide.
Le mergesort est exactement le même que celui ci : https://www.geeksforgeeks.org/merge-sort-for-doubly-linked-list/
Les performances sont meilleures que le quicksort, par contre, pour une liste d'un million d'int, ça pète la stack. Une implémentation hybride (récursive + itérative) ou entièrement itérative ne poserai pas ce problème, mais est ce que les perfs seraient bonnes ? Idk.
Est une classe template, qui prends un itérateur (list::iterator, vector::iterator, etc) en paramètre.
Un objet de type reverse_iterator va fonctionner comme un wrapper autour d'un objet de type iterator. Les méthodes proposées sont toutes implémentées avec les méthodes de l'itérateur à partir duquel l'objet est construit.
from http://cplusplus.com/reference/iterator/reverse_iterator/operator++/
reverse_iterator operator++(int) {
reverse_iterator temp = *this;
++(*this);
return temp;
}
Commentaire intéressant from le code source :
The fundamental relation between a reverse_iterator and its corresponding iterator i is established by the identity:
&*(reverse_iterator(i)) == &*(i - 1)
This mapping is dictated by the fact that while there is always a pointer past the end of an array, there might not be a valid pointer before the beginning of an array.
Le vecteur de la STL est implémenté avec un tableau, ce qui implique une réallocation complète en cas d'insertion d'un nombre d'elements supérieur à la capacité mémoire de ce tableau.
Afin d'éviter de réallouer de la mémoire à chaque insertion, une quantité de mémoire supérieure à la quantité simplement requise pour insérer les elements est allouée.
Comment est choisie cette quantité supplémentaire ?
La STL a choisi un facteur de croissance de 2.
Et il semblerait que le choix se fasse de la manière suivante : pour N nombre d'éléments présent dans le vecteur et X nombre d'éléments que l'on souhaite ajouter dans le vecteur
if capacité * 2 < N + X
quantité_de_mémoire = N + X
else
quantité_de_mémoire = N * 2
D'autre stratégies de réallocation existent, bon exemple ici d'une réimplémentation optimisée de std::vector : https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md
code source de la libstdc++ :
https://gcc.gnu.org/onlinedocs/gcc-4.6.2/libstdc++/api/a01055_source.html
autres :
https://cs.calvin.edu/activities/books/c++/intro/3e/WebItems/Ch14-Web/STL-List-14.4.pdf
https://codefreakr.com/how-is-c-stl-list-implemented-internally/
https://stackoverflow.com/questions/5384358/how-does-a-sentinel-node-offer-benefits-over-null
https://codereview.stackexchange.com/questions/216444/c-linked-list-iterator-implementation
https://quuxplusone.github.io/blog/2018/12/01/const-iterator-antipatterns/
https://stackoverflow.com/questions/30287402/c-nested-class-in-class-template-declaration
https://42born2code.slack.com/archives/CMX2R5JSW/p1604438239334300
quicksort :
https://www.youtube.com/watch?v=0SkOjNaO1XY
https://www.geeksforgeeks.org/quick-sort/
https://www.geeksforgeeks.org/quicksort-for-linked-list/
reverse_iterator :
https://gcc.gnu.org/onlinedocs/gcc-6.4.0/libstdc++/api/a01623_source.html
http://cplusplus.com/reference/iterator/reverse_iterator/
mergesort :
https://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html