Au cours du TP précédent, vous avez implémenté une classe Vecteur dans le but de redéfinir l'opérateur crochet d'accès aux éléments. Ici, nous allons explorer le monde fantastique et terrifiant à la fois des classes paramétrées ou template.
Le but est de créer une classe ListeChainee générique. Vous supposerez que les types d'instanciation du template disposeront des éléménts suivants :
Ces pré requis ne sont pas exorbitants car définis dans la forme canonique de Coplien ... et toute classe qui se respecte se doit d'être conforme à Coplien.
Rappelons qu'un itérateur est une balise de positionnement dans une collection.
Vous devrez fournir 3 classes :
A ce sujet il existe deux grandes variantes de programmation :
Quelle variante allez vous choisir ? Il est évident que le code est plus simple (et sans doute plus efficace) en utilisant les friend, aussi je vous les recommanderai malgré mon aversion profonde pour cette technique.
Les opérations suivantes devront être disponibles sur la liste :
Les opérations suivantes devront être fournies sur l'itérateur :
Les listes chaînées les plus simples à manipuler sont les listes doublement chaînées circulaires avec élément fictif. Le schéma suivant les illustre :
L'intérêt réside dans le fait que chaque élément a toujours un successeur et un prédécesseur (éventuellement lui même). On supprime ainsi tous les cas particuliers lors de l'insertion ou de la suppression.
En outre, vous n'avez besoin de conserver qu'un seul pointeur : celui sur l'élément fictif.
L'insertion d'un nouvel élément entre les cellules A et B se fait très simplement à l'aide des opérations numérotées :
De même, il est facile de supprimer la cellule B :
