et un peu de
Programmation par Objets
Troisième Partie: Classes
Génériques en C++.
Najib TOUNSI ( ntounsi@emi.ac.ma)
Creation : Mai 1998
Derniere MAJ: Oct 98
La généricité, est la possibilité de définir des fonctions ou des classes paramétrées par un type. De telles fonctions ou classes sont dites génériques. En effet, certaines abstractions, comme une procédure de tri par exemple, ne dépendent pas du type des objets (entiers, réels, ...) à trier. De même, une pile par exemple, ne dépend pas du type des éléments qui s'y trouvent. Les opérations concernées par une pile sont les mêmes quelque soit la classe des objets à empiler ou dépiler.
En C++, on a la possibilité de définir des patrons (template) qui sont des descriptions paramétrées par un type T. On peut décrire une classe pile d'objets de type T, et ensuite instancier des piles d'un type spécifique. Ainsi, une seule implantation de pile peut servir comme une représentation générique de la sémantique d'une pile. Chaque instanciation produira une nouvelle pile d'éléments spécifiques.
La description d'une classe générique , X disons, se fait par:
template <class T>
class X {
// description de la classe X avec usage du type T
//...
};
Le préfixe template <class T> indique que la classe X est générique paramétrée par la classe T. X est donc comme modèle de classes[13]. Des instanciations se feront par:
X <int> xi;
X <char> xc;
ou
X <article> xa; etc.
où on indique entre <> le type effectif pour chaque objet déclaré.
Exemple:
Au § 3. nous avons défini une pile de caractères. Maintenant on peut définir une pile d'objets quelconques:
template <class T>
class Pile {
T P[10]; //Tableau d'objets de type T
int top;
public:
Pile(){ top = -1;}
void empiler(T& e){
P[++top] = e;
}
void depiler(){
top--;
}
T sommet (){
return P[top];
}
};
Pour créer des piles effectives on peut écrire:
Pile <int> pileInt; // une pile d'entiers
Pile <float> pileFloat; // une pile de réels
Pile <article> pileArticle; // une pile d'articles
L'usage de ces piles est par exemple:
pileInt.empiler(2);
pileFloat.empiler(x);
pileArticle.empiler(a); // a objet article
n = pileInt.sommet();
On pourra remarquer que l'écriture:
Pile <int>
est une instanciation de classe. On peut, d'ailleurs, lui donner un nom par typedef:
typedef Pile <int> PileIntType;
PileIntType est le nom de la nouvelle classe qui peut servir à déclarer deux pile d'entiers pileInt1 et pileInt2:
PileIntType pileInt1, pileint2;
En résumé, la classe générique Pile sert à créer (instancier) de nouvelles classes:
typedef Pile <int> PileIntType;
typedef Pile <float> PileFloatType;
etc... qui, quand à elles, servent à instancier des objets:
PileIntType pileInt1, pileInt2;
PileFloatType pileFloat1, pileFloat2;
Le type en paramètre d'une classe générique n'est pas forcement neutre. En effet, une classe générique doit pouvoir faire des hypothèses sur son type paramètre afin d'utiliser des opérations définies dessus. Par exemple, dans la classe Pile juste dessus, il est fait usage implicite de l'affectation d'objets de type T (de même que d'un constructeurs T(T&); ). On a peut être en tête l'idée d'instancier la classe sur des types de base. Mais en générale, il s'avère nécessaire que le type T soit muni de certaines opérations. On va justifier ce point sur un exemple, avec cette fois-ci une fonction générique. C'est la fonction tri qui trie les éléments d'une liste. Le type des éléments de la liste, donné en paramètre, doit avoir une relation d'ordre et donc une fonction de comparaison.
Une fonction générique se définit de la même façon comme:
template <class T> definition_fonction
ce qui donne pour notre fonction tri:
template <class T>
void tri (T* l, int taille){
// tri d'une liste l de longueur taille
// Algorithme bubble sort
}
Cet algorithme, quoiqu'il ne dépende pas du type T des éléments de la liste, nécessite qu'il soit muni d'une opération de comparaison qui est supposée inf() ici. Considérons la classe String ([[section]] 8) et munissons la d'une opération inférieur().
Class String {
//...
friend int inférieur( String&, String&);
};
Pour trier un tableau d'objets de type String on écrire:
String s[10];
//...
tri (s,10);
Il serait intéressant de surcharger l'opérateur < pour une classe, et ainsi on utilisera la comparaison
l[i] < l[i+1]
dans l'algorithme de tri, pour pouvoir écrire ensuite:
int t;[20]
String s[10];
// Classe String ayant int operator<(String&, String&)
tri (s,10);
tri (t, 20)
Ici, C++ instanciera tri, en fonction du paramètre fourni. Noter au passage que c'est un autre aspect de la surcharge.
En fait la généricité est surtout utile pour décrire un concept générale tel qu'une une collection d'objets. Par exemple pile, file, liste, ensemble, etc...De telles collections sont indépendantes du type des objets qui s'y trouvent et présentent, en outre, un comportement de même genre: on peut y insérer des éléments (ou les consulter et supprimer etc...). Avoir une description générique d'une collection s'avère donc intéressant. Et on peut considérer deux niveaux:
C'est ce dernier aspect qui nous concerne ici.
Nous allons illustrer cela sur un exemple simple qui décrit un
ensemble d'éléments de type T, lequel type sera le
paramètre générique. La collection est gérée comme un tableau
d'objets. Une variable size retient le nombre d'éléments
actuels.
Figure 6. Structure
de Données Ensemble d'éléments.
(1ère Version)
Soit:
#define MAX 10
#include "String.c"
template <class T> class Collection{
T t[MAX]; // tableau des éléments
short size; // taille actuelle
public:
Collection(){
size=0; // ensemble vide
}
void insert(T& e){
t[size++]=e;
}
void suppr (T& e){
for (int i=0;i<size;i++)
if(cmp(t[i],e)==0)
t[i] = t[--size];
}
int appart (T& e){ // test d'appartenance
// resultat 0 ou 1
// ...
}
// ...
};
La classe T des éléments du tableau est supposée munie des opérations d'affectation, (pour t[size++]=e;) et de l'opération de comparaison cmp(x, y) utilisée dans la suppression pour comparer deux éléments (cette opération est supposée rendre -1, 0 ou 1 pour x<y, x=y ou x>y ). La sémantique de la comparaison est bien sûr dépendante de la classe considérée: pour les nombre c'est l'égalité des valeurs et pour des articles c'est le même numéro etc... La classe T doit aussi, et surtout, disposer du constructeur défaut sans paramètres T(), car on ne peut prévoir ses paramètres de façon générale.
Note: Pour la collection, nous avons spécifié juste le constructeur, les opérations d'insertion et de suppression suffisantes pour illustrer les concepts désirés.
Exemples d'utilisation: On a une collection de String (cf [[section]] 8)
typedef Collection<String> ColStr;
ColStr maCol; //maCol est une collection de chaînes
String a("toto");
maCol.insert(a); // Insertion de toto
maCol.insert("titi");
maCol.suppr(a);
if (maCol.appart(a)) // test si a appartient à maCol
cout << "OK\n";
Cette implantation de collection serait idéale pour des objets élémentaires comme de entiers, des chaînes etc... qu'il est simple de copier déplacer au sein du tableau. L'implantation suivante, avec pointeurs, est parfois préférable.
Cette fois-ci, la collection est gérée à travers un tableau t de pointeurs vers les éléments individuels.
Figure 7. Structure
de Données Ensemble d'éléments
(2e Version).
Soit alors la deuxième implantation, avec pointeurs:
#define MAX 10
template <class T> class Collection{
T* t[MAX];
short size;
public:
Collection(){
size=0;
for (int i=0; i<size; i++)
t[i] = NULL;
}
void insert(T& e){
t[size++] = new T(e);
}
void suppr (T& e){
for (int i=0; i<size; i++)
if ( cmp(*t[i], e) == 0){
delete (t[i]);
t[i] = t[--size];
}
}
int Appart(T&) {
//...
}
~Collection(){
for (int i=0; i<size; i++)
delete (t[i]);
}
};
Ici, le code des méthodes est différent. Dans le constructeur, on prend la précaution d'initialiser les pointeurs à 0. C'est lors de l'insertion, qu'on alloue de la place par new pour instancier un nouvel élément. On note ici la présence d'un destructeur, pour libérer cas par cas les mémoires alloués aux objets de la collection.
Bien sûr, la mise en oeuvre de cette nouvelle collection est inchangée, puisque seulement l'implantation a changé (Execice: le verifier).
Un itérateur est un mécanisme qui permet d'énumerer un à un les
éléments d'une collection afin de les examiner lors d'un parcours.
(Paragraphe A Venir, Excuses)
//
// collection tableau , usage iterateur avec pointeurs
//
#include "String.c"
template <class T>
class Collection{
T t[10];
short size;
public:
Collection(){
size=0;
}
void insert(T& e){
t[size++]=e;
}
void suppr (T& e){
for (int i=0;i<size;i++)
if(cmp(t[i],e)==0)
t[i] = t[--size]; }
void print(){
printf("---------\n");
for(int i=0; i<size;i++){
t[i].print();
}
}
friend class iterator;
};
//--iterator class String--
typedef Collection<String> Strings;
class iterator{
Strings *s; // reference au set a parcourir
int cursor; // élém courant
public:
iterator (Strings &x){
// on itere sur x, ~reset
s = &x;
cursor = 0;
}
String* operator() () // suivant
{
return (cursor < s->size ? &(s->t[cursor++]) :
NULL );
}
};
main(){
Strings setStr;
iterator get(setStr); // init iterateur
/...
String *x;
x=get();
while ( x != NULL){
x->print();
x=get();
}
}