Nous voici encore une fois réunis pour une nouvelle ballade du côté du merveilleux monde de Oui-Oui et de son ami Cplusplusi... non, je rigole. Sachez que les informaticiens n'ont pas d'humour.

Aujourd'hui, nous allons parler de quelque chose de très utilisé et de très bien (l'un implique l'autre, à vous de deviner dans quel ordre!) : l'allocation dynamique de la mémoire. Jusqu'ici, nous n'avons vu que des variables dont nous connaissions l'existance dès le début du programme : un compteur i, un pointeur p, etc... Mais il existe bien des cas où le nombre de variables (ou plutôt où la quantitée de données) n'est pas connue au moment de l'exécution du programme. Par exemple, revenons un peu sur les structures. Nous souhaitons faire un carnet d'adresses, et nous rassemblons toutes les données concernant une personne dans une struct, appelons-là Pers. Pour l'instant, pas de problème. Par contre, on ne sait pas combien de personnes nous allons avoir dans notre carnet d'adresses. Il pourrait y en avoir 10 comme il pourrait y en avoir 1000.

Comme nous le faisions jusqu'ici, il nous faudrait créer un tableau de 1000 instances de Pers. Deux problèmes viennent alors nous compliquer la vie : 1000 instances de Pers occupent la mémoire, alors que nous n'avons que 10 personnes inscrites dans notre carnet. Second problème : et si on à 1000 contacts, et qu'on veut en rajouter un? Faut-il recompiler le programme?

L'allocation dynamique de mémoire va nous permettre de régler ce problème : nous allons tout simplement demander au langage, au cours de l'exécution du programme, de nous créer en mémoire une nouvelle instance de Pers à chaque fois qu'il nous en faut une. Ainsi, pas de problème d'instances inutilisées, et pas non plus de problème de "surpopulation".

Avant tout, voyons comment fonctionne la mémoire.

Les deux visages de la mémoire : Pile et Tas

Les programmes ont deux endroits où stocker des variables : la pile et le tas. La pile (ou stack en anglais) est l'endroit où sont créées toutes les variables qu'on déclare de manière classique dans un programme.

Il faut voir la pile comme une pile d'assiettes : on ajoute des assiettes en haut, mais on ne peut retirer que celle du haut. Si on veut retirer la troisième (je dis bien "retirer". On peut connaître la valeur d'une variable quelque soit sa position en mémoire, grâce aux pointeurs), il faut d'abord retirer les deux précédentes. C'est ce qu'on appelle une pile LIFO : Last In First Out (dernière rentrée, première sortie). On comprend alors aisément que le compilateur a besoin de toutes les informations dès la compilation pour pouvoir manipuler correctement la pile.

Lorsque vous passez des paramètres à une fonction, leurs valeurs sont recopiées dans la pile afin que la fonction en question puisse les utiliser pour elle, sans modifier la variable d'origine. Ensuite, lorsque la fonction se termine, toutes les variables qu'elle a créé dans la pile sont effacées, et la pile revient à son état initial. En fait, lorsqu'on entre dans une fonction, il se crée une sorte de barrière dans la pile, qui empêche une fonction de voir les variables de la fonction appellante. C'est cette barrière qu'on contourne lorsqu'on déclare une variable globale. Sinon, il faut s'y plier. Là encore, les pointeurs permettent de tricher un peu : on passe l'adresse d'une variable à une fonction, et hop, on peut lire cette variable quelque soit son emplacement. Mais sinon, le principe est là.

Le tas (heap en anglais), lui, s'affranchit de cet ordonnancement. D'ailleurs, un tas, c'est toujours en bordel. Le tas est le second endroit où un programme peut stocker des variables. Il ne contient pas de barrière, et n'est pas ordonné comme la pile. C'est un espace mémoire où l'on alloue et où l'on libère de la mémoire, sans se soucier de ce qu'il y a autour. Cela à ses avantages et ses inconvénients.

La pile, puisqu'elle est si bien ordonnée, n'a pas d'espace vide entre son début et sa fin ; elle est parfaîtement compacte. Le tas, lui, connaît un problème de fragmentation. Voici un exemple de fragmentation :

