Structures de données IFT-2000 Abder Alikacem Pointeurs, références et gestion dynamique de la mémoire. QQ éléments techniques du C++. Semaine 2 Département

Structures de donnéesIFT-2000

Abder AlikacemAbder Alikacem

Pointeurs, références et gestion dynamique de la mémoire. QQ éléments

techniques du C++.

Semaine 2

Département d’informatique et de génie logiciel

Édition Septembre 2009

! +

Plan

RappelsDéfinition du type pointeurArithmétique des pointeurs

Application des pointeursLes référencesGestion dynamique de la mémoireTableaux dynamiques, tableaux à une et plusieurs

dimensionsPointeurs sur des objets et chaînage de la mémoire

Listes simplement chaînéesQuelques éléments techniques du C++

Le mot clé constLe mot clé staticLes itérations

Les pointeurs

Définition

Un pointeur est une variable contenant l’adresse d’une donnée (dans le vocabulaire des langages C/C++, le procédé qui consiste à atteindre une donnée via un pointeur sur cette donnée s’appelle une indirection). Toujours une valeur absolue

Adresses admissibles = entiers de longueur fixe (uniformité => référence uniforme et homogène)

Le type pointeur est considéré comme étant un type de base.

Déclarationchar *ptC; // Un pointeur sur un caractèrefloat *ptT; // Un pointeur sur un réelint *ptP; // Un pointeur sur un entier

L'opérateur &

&variable : donne l'adresse d'une variable

partout dans un programme si une adresse est mise dans une autre variable, cette autre variable doit être un pointeur.

Opérations d’adressage

x : contenu de la case mémoire associée à x

&x : adresse de x (adresse de la case mémoire associée à x)

ptr = &x : ptr sera un pointeur sur la case mémoire associée à x

Opérations d’adressage

L’opérateur * désigne le contenu de la variable dont l’adresse est l’opérande.

Notez que dans une déclaration, l’opérateur * n’a pas le même sens. Par exemple, la déclaration int* ptr; signifie que n est un pointeur sur un entier.

