Polymorphisme

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 d’autres, et l’un 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 l’usage des classes).

Revenons sur notre liste chaînée. Elle possède un certain nombre de défauts. Des défauts fonctionnels d’abord : 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 l’un sur l’autre. L’intérêt de cette méthode est qu’il suffit de posséder un pointeur sur l’un 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 d’un destructeur qui permet de supprimer un élément de la liste sans altérer la structure de celle-ci ; il n’était pas possible d’en écrire un semblable avec une liste chaînée simple.

On a supposé les éléments assez volumineux (quoique dans notre exemple il s’agisse de long), d’où l’emploi de références constantes comme arguments des méthodes insere et noeud.

L’utilisation d’une telle liste est cependant un peu fastidieuse, notamment lorsqu’il faut la créer par petits morceaux, ou la détruire de même. Nous avons vu qu’on pouvait définir des fonctions pour cela. Mais en fait, ce que nous voulons, c’est un type de liste, qui permette des opérations d’écriture, et dans lequel on puisse avancer ou reculer (c’est-à-dire modifier l’élément pris comme base de référence), ainsi qu’insérer ou supprimer des éléments. Voici un exemple de programme que l’on 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 d’un é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 l’insertion se fait à la position courante.

Il n’est 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 d’avoir à 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) d’avancer ce pointeur de noeud en noeud ou de le faire reculer ; on ne change ainsi que l’ordre 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 d’un tableau, comme dans l’exemple 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, avance, affiche, insere et supprime. La méthode insere renvoie 0 s’il n’y a plus de place en mémoire.

Pour toutes les méthodes, on tiendra compte de la limitation de la mémoire, qui peut obliger à n’insérer qu’une partie des éléments lors de l’appel 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 l’on a bien le résultat souhaité.

Exercice 6.5

Quel(s) manque(s) voyez-vous dans la classe liste ? Et quelles méthodes lui ajouteriez-vous ?

Voir solution

Un tel mécanisme de liste doublement chaînée est intéressant lorsque les éléments sont assez volumineux (sinon l’ajout de deux pointeurs augmenterait trop la place mémoire occupée) et que l’on fait de nombreuses opérations d’insertion et de suppression.

Par contre, avec pour éléments des entiers long, cela semble peu rentable. Imaginons donc qu’ayant é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 l’accé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 n’est pas le cas en programmation objet. Voici une seconde implantation possible de liste, qui... n’est pas une liste mais un tableau dont l’apparence 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 l’un de ces éléments (on aurait pu utiliser aussi un entier servant d’index). Les méthodes ont le même effet, mais évidemment une implantation différente. Le type noeud n’est pas utilisé puisqu’il ne s’agit pas d’une 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 l’opération d’insertion 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 s’il y a peu d’insertions séparées.

Exercice 6.7

Le reproche fait à la première implantation de liste (exercice 6.5) s’applique-t-il toujours ? Si oui, que faire ?

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 d’avis sur l’implantation 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 d’exemple n’a nécessité aucune modification.

Cette capacité à réaliser un ensemble logiciel de plusieurs façons différentes mais de manière totalement transparente s’appelle le polymorphisme. C’est un atout capital de la POO, surtout pour des programmes de grande taille qu’il est exclu de réécrire entièrement lorsqu’on en modifie une petite partie.

Nous verrons au chapitre 10 comment utiliser plusieurs fichiers différents pour compléter à la fois l’encapsulation et le polymorphisme (et notamment éviter des recompilations). Nous verrons aussi ultérieurement un autre aspect du polymorphisme : les gabarits.

Précédent Précédent Sommaire Sommaire Suivant Suivant