Au début du tas, on trouve deux espaces mémoires alloués (pour des structs par exemple, comme c'est souvent le cas) : le premier prend 27 octets en mémoire, et l'autre est situé juste derrière. Plus tard, on désalloue l'espace occupé par la première struct, c'est-à-dire qu'on libère les 27 octets. Dès qu'on veut allouer 27 octets ou moins en mémoire, le compilateur va nous donner l'emplacement situé au début du tas, car il y a la place. Le problème vient ici : si on alloue par exemple 24 octets? Il y a alors un "trou" de 3 octets entre le premier espace alloué et le second. Ce "trou" ne pourra être rempli que si on demande une place de 3 octets ou moins. D'ici là, ce sont trois octets de perdus! Si bien qu'à la fin, le tas contient peut-être 680 octets de libres, mais on ne peut plus allouer de la place pour une struct de 9 octets, et on à l'impression d'être à court de mémoire.

Ne vous alarmez pas cependant, il y a plein de place dans le tas, et ce problème ne vous concerne que si vous avez décidé d'utiliser plein de mémoire dynamique.

Un autre désavantage est la performance: la pile est beaucoup plus rapide que le tas, car elle est gérée directement pas le processeur, avec ses registres super-rapides-de-la-mort-qui-tue, alors que dès qu'on veut faire quelque chose avec le tas, il faut faire plein de choses : pour une allocation, par exemple, il faut commencer par rechercher un espace libre, ce qui prend déjà un peu plus de temps. La perte de performance est négligeable si on ne passe pas son temps à allouer de la mémoire, mais elle peut devenir significative si c'est le cas. Si la performance est un problème, il vaut peut-être mieux allouer de la place pour un nombre limité d'objets en mémoire dans la pile, quitte à laisser tomber la flexibilité offerte par le tas.

Là encore, ne vous faites pas trop d'inquiétudes non plus : ce problème de performance sera inexistant pour nous jusqu'à la fin de ce petit cursus d'apprentissage.

Troisième problème, qui lui touche tout le monde : lorsqu'on alloue un espace mémoire dans le tas en C++, on doit également le libérer. Le compilateur ne peut pas savoir le moment où un objet alloué en mémoire n'est plus nécessaire. Le problème est que si le programmeur ne libère pas cet espace mémoire dès que l'objet n'est plus utilisé, c'est de l'espace mémoire perdu temporairement. Si un emplacement mémoire n'est jamais libéré par le programme, c'est le système qui libèrera cet espace à la fin du programme. C'est ce qu'on appelle les fuites de mémoire. Il y a des outils pour analyser les fuites de mémoires des programmes, mais si on ne les utilise pas, on peut ne pas s'en rendre compte! La mémoire est une resource limitée, il faut donc l'utiliser intelligemment, et ne pas la gâcher.

Il faut toujours libérer un espace mémoire que l'on n'utilise plus dès qu'on n'en a plus besoin, afin d'éviter de saturer la mémoire.

L'allocation de mémoire avec new et delete

En C++, deux opérateurs se partagent la tâche d'allocation et désallocation de mémoire : new et delete.

L'opérateur new permet d'allouer de la mémoire. S'il s'appelle new, c'est parce qu'en C++, on considère qu'on crée un nouvel objet d'un certain type. En réalité, avec new, on crée un objet, et l'espace mémoire est implicitement demandé. Une fois l'objet créé sur le tas, new renvoie un pointeur du type de l'objet, qui pointe vers l'objet en question. On peut alors manipuler l'objet, via le pointeur.

Si new n'a pas réussi à créer l'objet en mémoire (faute de place, la plupart du temps), il renvoie la valeur spéciale NULL. On peut ainsi savoir si l'allocation s'est bien passée. Voici tout de suite un petit exemple :

Vous voyez, ce n'est pas vraiment difficile. En fait, dans la pratique, on ne vérifie pas à chaque fois la validité du pointeur, sinon, cela deviendrait trop fastidieux. Cela dépend de votre rigueur : les plus rigoureux voudront vérifier à chaque fois, les autres se contenteront d'espérer qu'il y a assez de mémoire à allouer. C'est surtout vrai dans ce genre d'exemple : il y a toujours la place de mettre une instance de Position en mémoire, étant donné que c'est une toute petite struct. Mais encore une fois, la mémoire est une resource limitée. Vous pouvez vous amuser à voir combien de mémoire vous pouvez allouer dans un programme :

Attention toutefois : faire tourner ce programme n'endommage pas votre machine. Par contre, sauvegardez tous vos documents ouverts (y compris codes sources C++ :-), car votre machine risque de travailler pendant un moment. Lors de mes essais, Windows 98 m'a laissé allouer 120 Mo de mémoire, ce qui est absolument énorme (la quasi totalité de ma RAM). Par contre, j'avais à la fin un fichier d'échange (ou Swap) de 600 Mo sur mon disque dur, devenu plein par ailleurs, et il m'a fallu redémarrer après l'exécution de ce programme, car je n'avais plus de mémoire. Linux n'a pas laissé le programme se terminer : au bout de quelques minutes, il a préférer "tuer" le programme (eh! oui, la gourmandise est un pêché mortel! :-).

Bien, maintenant que nous avons fini de jouer avec notre mémoire, voyons de quoi d'autre sont capables new et delete.

L'allocation de mémoire pour un tableau

Allouer dynamiquement un tableau est une possibilité très appréciée. On peut ainsi créer des tableaux qui ne prennent en mémoire que la place nécessaire. C'est utile lorsqu'on écrit, par exemple, un editeur de texte, qui doit stocker chaque ligne de texte en mémoire. Statiquement, ce n'est pas facile : ou bien on limite la taille de chaque ligne à disons 80 caractères (la largeur de l'écran sons DOS), ou bien on en autorise plus, mais on perd plus de mémoire car toutes les lignes ne seront pas remplies, alors que la mémoire est allouée. Dynamiquement, on peut décider exactement de la taille de chaque tableau, ce qui permet de créer des lignes de la longueur qu'on veut, sans pour autant perdre de mémoire. Voici comment se fait une allocation de mémoire pour un tableau :