*ptr : réfère donc à la variable pointée (opérateur d'indirection), c’est le contenu de la variable dont l’adresse est ptr. On parle de déréférenciation.

Si ptr est un pointeur, ptr et *ptr sont des lvalue: ils sont modifiables.

Il n'en va pas de même de &ptr : (&ptr)++; elle sera rejetée à la compilation.

int* ptr; réserve un emplacement en mémoire pour un pointeur sur un

entier… elle ne réserve pas en plus un emplacement pour un entier!

Exemple

int i1=1,i2=2; int *p1,*p2;

p1=&i1; p2=p1; cout << *p1 << endl; /*affiche ?*/p2=&i2;*p2=*p1; cout << i2 << endl; /*affiche ?*/

Les pointeurs en C/C++

Exemple

int* ad1, * ad2, * ad;int n = 10, p = 20;

ad1 = &n;ad2 = &p;*ad1 = *ad2 + 2; /*identique à n=p+2; */(*ad1)++; /* identique à n++;*/ad++;ad += 10;ad -= 25;n= ad1-ad2;

Quelques éléments de syntaxe

Représentation graphique

affectations• int *ptP; int p;• ptP = &p; *ptP = 3;

ptP p


Affectations• int *ptP; int p;• ptP = &p; *ptP = 3;

ptP p


affectations• int *ptP; int p;• ptP = &p; *ptP = 3;

ptP p

3


affectations:• int **ptPtP; int * ptP; int p;• ptP = &p; *ptP = 3;

• ptPtP = &ptP;

ptP pptPtP

3


ptP pptPtP

3

affectations:• int **ptPtP; int * ptP; int p;• ptP = &p; *ptP = 3;

• ptPtP = &ptP;


ptP pptPtP

34x

affectations:• int **ptPtP; int * ptP; int p;• ptP = &p; *ptP = 3;• ptPtP = &ptP;• **ptPtP = 4;

Pointeur NULL

affectations:• #include <iostream> pour la définition de NULL mais il est préférable en C++ d’utiliser 0 à la place.• *ptPtP = 0; /* utile pour tester */

ptP pptPtP

4X


affectations:

• *ptPtP = 0; /* utile pour tester */• if (*ptPtP == 0) …

(p est toujours accessible par son nom!!)

ptP pptPtP

4

Pointeur NULL: affectation

affectations:

• *ptPtP = 0; ptPtP = 0; (et non l’inverse!!!)

ptP pptPtP

4X


affectations:

• *ptPtP = 0; ptPtP = 0;• if (ptPtP == 0) ...

ptP pptPtP

4

Affectations de pointeurs

On peut affecter un pointeur à une variable pointeur de même type.

Sauf:• si on affecte l ’entier 0 (pour NULL)

• pt1 = 0; • ou un pointeur de type générique void *, un pointeur qui

accepte de prendre pour valeur l’adresse de n’importe quel objet, quel qu’en soit le type.

void * ptr = 0; //un pointeur génériqueint entier = 4;ptr = &entier; //un pointeur générique peut désigner un int..char lettre = ‘c’;ptr = &lettre; //..ou un char…

Cependant, on ne peut déférencer un pointeur générique sans recourir au

transtypage (casting).

Pointeurs génériques

Transtypage d’adresses en C++

Le transtypage d’une adresse peut être effectuée à l’aide de l’opérateur static_cast < > ( ) qui exige deux opérandes: le type souhaité et la valeur à convertir. Comme tous les autres opérateurs de transtypage, ils sont dénués d’effet.

Exemple.

double uneVariable = -3.92;void* ptr = &uneVariable;int i = 18;double * ptrDouble;*static_cast <double *> (ptr) = 2.4; //uneVariable prend la valeur 2.4ptrDouble = static_cast <double *> (ptr); //ptrDouble pointe

uneVariablecout << *static_cast <double *> (ptr) << endl;ptr = &i; // ptr pointe maintenant sur la variable entière i

Pointeurs sur structures ou classes

Exemple

struct Pixel { unsigned char r,g,b;};struct Image {

Pixel *bitmap;int largeur;int longueur;

};

Image temp, *ptr;(...)ptr=&temp;cin >> ptr->Largeur >> (*ptr).Longueur >> ...;//Ptr->Largeur est la même chose que (*Ptr).Largeur

int largeur

int longueur

char g

char b

char rImage temp

Pixel

ptr

...

char g

char b

char r

char g

char b

char r

Passage de paramètres

Types de passage de paramètres en C/C++

Passage par valeur

Passage par adresse

Passage par référence (seulement en C++)

Passage par valeur, exemple

#include <iostream>#include <string>using namespace std;

string MettreEnMajuscule (string texte){ unsigned int dim = texte.size(); for (int i=0; i<dim; i++) { texte[i] = toupper(texte[i]); } return texte;}

int main(){ string nom = "programmation"; string NOM = MettreEnMajuscule(nom);

cout << "Minuscule : " << nom << endl; cout << "Majuscule : " << NOM << endl; return 0;

}

Résultat:Minuscule : programmationMajuscule : PROGRAMMATION

Passage par adresse, exemple

Département d’informatique et de génie logiciel

23


string MettreEnMajuscule (string* texteP){ unsigned int dim = texteP->size(); for (int i=0; i<dim; i++) { (*texteP)[i] = toupper((*texteP)[i]); } return *texteP;}

int main(){ string nom = "programmation"; string NOM = MettreEnMajuscule(&nom);


}

Passage par pointeur :Accès direct aux données originales

Résultat:Minuscule : PROGRAMMATIONMajuscule : PROGRAMMATION

Les références

Exemple :

int i; int & ir = i; // ir référence à iint *ptr;i=1;

cout << "i= " << i << " ir= " << ir << endl;// affichage de : i= 1 ir= 1

ir=2;cout << "i= " << i << " ir= " << ir << endl;// affichage de : i= 2 ir= 2

ptr = &ir;*ptr = 3;cout << "i= " << i << " ir= " << ir << endl;// affichage de : i= 3 ir= 3

Passage par référence, exemple


string MettreEnMajuscule (string& texte){ unsigned int dim = texte.size(); for (int i=0; i<dim; i++) { texte[i] = toupper(texte[i]); } return texte;}



}

Passage par référence :Accès direct aux données originales

Résultat:Minuscule : PROGRAMMATIONMajuscule : PROGRAMMATION

Passage par référence constante

• Le langage C++ offre donc la possibilité de protéger les données originales en utilisant le passage par référence ET le mot const.

• Il n'y a plus de coût associé à la copie des données et il n'y a plus de risque de modification des données originales.

• Le passage par référence constante donne le même résultat que le passage par valeur, la copie en moins !

Passage par référence constante, exemple


string MettreEnMajuscule (const string& texte){ unsigned int dim = texte.size(); string texte2 = texte; //ou string texte2(texte);

for (int i=0; i<dim; i++) { texte2[i] = toupper(texte[i]); } return texte2;}



}

