Nous avons déjà vu un premier avantage de la programmation orientée objet : la protection des données, fournie par la déclaration de membres privés dans une classe.
Il en existe dautres, et lun des plus importants est le polymorphisme, que nous allons illustrer à présent par un exemple (ce qui nous permettra en même temps de nous perfectionner dans lusage des classes).
Revenons sur notre liste chaînée. Elle possède un certain nombre de défauts. Des défauts fonctionnels dabord : on ne peut pas « revenir en arrière » dans la liste, puisque les noeuds ne pointent que sur les suivants. Pour améliorer cela, nous utiliserons une liste circulaire doublement chaînée. Chaque noeud pointe à la fois sur le précédent et le suivant, et le dernier et le premier lun sur lautre. Lintérêt de cette méthode est quil suffit de posséder un pointeur sur lun quelconque des noeuds pour pouvoir accéder à toute la liste ; en quelque sorte, chaque noeud est racine de la liste entière. Voici un nouveau type noeud répondant à ces attentes :
typedef long element; // (par exemple) class noeud { noeud *suivt, *prec; element elm; public : noeud(const element& e, noeud* apres = 0) { // construit et insère après apres elm = e; if (apres) { suivt = apres->suivt; prec = apres; apres->suivt = this; suivt->prec = this; } else prec = suivt = this; } ~noeud() // destructeur { prec->suivt = suivt; suivt->prec = prec; } element& contenu(void) { return elm; } noeud* suivant(void) { return suivt; } noeud* precedent(void) { return prec; } noeud* insere(const element& e) { // insère après this noeud *nouveau = new noeud(e, this); return nouveau; } };
Noter la présence dun destructeur qui permet de supprimer un élément de la liste sans altérer la structure de celle-ci ; il nétait pas possible den écrire un semblable avec une liste chaînée simple.
On a supposé les éléments assez volumineux (quoique dans notre exemple il sagisse de long
), doù lemploi de références constantes comme arguments des méthodes insere
et noeud
.
Lutilisation dune telle liste est cependant un peu fastidieuse, notamment lorsquil faut la créer par petits morceaux, ou la détruire de même. Nous avons vu quon pouvait définir des fonctions pour cela. Mais en fait, ce que nous voulons, cest un type de liste, qui permette des opérations décriture, et dans lequel on puisse avancer ou reculer (cest-à-dire modifier lélément pris comme base de référence), ainsi quinsérer ou supprimer des éléments. Voici un exemple de programme que lon souhaite voir fonctionner avec une telle liste :
main(){ element table[9] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; liste ls(9, table); // 9 éléments dans la liste ls.affiche(); // affiche tout ls.avance(5); // avance de 5 éléments ls.affiche(); ls.supprime(6); // supprime 6 éléments ls.affiche(); ls.insere(18); // ajouter lélément 18 ls.insere(17); ls.recule(); // reculer dun élément ls.affiche(); return 0;}
On doit voir alors ceci à lécran :
1 2 3 4 5 6 7 8 96 7 8 9 1 2 3 4 53 4 55 17 18 3 4
étant entendu que linsertion se fait à la position courante.
Il nest pas très difficile de créer une classe liste
répondant à ces attentes. Voici une possibilité :
class liste { noeud* courant; int nombre; public : liste() { nombre = 0; courant = 0; } liste(int n, const element*); // constructeur avec table ~liste(); void avance(int combien = 1); void recule(int combien = 1) { avance(-combien); } element& valeur(void) { if (courant) return courant->contenu(); } unsigned nombre_elt(void) { return nombre; } void affiche(unsigned combien = 65535); int insere(const element&); void supprime(int n = 1); };
La liste contient le nombre de ses éléments (afin déviter davoir à les recompter quand on en a besoin), et un pointeur sur un élément quelconque de la liste, qui est la racine courante ; il est parfaitement possible (contrairement à une liste simple) davancer ce pointeur de noeud en noeud ou de le faire reculer ; on ne change ainsi que lordre de vue des éléments, non leur nombre ni leur position relative.
La méthode nombre_elt
indique le nombre déléments dans la liste, et valeur
donne la valeur de lélément courant. Un constructeur permet de créer la liste en bloc à partir dun tableau, comme dans lexemple de programme ci-dessus, et le constructeur par défaut crée une liste vide.
Exercice 6.4 | Écrivez les méthodes qui ne sont pas en ligne ci-dessus : le constructeur à deux arguments, le destructeur, Pour toutes les méthodes, on tiendra compte de la limitation de la mémoire, qui peut obliger à ninsérer quune partie des éléments lors de lappel du constructeur par exemple. |
Voir solution |
Nous avons donc rempli notre contrat : le lecteur pourra essayer cette classe avec le programme donné, et constater que lon a bien le résultat souhaité.
Exercice 6.5 | Quel(s) manque(s) voyez-vous dans la classe |
Voir solution |
Un tel mécanisme de liste doublement chaînée est intéressant lorsque les éléments sont assez volumineux (sinon lajout de deux pointeurs augmenterait trop la place mémoire occupée) et que lon fait de nombreuses opérations dinsertion et de suppression.
Par contre, avec pour éléments des entiers long
, cela semble peu rentable. Imaginons donc quayant écrit tout un programme utilisant le type liste
, vous vous apercevez que celui-ci est trop lent et prend trop de place en mémoire.
Pour laccélérer et gagner de la place mémoire, on peut changer le type liste
en un tableau ordinaire.
En programmation ordinaire, il faudrait refaire tout le programme utilisant le type liste
. Cela nest pas le cas en programmation objet. Voici une seconde implantation possible de liste
, qui... nest pas une liste mais un tableau dont lapparence extérieure est identique, de sorte que le programme donné précédemment fonctionne de la même façon avec celle-ci :
class liste { // 2° version : tableau element *tab, *courant; int nombre; public : liste() { nombre = 0; courant = tab = 0; } liste(int n, const element*); // constructeur avec table ~liste(); void avance(int combien = 1); void recule(int combien = 1) { avance(-combien); } element& valeur(void) { if (courant) return *courant; } unsigned nombre_elt(void) { return nombre; } void affiche(unsigned combien = 65535); int insere(element); void supprime(int n = 1); };
Ici tab
est un tableau déléments placé dans le tas ; courant
est un pointeur sur lun de ces éléments (on aurait pu utiliser aussi un entier servant dindex). Les méthodes ont le même effet, mais évidemment une implantation différente. Le type noeud
nest pas utilisé puisquil ne sagit pas dune vraie liste chaînée.
Exercice 6.6 | Écrire les six méthodes non implantées ci-dessus. |
Voir solution |
Un examen détaillé et des essais montrent que lopération dinsertion est à présent trois fois plus lente, mais que les autres sont plus rapides, même la suppression (car la suppression de plusieurs noeuds est assez lente en fait). On y gagne donc sil y a peu dinsertions séparées.
Exercice 6.7 | Le reproche fait à la première implantation de |
Voir solution |
Que peut-on conclure de cet exemple ? Primo, nous avons constaté une encapsulation des données insuffisantes avec le type noeud
, obligeant à faire des manipulations compliquées au programme ; pour éviter cela, nous avons créé une couche supplémentaire de logiciel, avec une classe liste
.
Ensuite, changeant davis sur limplantation de liste
, nous avons recréé cette classe sur un modèle complètement différent, mais les en-têtes des méthodes sont restés les mêmes, de sorte que le programme dexemple na nécessité aucune modification.
Cette capacité à réaliser un ensemble logiciel de plusieurs façons différentes mais de manière totalement transparente sappelle le polymorphisme. Cest un atout capital de la POO, surtout pour des programmes de grande taille quil est exclu de réécrire entièrement lorsquon en modifie une petite partie.
Nous verrons au chapitre 10 comment utiliser plusieurs fichiers différents pour compléter à la fois lencapsulation et le polymorphisme (et notamment éviter des recompilations). Nous verrons aussi ultérieurement un autre aspect du polymorphisme : les gabarits.
Précédent | Sommaire | Suivant |