Au départ, rien d'imprévisible : un tableau est créé sur le tas avec la syntaxe de la première ligne. Comme un nom de tableau est un pointeur vers le début en mémoire du tableau, rien d'exotique non plus à la déclaration sous forme de pointeur de p, ni à son utilisation (p[i] = 0). Par contre, regardez bien la dernière ligne : le delete est affublé de crochets. Ceci indique au compilateur qu'on désire effacer le tableau entier de la mémoire, et pas seulement le premier élément du tableau, comme il le ferait si on ne mettait pas les crochets. Petite subtilité qu'il faudra retenir :

Un tableau s'alloue sur le tas avec l'écriture : type* var = new type[taille] Il est libéré avec l'écriture : delete[] var

Bien sûr, un tableau est un tableau : pas de différence, donc, si on souhaite créer un tableau de Schmurtz, Schmurtz étant une structure définie plus tôt par vous. On écrira toujours : Schmurtz* p = new Schmurtz[10].

Autre remarque concernant l'allocation de tableaux, illustrée par l'exemple précédent :

Lors de sa création avec new, les cases d'un tableau ne sont pas initialisées.

Allocation de tableaux de tailles non prédéfinies

Dernière précision concernant l'allocation de tableaux : grâce à new, on n'est plus obligé de fournir une valeur constante. Puisque l'allocation est dynamique et qu'elle se fait sur le tas, le compilateur n'a plus besoin de connaître la taille exacte de l'objet. Voici tout de suite une illustration :

Cet exemple fonctionne parfaîtement, et c'est ce qui nous manquait pour réellement rendre cette allocation de tableaux complètement dynamique : création et taille sont décidées au moment de l'exécution. Youpi.

Fin du cours

Voilà un cours important. Assurez-vous bien d'avoir tout compris avant de passer à la suite.

Il est temps de découvrir le programme du jour. Celui-ci est un peu trop long pour être inclus dans cette page, il est cependant présent dans le fichier associé.

Il s'agit de créer un tableau qui se redimensionne au fur et à mesure qu'on y ajoute des éléments. Vous allez voir, ce n'est pas très compliqué. Le tableau n'est pas trié, et ne contient aucune case vide. On procède de la manière suivante : lorsqu'on veut ajouter ou retirer un élément du tableau, on commence par créer un autre tableau, de la nouvelle taille, puis on recopie les valeurs. Si on ajoute un élément, alors on saisit la nouvelle valeur et on la place à la fin du tableau. Si on retire un élément, on se contente de ne pas recopier la valeur à la case qu'on enlève. Tout cela est très simple. Bien sûr, le nouveau tableau est créé avec new, et l'ancien tableau est effacé avec delete[].

Voici maintenant un récapitulatif des points importants :

Contrairement aux variables créées sur la pile, les variables créées sur le tas ne sont détruites que par un appel à delete sur leur pointeur. Elles ne sont pas concernées par la sortie d'une fonction ou d'un bloc. Il faut toujours libérer un espace mémoire que l'on n'utilise plus dès qu'on n'en a plus besoin, afin d'éviter de saturer la mémoire. Un tableau s'alloue sur le tas avec l'écriture : type* var = new type[taille] Il est libéré avec l'écriture : delete[] var Lors de sa création avec new, les cases d'un tableau ne sont pas initialisées

Bien. Pour cette fois-ci, nous allons construire, exercice par exercice, un petit programme sympatique. Nous allons créer un petit carnet d'adresses. Commençons d'abord par introduire une manière de saisir des chaînes de caractères au clavier.