Passage par référence constante :Accès direct aux données originalessans pouvoir les modifier.

Résultat:Minuscule : programmationMajuscule : PROGRAMMATION

Conclusion sur le passage de paramètre

Ne jamais utiliser le passage par valeur sauf pour les types de base du langage.

Toujours utiliser le passage par référence constante si on désire que les données originales ne soient pas modifiées.

Toujours utiliser le passage par référence si on désire que les données originales soient modifiées.

Le passage par pointeur pourra être utilisé dans quelques rares cas, notamment pour le polymorphisme (voir le cours de POO).

Les pointeurs et le calcul d’adresses

Si ptr est un pointeur:

*ptr : retourne le contenu de la case mémoire pointée par ptr

ptr+i :nouveau pointeur qui pointe i cases plus loin que la case pointée par ptr

*(ptr+i) : retourne le contenu la ième case après la case pointée par ptr

ptr[i] : même chose que *(ptr+i)

Calcul d’adresses

int note[4]={56, 23,67,89}; int *liste; note[i] = *(note+i) = *(note+i); liste=note; liste[i] = *(liste+i) = *(liste+i); cout << note << liste; cout << *++liste; cout << ++*liste; cout << *liste++; cout << *liste); cout << liste-note << endl;

0 1 2 3

noteliste

Qu’affiche le programme suivant?

Exemple: strlen de <cstring>

strlenV1: utilisant un tableau strlenV2: utilisant un pointeur strlenV3: calcul d’adresse appel: strlen(tab), strlen(“bonjour”), strlen(chaine) autres appels: strlen(&tab[3]), strlen(&chaine[4])

b o n j o u r \00 1 2 3 4 5 6 7

tab

chaîne

int strlenV3(char *ch ){ char *debut;

/*A: ch contient le caractère '\0' */

debut = ch;while (*ch != '\0') ch++;

return ch - debut;}

Calcul d’adresses

char *tab[ ] = { "Eleves","Prof","Stage"};

tab : est équivalent à : &tab[0] : c'est l'adresse du premier élément du tableau.

*tab : est équivalent à : tab[0] : c'est le premier élément du tableau, c'est à dire l'adresse du premier caractère de la chaîne "Eleves".

tab[1] : est l'adresse sur le premier caractère de la chaîne "Prof". *(tab+1) : est équivalent à : tab[1]

Calcul d’adresses

char *tab[ ] = { "Eleves","Prof","Stage"};

*tab[1] : est le caractère pointé par tab[1] : c'est le caractère 'P' de la chaîne "Prof".

**tab : est équivalent à : *tab[0] :c'est le caractère 'E' de la chaîne"Eleves".

**(tab+1) : est équivalent à : *tab[1] :c'est le caractère 'P' de la chaîne"Prof".

*(tab[2]+1) : est équivalent à : tab[2][1] :c'est le caractère 't' de la chaîne"Stages".

Pointeur sur une fonction

int tab[10]; tab est l'adresse du premier octet du tableau.

void fonctionQc(int i, int j){…} À l’instar du nom d’un tableau, fonctionQc est

l'adresse du premier octet implantant la fonction.

Comme le nom d’une fonction est une adresse, il est alors possible de déclarer une variable de type pointeur sur la fonction :

void (*f)(int, int);

À la déclaration, il faut définir : le type des paramètres le type de retour

Exemple

int addition(int i, int j);

int main(){

int (*fonction)(int, int); /*déclaration d'un pointeur sur une fonction*/int i=1, j=2, k; //déclaration de 3 entiers

fonction = &addition; // ou bien fonction = addition

k = fonction(i,j); k = (*fonction)(i,j);k = addition(i,j);k = (*addition)(i,j);

return(0);}

Un pointeur sur une fonction comme paramètre d'une fonction

void tri(int *tab, int size, bool (*compare)(int, int)){ void swap(int *, int *);

for (int idx = 1; idx <= size - 1; idx++) for (int count = 0; count <= size - 2; count++) if ((*compare)(tab[count], tab[count + 1])) swap(&tab[count], &tab[count + 1]);}

L'ordre du tri est défini par la fonction compare

Exemple

Les pointeurs aux fonctions peuvent toujours être remplacés par des fonctionnalités du C++ comme les « fonctions virtuelles » ou les génériques (« templates »). Mais ils tendent à revenir d’usage dans les librairies les plus sophistiquées et les mieux conçues.

3 grandes zones de mémoire:

Zone de la pile d'appel (variables locales, arguments de fonctions)

