Bonjour à tous,

J'aimerais avoir des détails sur l'implémentation de la classe list de la stl.

Est-ce que cette classe utilise des sentinelles (debut ou fin) ?

Merci beaucoup

Salut,

De manière générale, j'aurais envie de demander "quel intérêt y aurait-il à le savoir?".

En effet, le rôle des différentes classes proposées par la bibliothèque standard est, justement:

• de t'éviter d'avoir à te casser la tête quant à la manière dont elles fonctionnent en interne
• de te garantir que  les différentes fonctionnalités exposées par ces classes présentent une complexité clairement définie.

Si l'on prend la documentation de std::list, on peut lire:

std::list is a container that supports constant time insertion and removal of elements from anywhere in the container. Fast random access is not supported. It is usually implemented as a doubly-linked list. (...) this container provides bidirectional iteration capability while being less space efficient.

(std::list est un container qui supporte l'insertion et la suppression d'éléments n'importe où dans le container en temps constant. L'accès aléatoire rapide aux élément n'est pas supporté. Elle est généralement implémentée en tant que liste doublement chainée. (...) ce container permet le parcours dans les deux sens bien qu'étant moins efficace en terme d'espace requis)

Adding, removing and moving the elements within the list or across several lists does not invalidate the iterators or references. An iterator is invalidated only when the corresponding element is deleted.

(l'ajout, la suppression et le déplacement d'élément à l'intérieur d'une liste ou entre différentes listes n'invalide ni les itérateurs ni les référence. Un itérateur est invalidé uniquement lorsque l'élément correspondant est détruit)

std::list meets the requirements of Container, AllocatorAwareContainer, SequenceContainer and ReversibleContainer.

(std::list rencontre les restrictions imposées au concepts de Container,de AllocatorAwareContainer (container disposant de son propre allocateur), de SequenceContainer (container stockant les objets de type similaire sous forme linéaire) et de ReversibleContainer (container permettant de parcourir les éléments dans les deux sens) )

Et c'est tout ce que tu as besoin de savoir à son sujet!

De toutes façons, tu peux te dire qu'il n'y a pas trente-six manière de garantir le respect de ces restrictions en termes d'implémentation

Cependant, si, une fois que tu as compris que les règles qui sont énoncées concernant std::list ne laissent en définitive pas vraiment le choix de l'implémentation, tu peux toujours aller voir du coté des fichiers d'en-tête fournis par ton compilateur (le fichier list, de base, mais surtout les fichiers qu'il inclut, comme bits/stl_list.h sous gcc) afin d'en savoir un peu plus.

Il faudra sans doute te retourner un sérieux coups le cerveau dans tous les sens pour arriver à en conclure que la seule manière "sensée" pour garantir les restrictions imposées (en plus de garantir l'exécution en temps constant de la fonctions size() ) est de prévoir:

• un pointeur sur le premier élément de la liste
• un pointeur sur le dernier élément de la liste
• une valeur entière représentant le nombre d'éléments utilisés