Ceci est un exercice de style :
Pour respecter le principe de réutilisation, il est bien entendu recommandé d'utiliser
autant que possible les conteneurs de la "STL", ainsi que ses Algorithmes et Fonctions
L'objectif de cet article est de créer un conteneur d'éléments
Les éléments seront de types quelconques (utilisation des Templates)
Il devra être pratique et efficace pour les opérations suivantes :
- créer un nouveau conteneur
- ajouter un nouvel élément - à la fin ou derrière un élément donné
- retirer un élément au conteneur
- parcourir les éléments en vue de les afficher ou d'effectuer toute autre opération dessus
- rechercher un élément par sa valeur
- compter les éléments
- vider le conteneur
Les fuites mémoires devront être évitées
"PARTIE I:"
Création d'un conteneur à simple chaînage sur des int
Accepte des insertions
"PARTIE Ibis:"
Accepte l'opération Compte() qui renvoie le nombre d'éléments
"PARTIE II:"
Création d'un conteneur à double chaînage sur des int
Accepte des insertions et des destructions
"PARTIE III:"
Refactoring et Factorisation du code
"PARTIE IV:"
Généricité : un conteneur valide pour tous les types de valeurs
Source / Exemple :
#include <iostream.h>
namespace vieuxLion
{
class Liste;//déclaration forward nécessaire pour "friend"
/* "PARTIE I: "
On commencera par choisir la liste chaînée comme support
Elle est meilleure que le simple tableau pour les insertions et suppressions
Dans cette première partie, on raisonnera avec le type 'int' pour les valeurs des éléments
On créera une classe Element dont le rôle est de supporter la valeur ET les chaînages avant et arrières
sur les éléments suivant et précédent
L'élément suivant sera utilisé pour le parcours de la liste (en avant)
L'élément précédent sera utile en cas de destruction d'élément (pour mettre à jour le pointeur suivant du précédent)
ou en cas de parcours arrière
Cette classe aura donc trois données membres (deux seulement dans cette partie I) et un constructeur correspondant
class Element
{ friend Liste;//l'accès aux données des Elements est OK pour la Liste
private:
int valeur_;//la valeur de l'élément est pour l'instant limitée à 'int'
Element* suivant_;
public:
Element(int valeur): valeur_(valeur), suivant_(NULL){}
};
/*On créera ensuite une classe Liste composée des Elements
Pour des raisons d'efficacité, il est bon de mémoriser la tête et la queue de la liste
La tête sera utile pour parcourir la liste à partir du bébut
La queue sera utile pour insérer efficacement un nouvel élément à la fin
class Liste
{
private:
Element* tete_;
Element* queue_;//la mémorisation de la queue est pratique pour les Ajouts
Liste (const Liste& l);//empêche la copie par Ctor
void operator=(const Liste& l);//empêche la copie par affectation
public:
Liste();
~Liste();
Element* Ajouter(int valeur, Element* pE=NULL);//ajouter derrière pElt
void Vider();//détruire la liste ainsi que les objets pointés
void Afficher() const;//parcours et affichage des éléments
};
/* Il est à noter que la liste contient des pointeurs sur les éléments et
qu'en cas de copie, la copie des pointeurs n'est pas recommandée (problème d'aliassing)
Il serait donc nécessaire de surcharger les opérateurs = et Ctor de copie...
La solution la plus simple ici, est d'interdire la copie
On rendra donc private les deux opérations.
Implémentation :
Le Ctor de Liste crée une liste vide
Le Dtor de Liste nettoie les éléments (s'il y en a)
La technique de parcours de la liste est toujours la même :
démarrer à la tête puis naviguer sur le suivant, etc...
Liste::Liste()
{ tete_ = NULL; queue_ = NULL;}
Liste::~Liste()
{ Vider(); }
Element* Liste::Ajouter(int valeur, Element* pE )
{//pE est l'élément derrière lequel se fait l'insertion
if (!pE) pE = queue_ ;//par défaut, ajout en queue
Element* pNew = new Element(valeur);//création de l'Elt à partir de la valeur
if (tete_==NULL)
{ tete_ = queue_ = pNew;//le premier est aussi le dernier, il est le seul}
else
{
pNew->suivant_ = pE->suivant_;//le suivant du nouveau est 'le suivant de pE'
pE->suivant_ = pNew;//le nouveau devient le suivant de 'pE'
if (pE==queue_) queue_ = pNew;
}
return pNew;
}
void Liste::Afficher() const //afficher toute la liste
{
if (tete_ == NULL) cout << "la liste est vide..." << endl;
else
{
cout << "la liste contient : " << endl;
Element* iter = tete_;
do
{
cout << "\t" << iter->valeur_ << endl;
iter = iter->suivant_;
}
while (iter);
}
}
void Liste::Vider() // Vider toute la liste
{
if (tete_ == NULL)
{ cout << "la liste est deja vide" << endl;
return;
}
else
{
Element* iter = tete_;
Element* pSuivant;
do
{
pSuivant = iter->suivant_;
delete iter;
iter = pSuivant;
}
while (iter);
}
tete_ = queue_ = NULL;
cout << "la liste est videe" << endl;
}
}//namespace vieuxLion
using vieuxLion::Liste;
using vieuxLion::Element;
int main()
{
cout << "creer une liste (vide)" << endl;
Liste l;
cout << "ajouter un nouvel element cree par valeur (1)" << endl;
Element* pE1 = l.Ajouter(1);
cout << "ajouter un nouvel element cree par valeur (2)" << endl;
Element* pE2 = l.Ajouter(2);
cout << "afficher la liste" << endl;
l.Afficher();
cout << "inserer un Element (3) derriere un autre (1)" << endl;
Element* pE3 = l.Ajouter(3, pE1);
cout << "afficher la liste" << endl;
l.Afficher();
cout << "rechercher un element par valeur (3)" << endl;
cout << "ajouter des nouveaux elements (3,4,5,6)" << endl;
l.Ajouter(3);l.Ajouter(4);l.Ajouter(5);l.Ajouter(6);
l.Afficher();
//Le Ctor de copie est inhibé
//Liste l2 = l;
//L'operator= est inhibé
//Liste l3;
//l3 = l;
cout << "Vider la liste" << endl;
l.Vider();
return 0;
}
/* "PARTIE I bis:"
Dans cette partie, nous nous proposons de gérer l'opération Compte
La solution consistant à effectuer un parcours complet des éléments
pour compter étant TRES inefficace, il faudra ajouter un compteur 'compte_' comme attribut
Ce compteur sera initialisé à 0 dans le Ctor, puis incrémenté lors de chaque
insertion. Il sera remis à 0 dans la méthode Vider()
La méthode Compte() sera très efficace : elle renverra simplement l'attribut compte_
Cf code source 'ClassList-Ibis.CPP' du ZIP
"PARTIE II:"
Amélioration de la classe Liste pour accepter les destructions d'éléments
- L'argument de la destruction est un pointeur sur un élément existant
Le problème est que la destruction d'un élément provoque une rupture de chaîne.
Il est nécessaire de raccrocher les deux bouts.
Ce qui signifie : positionner le suivant de l'élément détruit comme nouveau suivant
de l'élément "précédant" l'élément détruit
Dans notre implémentation, il est facile de connaître le suivant mais le précédent
n'est pas prévu. => Rajoutons le de façon à obtenir une liste doublement chaînée.
- Il est pratique de fournir aussi une fonction de destruction par valeur:
L'argument sera la valeur portée par l'élément plutôt que le pointeur
Elle servira dans les cas où l'on n'a pas mémorisé le pointeur renvoyé par l'Ajout.
On fournira alors de plus une méthode "helper" chargée de trouver le pointeur correspondant
à partir d'une valeur - elle renverra le premier pointeur trouvé dont la valeur correspond.
Pour des raisons d'efficacité, il est bon de pouvoir fournir à cette méthode
le point(eur) de départ. Ainsi, elle pourra servir à trouver tous les éléments de valeur
donnée par des appels successifs sans repartir de la 'tête'.
On la nommera 'ChercherPremier'
- On ajoutera une fonction pour vérifier l'existence d'un pointeur donné
La méthode sera nommée 'Existe' : elle devra parcourir la liste jusqu'à trouver l'élément.
Cf code source 'ClassList-II.CPP' du ZIP
"PARTIE III (technique avancée - facultatif)" :
Refactoring interne léger
Lors de la création de la pile et lors de son vidage
il faut ramener les trois variables membres à zero
on peut créer une méthode privée pour faire cela
void init(){ tete_ = queue_ = NULL; compte_=0;}
Elle sera appelée dans le Ctor et dans Vider()
Refactoring interne plus lourd
Remarquez la similitude des méthodes Afficher, Vider et ChercherPremier.
Toutes font un parcours de la liste. Comment peut-on faire pour partager ce code ?
Le point commun est le parcours
La différence est le traitement à faire sur chacun des éléments
La solution suivante crée une méthode 'iterer' appelée par les trois précédentes.
Elle sera chargée de parcourir la liste et de rappeler pour chaque élément
une fonction spécialisée (nommée par exemple affiche, detruire et compare)
La technique est réalisable avec une méthode 'iter' prenant en argument un pointeur de fonction
vers les fonctions spécialisées. La contrainte est que ces fonctions devront
avoir le même prototype
Nous avons choisi le suivant :
la fonction spécialisée doit
- connaitre l'élément : elle le reçoit par pointeur
- pouvoir arrêter le parcours : elle reçoit un booléen par référence
- connaître l'élément de comparaison : elle le reçoit par pointeur.
ceci est seulement utilisé dans le cas de l'appel par la méthode ChercherPremier,
pour savoir si l'élément est de la bonne valeur.
On mettra donc une valeur par défaut à NULL pour cet argument
Voici la déclaration du pointeur de fonction :
typedef void (Liste::*PFN)(Element *, bool&, Element* p=NULL);
Cf code source 'ClassList-III.CPP' du ZIP
"PARTIE IV" :
Génericité
Pour traiter des valeurs différente de 'int', la solution normalisée est de
passer par des Templates
La technique est de rajouter 'template <class T>' devant chaque classe et fonction
puis de remplacer toutes les occurences des 'int' à rendre génériques par 'T'.
Pour tester, on créera une classe Scalaire et une classe Composee
Elle devront être munies des opérateurs == et << qui sont utilisés dans la Liste.
Cf code source 'ClassList-IV.CPP' du ZIP
Conclusion :
inspiré par le bon source en C de COBRA84
sur cette tentative, il s'agit de C++
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.