Zone d'adressage statique (variables globale et statique)

Zone d'allocation dynamique sur le tas/monceau (heap)

Les types de mémoire

Gestion dynamique de la mémoire

Les deux premières zones ont leur utilité mais demeurent insuffisantes pour la plupart des programmes sérieux.

Dans un programme, on ne peut estimer la quantité de mémoire nécessaire prévoir à quel moment celle-ci sera nécessaire

Réserver une très grande partie de la mémoire simplement parce qu'on prévoit en avoir besoin?

Utiliser l'allocation dynamique pour obtenir et libérer de la mémoire lorsqu'on en a vraiment besoin.

Zone d’allocation dynamique



Le monceau (heap) est le nom de la zone mémoire qui sert à l'allocation dynamique de blocs de mémoire de taille variable.

Le seul risque est la fragmentation du heap, par allocation et libération successives. Il n'existe pas en C++ (comme en C) de mécanisme de "ramasse-miettes" comme dans le langage Java (garbage collector).

L'allocation de mémoire dynamique a tendance à être un peu plus problématique pour le programmeur. C’est lui qui l'alloue, qui la gère et qui n'oublie pas de la rendre au système quand il n'en a plus besoin (comme en C). Sinon, attendez vous à des problèmes!!! Pour une application sérieuse, i.e. une application vouée à

fonctionner pendant des jours et des jours sans corrompre sa mémoire, les «déchets» (ou «memory leaks») ne sauraient être tolérés. Il faut toujours libérer la mémoire qui a été allouée sur le monceau.

Pour allouer de la mémoire dynamiquement. opérateur new :

X* p = new X(arguments du constructeur);

On doit absolument récupérer l'espace alloué par le new sur le monceau

sinon on laisse des déchets (memory leaks). Appel de l'opérateur delete de la mémoire obtenue à partir d'un new :

delete p;

En C++


1) Soit le pointeur int *ptr = 0;

int*int*

ptrptr

00

int*int*

ptrptr2)2) On alloue un espace mémoire à l’endroit où le pointeur pointe, avec ptr = new int;

intint


int*int*

ptrptr3)3) On libère l’espace mémoire alloué avec delete ptr;

intint !!

Double indirection ou pointeur **

Soit int **ptr:

int**int**

ptrptr

int**int** int*int*

int**int** int*int*

ptr = new int*

ptrptr

*ptr = new int intint

ptrptr

Il s’agit donc d’un pointeur sur un pointeur (ou sur un tableau de pointeurs)


Tableau dynamique


Lorsqu'on a terminé avec l'usage de la mémoire: delete [] tab; L'opérateur delete libère l'espace mémoire alloué par new à un seul

objet, tandis que l'opérateur delete[] libère l'espace mémoire alloué à un tableau d'objets.

// il est sage de toujours initialiser// les pointeurs (au moins à NULL = 0)int *tab = 0, nb(5);

// réserve l'espace pour 5 entiers et // renvoie l'adresse du premier octet// ou ??? en cas d’échectab = new int[nb];

tab

Pile

Monceau

struct date {int jour, mois, an; };date *ptr4, *ptr5, *ptr6, d = {25, 4, 1952};

ptr4 = new date; // allocation dynamique d'une structure ptr5 = new date[10]; // allocation dynamique d'un tableau de structureptr6 = new date(d); // allocation dynamique d'une struct. avec init.…delete ptr4; //Rappel: après l’exécution de delete, l’espace mémoiredelete[] ptr5; //est désalloué, mais les pointeurs continuent de pointer à// cet endroit. Il faut donc prendre la bonne habitude de le mettre à NULL // (ou plutôt 0)

int *p =0, *r =0;double *q =0;

p = new int; // p pointe vers un nouvel entierq = new double[10]; // q pointe vers un tableau de 10 doublesr = new int(10); // allocation d'un entier avec initialisation...delete p; // l'espace mémoire de l'entier est libérédelete[] q; // l'espace mémoire du tableau est libéré…

Exemples


int * p = (int*)malloc(sizeof(int)); free(p); p = 0;

double * q = (double*)calloc(10,sizeof(double)); q = (double*)realloc(q,100*sizeof(double)); free(p); p = 0;

int * p = new int; delete p; p =0;

double * p = new double[10]; delete[] p; p = 0;

En C

En C++


La fonction realloc du C, n'a pas d’équivalent en C++. Cela ne cause cependant aucun inconvénient puisque les tableaux peuvent êtreremplacés par des variables de type vector qui éliminent, à toute fin pratique, les problèmes de redimensionnement.