La fonction cin.get() permet de faire ceci de manière correcte. Vous lui indiquez en paramètres le buffer (un tableau de char) et le nombre de lettres qu'il peut stocker dans ce buffer. Ce nombre inclut le '\0' de terminaison, si bien que si votre buffer comporte 30 cases, il faudra indiquer 30. Tout ceci est très simple, et voici un petit exemple d'utilisation :

Petite explication rapide :

• cin.get(buffer, n) prend les n premiers caractères qu'il trouve dans son tampon d'entrée (ou moins s'il rencontre un retour à la ligne avant le n-ième caractère) et les copie dans buffer.
• Le problème, c'est que lorsque le tampon d'entrée de cin n'est pas vide, il se sert de ce qu'il reste pour le cin.get() suivant. Si vous copiez les lignes 3 et 5 (sans la ligne 4) de l'exemple ci-dessus 5 fois dans le programme, et que vous entrez au début une phrase de 64 caractères, il ne s'arrêtera pas au deux prochains cin.get(), car il a déjà des caractères à mettre dans buffer, et donc il le fait sans rien demander à l'utilisateur. Voici une démonstration :

Affichage produit à la fin du programme :

Ce n'est qu'après les 4 premiers cin.get() que l'utilisateur reprend le contrôle. C'est un petit peu facheux. Pour éviter cela, on utilise l'instruction cin.sync(), qui vide le tampon d'entrée de cin. Ainsi ce problème n'apparaît plus : cin.get() prend les 29 premiers caractères qu'il trouve, puis vide le tampon, si bien que vous reprenez le contrôle dès le second cin.get().

Rien de tel qu'un peu de pratique pour mettre tout ça en place. Passons maintenant à nos exercices :

Commençons par créer une struct qui va contenir des informations concernant quelqu'un : son nom, son adresse, son e-mail. Ces trois informations seront placées dans des chaînes de caractères dont la struct contient les pointeurs. Ce sera la struct Contact. Ensuite, écrivez une fonction qui saisisse au clavier les informations concernant une personne. La saisie se fera au moyen de l'instruction cin.get() introduite plus haut. Bien sûr, c'est dans cette fonction qu'on crée les tableaux de char qui vont contenir les chaînes de caractères. En reprenant le programme du jour, faites un petit menu similaire pour notre programme. Adaptez les fonctions pour refaire la même chose que le programme du jour, mais avec des Contacts. Déjà, à ce niveau, nous avons un petit programme sympatique. Ne nous arrêtons pas en si bon chemin. Ecrivez une fonction Compare(char* s1, char* s2) qui compare deux chaînes de caractères s1 et s2 entre elles. La fonction renvoie -1 si s1 est inférieure à s2 (c'est-à-dire si s1 est alphabétiquement placée avant s2), 0 si s1 et s2 sont égales, et 1 si s2 est inférieure à s1. Ainsi : Compare("coucou", "bonjour") renvoie 1 Compare("a", "abc") renvoie -1 Compare("Schtoumpf", "Schtoumpf") renvoie 0 Utilisez la fonction Compare() dans une fonction Trier() qui va trier les Contacts. Cette fonction sera appliquée après chaque entrée de nouvel élément dans la liste. Ajoutez au menu une fonction pour modifier les données d'un Contact. Ecrivez une fonction correspondante. Ecrivez une fonction Contient(char* s1, char* s2) qui renvoie 1 si une chaîne s2 contient s1, 0 autrement. Plus fort : ajoutez au menu une fonction de recherche (on se contentera au début d'une recherche par nom). On entre un nom (ou une partie de nom) et le programme affiche tous les contacts dont le nom contient la chaîne recherchée. Pour revenir à du new et delete, essayez d'ajouter au programme une fonctionalité amusante : la gestion de plusieurs carnets d'adresses. En fait, un carnet d'adresses est un tableau de Contacts. Maintenant, il faut faire plusieurs tableaux de ce type, également de manière dynamique (on peut ajouter et enlever des carnets d'adresses comme on veut). Attention cependant : si l'utilisateur veut enlever un carnet d'adresses, n'oubliez pas de libérer la mémoire prise par tous les Contacts de ce carnet d'adresses. Voilà de quoi travailler un peu.

Voilà, c'est fini pour aujourd'hui. Une fois que vous aurez bien ingurgité new et delete, nous pourrons passer à des choses très amusantes : les listes chaînées et les arbres. Tout cela pour démontrer la puissance des pointeurs. C'est parti !

Voir aussi : Les tableaux (partie chaînes de caractères)