Différence entre le C et le C++

Se créer un tableau dynamique 2D

Exemple

#include <new>

int ** tableau2d(int dim1,int dim2){

int **p;if (( p = new(nothrow) int*[dim1])== 0) return 0;

for ( int i = 0; i < dim1; i++)if ((p[i]= new(nothrow) int[dim2])== 0) return 0;

return p;}


Désallocation d’un tableau dynamique 2D

Exemple d’une fonction de désallocation :

void detruitTableau2D( int ** & p, int dim1, int dim2){

for ( int i = 0; i < dim1; i++)delete [] p[i];

delete []p;p = 0;

}


double ** allocMatrix(int n, int m) {

double ** m = new double*[n];

for(int i=0; i< n; ++i) m[i] = new double[m];

return m; }

void freeMatrix(double ** &m, int n) {

for(int i=0; i< n; ++i) delete[] m[i];

delete[] m; m = 0;

}

Autre exemple

Allocation d’unematrice nxm.


Libération de l’espace mémoireAlloué pour lamatrice

Chaînes de caractères dynamiques

Puisqu’une chaîne de caractères n’est finalement qu’un tableau de caractères, on peut en faire une version dynamique.

#include <new>…char *x;x = new(nothrow) char[strlen(‘’Bonjour’’)+1];if(!x) { // Erreur…l’allocation a échoué }//Si l’allocation a réussi, la ligne suivante peut se faire…strcpy(x, ’’Bonjour’’);cout << x << endl;delete[] x;

À ne pas oublier!

Chaînes de caractères dynamiques

Puisqu’une chaîne de caractères est un tableau, si on veut faire un tableau de chaînes de caractères, on a alors à faire à un tableau de tableaux.

On a le choix entre:

Un tableau statique de chaînes de caractères statiques Un tableau dynamique de chaînes de caractères statiques Un tableau statique de chaînes de caractères dynamiques Un tableau dynamique de chaînes de caractères dynamiques

La librairie standard de C++ met à notre disposition le type string (en réalité une classe), permettant une représentation efficace des chaînes. Bien sûr, on pourra parler également de tableaux de string voire des vectors de string. La version des chaînes que nous avons invoquer, bien que reconnue en C++, est attachée plutôt au langage C. Nous aurons l’occasion dans le cours de présenter les types string et vector.

Les tableaux à plusieurs dimensions

Comme pour les tableaux de chaînes de caractères, l’utilisation de n’importe quel tableau à plusieurs dimensions implique un choix « dynamique » ou « statique » pour chaque dimension.

Par exemple, un tableau de « int » à trois dimensions peut être déclaré de 8 façons différentes:1. int x[2][3][4]; // 2 tableaux de 3 tableaux de 4 ints.2. int *x[2][3]; //2 tableaux de 3 tableaux d’un nombre variable de ints.3. int **x[2]; // 2 tableaux de nombres variables de tableaux à taille

variable de ints.4. int ***x; // Nombre variable de tableaux à tailles variables de

tableaux à tailles variables de ints.5. int (*x)[3][4]; // Nombre variable de tableaux de 3 par 4 ints.6. int (**x)[4]; // Nombre variable de tableaux à tailles variables de 4

ints.7. int (*x[2])[4]; // 2 tableaux d’un nombre variable de tableaux de 4

ints.8. int *(*x)[3]; // Un nombre variables de tableaux de 3 tableaux de

nombres variables de int.

Allocation dynamique de la mémoire• Obtenir des variables (de la mémoire)

• selon les besoins de l’application• gestion dynamique de la mémoire• mais: variables sans noms!• => accès par pointeur

debut

Utilisation des pointeurs

Liste simplement chaînée

Objets chaînésstruct Noeud {

int el; /* l’information à stocker */Noeud*suivant;

} ;

Noeud *debut, *courant, *nouveau;Noeud t1, t2, t3;debut = &t1;

debut el

suivant

t1

el

suivant

t2

el

suivant

t3

courant

• t1.el = 3; ou (*debut).el = 3; ou debut->el = 3;

debut el

suivant

t1

3

el

suivant

t2

el

suivant

t3

courant

Accès aux objets pointées

• t1.el = 3; ou (*debut).el = 3; ou debut->el = 3;• t1.suivant = 0; ou (*debut).suivant = 0 ou

debut->suivant = 0;

debut el

suivant

t1

3

el

suivant

t2

el

suivant

t3

courant


• t1.el = 3; ou (*debut).el = 3; ou debut->el = 3;• t1.suivant = NULL; ou (*debut).suivant = 0 ou

debut->suivant = 0;• t1.suivant = &t2; ou (*debut).suivant = &t2 ou

debut->suivant = &t2;

debut el

suivant

t1

3

el

suivant

t2

el

suivant

t3

courant




debut->suivant = &t2;• debut->suivant->el = 4;

debut el

suivant

t1

3

el

suivant

t2

el

suivant

t3

courant

4




debut->suivant = &t2;• debut->suivant->el = 4;• debut->suivant->suivant = 0;

debut el

suivant

t1

3

el

suivant

t2

el

suivant

t3

courant

4


• courant = debut->suivant;

debut el

suivant

t1

3

el

suivant

t2

el

suivant

t3

courant


• courant = debut->suivant;• (*courant).el = 4; ou courant->el = 4;

debut el

suivant

t1

3

el

suivant

t2

el

suivant

t3

courant

4


• courant = debut->suivant;• (*courant).el = 4; ou courant->el = 4;• (*courant).suivant = 0; ou courant->suivant = 0;

debut el

suivant

t1

3

el

suivant

t2

el

suivant

t3

courant

4


• courant = debut->suivant;• (*courant).el = 4; ou courant->el = 4;• (*courant).suivant = 0; ou courant->suivant = 0;• courant->suivant = &t3;

debut el

suivant

t1

3

el

suivant

t2

el

suivant

t3

courant

4


• courant = debut->suivant;• (*courant).el = 4; ou courant->el = 4;• (*courant).suivant = 0; ou courant->suivant = 0;• courant->suivant = &t3;• courant = courant->suivant;

debut el

suivant

t1

3

el

suivant

t2

el

suivant

t3

courant

4


• courant = debut->suivant;• (*courant).el = ...; ou courant->el = ...;• (*courant).suivant = 0; ou courant->suivant = 0;• courant->suivant = ...;• courant = courant->suivant;

debut el

suivant

t1

3

el

suivant

t2

el

suivant

t3

courant

4 ...



debut el

suivant

t1

3

el

suivant

t2

el

suivant

t3

courant

4 ...



debut el

suivant

t1

3

el

suivant

t2

el

suivant

t3

courant

4 ...



debut el

suivant

t1

3

el

suivant

t2

el

suivant

t3

courant

4 ...


Allocation de mémoire

obtenir les objets au besoin:• debut = new Noeud;

• réserve de l’espace sur le « heap » (tas)• retourne un pointeur sur un objet un Noeud• lance une exception si plus de mémoire

debut el

suivant

taspile



debut el

suivant

taspile




• debut->el = 3; debut->suivant = 0;


debut el

suivant

taspile

3

debut el

suivant

taspile

3





Libération de mémoire




• delete debut;debut = 0;/* et non l’inverse */

debut el

suivant

taspile

3






debut el

suivant

taspile

3x


debut el

suivant

taspile

3x






debut el

suivant

taspile

3




• debut = 0;delete debut;/* et non l’inverse */

debut = new Noeud;debut->el = 3;debut->suivant = NULL;debut = new unNoeud;

debut el

suivant

taspile

3

Chaînage d’objets

debut el

suivant

taspile

el

suivant

3

debut = new Noeud;debut->el = 3;debut->suivant = NULL;debut = new Noeud; //non, il faut utiliser un autre //pointeur que debut, le sommet de la liste chaînée en//construction, pour poursuivre la//construction de la liste chaînée


Érreur à éviter car, entre autres, on acréé un déchet (memory leack)

/* pour le premier élément */debut = new Noeud;debut->el = 3; debut->suivant = 0;courant = debut;

/* pour les autres éléments */nouveau = new Noeud;nouveau->el = ...;nouveau->suivant = 0;courant->suivant = nouveau;courant = nouveau;

debut

taspile

nouveau

courant


debut el

suivant

taspile

nouveau

courant




debut el

suivant

taspile

3

nouveau

courant




debut el

suivant

taspile

3

nouveau

courant




debut el

suivant

taspile

3

courant

nouveau




debut el

suivant

taspile

3

nouveau

courant

el

suivant




debut el

suivant

taspile

3

nouveau

courant

el

suivant

...




debut el

suivant

taspile

3

nouveau

courant

el

suivant

...




debut el

suivant

taspile

3

nouveau

courant

el

suivant

...




debut el

suivant

taspile

3

nouveau

courant

el

suivant

3

...




debut el

suivant

taspile

3

nouveau

courant

el

suivant

3

...




debut el

suivant

taspile

3

nouveau

courant

el

suivant

3

...

el

suivant




debut el

suivant

taspile

3

nouveau

courant

el

suivant

3

...

el

suivant

...




debut el

suivant

taspile

3

nouveau

courant

el

suivant

3

...

el

suivant

...




debut el

suivant

taspile

3

nouveau

courant

el

suivant

3

...

el

suivant

...




debut el

suivant

taspile

3

nouveau

courant

el

suivant

3

...

el

suivant

...




Constructeur!!




On est en présence ici de 2 parties de code identiques, on va les rassembler dans une fonction/méthode appelée constructeur.

struct Noeud {

int el; // l’information à stocker Noeud*suivant; // lien avec le suivant

Noeud (const int& data_item, Noeud* next_ptr = 0) : el(data_item), suivant(next_ptr) {} //constructeur} ;


/* pour le premier élément */debut = new Noeud(3);courant = debut;

/* pour les autres éléments */nouveau = new Noeud(…);courant->suivant = nouveau;courant = nouveau;

debut

taspile

nouveau

courant


debut

taspile

nouveau

courant

el

suivant

33




debut

taspile

nouveau

courant

el

suivant

33




debut

taspile

nouveau

courant

el

suivant

33

el

suivant

...




debut

taspile

nouveau

courant

el

suivant

33

el

suivant

...




debut

taspile

nouveau

courant

el

suivant

33

el

suivant

...




debut

taspile

nouveau

courant

el

suivant

33

el

suivant

...




Liste simplement chaînée


Le C++, comme le C, n'offre pas de mécanisme de récupération automatique de la mémoire (garbage collecting). Attention donc aux déchets (memory leack).

Allocation et libération des ressources : la responsabilité du programmeur et attention aux références pendantes!

Pour gérer les ressources à l'intérieur des classes, il faut correctementimplanter certaines fonctions/méthodes pour ne pas se retrouver avec des problèmes. Nous en reparlerons.

Rappels et mise en garde!

Copies profondes et copies de surface

Lorsqu’une structure a un membre qui est un pointeur, copier le contenu de la structure d’une variable à une autre avec l’opérateur « = » ne va que copier le contenu du pointeur en question. Ainsi, les deux variables partageront un même espace-mémoire.

Par exemple, si on fait delete sur l’une des copies, alors la deuxième copie n’est plus utilisable non plus et fera planter le logiciel.

Noeud n1(10), n2;

n2 = n1; // Dangereux!

Nous verrons bientôt comment régler ce problème par le biais de la surcharge de l’opérateur d’affectation.

Annexe mathématique (analyse d’algorithmes)

• Les séries simplifiées• Rappel sur les logarithmes• Règles de simplification dans la notation O()

En plus, voir document RappelsMath.pdf sur le site Web du cours.

Laboratoire #2

Surcharge de fonctions Les références Le mot clé const

const int x=22;const int *p = &x;*const_cast<int*>(p) = 44;

Le mot clé static Les tableaux à plusieurs dimensions Les itérations

Quelques éléments techniques du C++

Documentation: acétates du cours (semaine #2) ainsi que desdocuments sur le C++ sur le site Web du cours (C++ Primer/Du C au C++).

Éléments du C++ à voir dans la semaine

Rappel (semaine 1)

Du C au C++Les entrées/sorties (important pour cette semaine)L'espace de nommageLes types vector et string

Cette semaine

Concepts orientés objet Classe et objet

Le point sur les normes de programmation

Normes de programmation:

• Commentaires d’interface• Commentaires d’implémentation• Découpage logique d’un programme• La gestion des exceptions• Style de programmation

Voir sur le site Web du cours, section Documentations/Normes de programmation:

•NormesProgrammation.pdf•Resume.h (à propos des commentaires Doxygen)

//Fichier ModeleImplantationListe.h#ifndef _LISTEC__H#define _LISTEC__H#define MAX_LISTE 100typedef enum {FAUX, VRAI} Bool;

typedef struct{

int tab[MAX_LISTE];int cpt;

} Liste; #endif

//Fichier Liste.h#include "ModeleImplantationListe.h"#include "CodesErreur.h"

Liste initListe(int * err);/* */int tailleListe(Liste l, int *err);/* */Bool estVideListe(Liste l, int *err);/* */Liste ajouterListe(Liste l, int x, int pos, int *err);/* */// etc..

// Fichier Liste.h#include <iostream>

#ifndef _LISTEC__H #define _LISTEC__H

class Liste {public: Liste(); //constructeur ~Liste(); //destructeur void ajouter (int x, int pos)

throw(range_error, length_error); int taille() const ; bool estVide() const; //etc…private: static const int MAX_LISTE = 100; int tab[MAX_LISTE]; int cpt;

};#endif

Interface en C++

Interface en C

Retour sur l’interface d’un type abstrait

C’est la partie publique

Spécifications « langage C »

Exemple: ajout dans une liste ordonnée L L +i x

• prototype de la fonction implantant l’opérateur:• Liste ajouterListe(Liste l, TypeEl x, int i, int *err);

• préconditions conditions devant être vraies au départ pour assurer le bon fonctionnement de l ’opérateur

• l ne doit pas être pleine et i [1,|L|+1]

• postconditions conditions étant vraies (observables) après l’application (correcte) de l’opérateur

• l contient x et *err = OK si les préconditions sont respectées• l est inchangée sinon et

*err contient:PAM si L est pleine,PERR si i [1,|L|+1]

• valeur retournée en output de l’application de l ’opérateur:• l mise à jour ou l inchangée en cas d'erreurs

// Le type Liste

class Liste{

public://L'interface...

/**

* \brief Ajouter un nouvel élément dans la liste

*

* \pre il y a assez de mémoire pour ajouter l'élément x

* \pre la position d'ajout, pos, est comprise entre 1 et |L|+1

*

* \post la liste comprend un élément de plus

* \post la liste est inchangée sinon

*

* \exception range_error si la position est erronée

* \exception length_error si pas assez de mémoire

*/

void ajouter(int x, int pos) throw(range_error, length_error);

...

private:

...//Modèle d'implantation

};

Fichier Liste.h

Spécifications « C++ » (version Doxygen)

L'interface...

/**

* \brief

*

* \pre

* \pre

*

* \post

* \post

*

* \exception

* \exception

*/

Résumé des balises de Doxygen

Implémentation...

/**

* \fn

*

* \param[in]

* \param[out]

*

* \return

Section Documentations/Normes de programmation:

•Resume.h (à propos des commentaires Doxygen)

Avantages des TDA

Écriture de programmes en couches : •la couche supérieure traite le problème dans les termes du domaine

de problèmes•Empiler (x, P)

•la couche inférieure entre dans les détails du langage de programmation

•tab[sp++] = x

Séparation claire •des offres de service •du codage

Et..•facilité de compréhension et d'utilisation des modules de codes•prise en compte de types complexes•briques d'une structuration modulaire rigoureuse•introduction à la programmation objet

Théorie du contrat

Non-respect de la théorie du contrat• On modifie sauvagement les

données dans structures à tous les endroits où on a besoin des structures. On considère que tous les membres de la structure sont accessibles.

• Ça semble plus facile à faire pour un débutant.

• Un changement de conception d’une structure devient impossible dès que le logiciel prend de l’envergure.

Respect de la théorie du contrat

• L’idée est de préparer le logiciel à un changement radical du contenu de la structure.

• On passe obligatoirement par des fonctions pour accéder aux membres structures.

• On ne fait jamais de supposition sur l’existence de tel membre.

• Plus difficile à réaliser pour un débutant.

• Ça facilite les changements de conception de structures.

Avantages des TDA

Avantages des TDAstruct Boite{int taille;int direction;} ; /*définition d’un modèle interne pour un type Boite*//*Les opérateurs du type Boite*/int getTailleBoite(Boite b); /* Retourne la taille de b*/Boite setTailleBoite(Boite b, int nouvelleTaille); /*Assigne une nouvelle taille à b*/Boite augmenterTailleBoite(Boite b, int i); /*Augmente la taille de b d’une valeur égale à i */

Ce programme brise l’encapsulation, à la ligne 4: il y a non respect de la théorie du contrat.

int main(){ Boite b; // ligne 1

int t; // ligne 2 ... // ligne 3 t = b.taille; // ligne 4 t = t+5; // ligne 5 b=setTailleBoite(b,t); // ligne 6 ...}

Exemple

Inconvénients des TDA

L'utilisateur d'un TDA connaît les services mais ne connaît pas leur coût.

Le concepteur du TDA connaît le coût des services mais ne connaît pas leurs conditions d'utilisation.

Le choix des primitives est quelque fois difficile à faire.

Documents

Structures de données IFT-2000 Abder Alikacem Pointeurs, références et gestion dynamique de la mémoire. QQ éléments techniques du C++. Semaine 2 Département