L’allocation dynamique

Qu’est-ce que l’allocation dynamique de mémoire, et à quoi ça sert ?

Pour le moment, lorsque nous écrivons un programme nous devons connaitre à l’avance le nombre de variables que nous allons utiliser (et les tailles exactes de nos tableaux) ainsi que leur durée de vie (qui dépends de l’endroit et de la manière dont on les déclares). Par exemple, dans le programme suivant, j’utilise une fonction qui utilise un tableau de 500 entiers et deux variables entières. Dans la fonction principale, j’utilise un tableau de 1000 entiers et deux autres entiers. Ce dernier tableau va exister durant toute la durée du programme, tandis que celui de la fonction n’existera que durant l’appel de la fonction.

Ces différentes variables et tableaux ont une durée de vie dite automatique. Cela signifie que de la mémoire utilisée pour les stocker est réservée automatiquement au moment de l’entrée dans le bloc d’instructions (délimité par les accolades : { et } ) auxquels ils appartiennent. A la fin de l’exécution de ce bloc, la mémoire réservée pour ces objets est libérée automatiquement.

Un exemple de programme pour lequel on déclare toutes les variables à l'avance
Que fait ce programme
Ce programme n’a pas d’objectif particulier. Il me sert uniquement à illustrer mon propos. Cela étant, comme vous êtes curieux :

  • la fonction eratosthene va utiliser la méthode du crible d’Ératosthène pour déterminer la liste des nombres premiers inférieurs à une certaine valeur passée en argument.
  • Dans la fonction main, le tableau est remplis des 1000 premiers termes de la suite de Syracuse en considérant que le terme initial est le nombre saisi par l’utilisateur.

Dans ce programme, on peut constater plusieurs problèmes :

  • On demande à l’utilisateur de rentrer un nombre. De ce nombre va dépendre le nombre de cases de tableaux que nous allons utiliser. Si l’utilisateur rentre une valeur supérieure à 500, le programme va planter car nous allons déborder de notre tableau qui ne contient que 500 cases. Pour résoudre ce problème, on peut déclarer un tableau beaucoup plus grand, par exemple de taille 1000 ! Mais maintenant, que se passe-t-il si l’utilisateur rentre un nombre encore plus grand ? Nous aurons exactement le même problème de débordement de notre tableau.
  • Au contraire, si l’utilisateur rentre une petite valeur, par exemple 20, notre tableau possède 480 cases qui ne seront pas utilisées. Nous monopolisons de la mémoire pour rien.
  • Le tableau de la fonction main monopolise de la mémoire durant toute la durée u programme, alors qu’on ne l’utilise qu’après l’appel de la fonction crible.
  • Pour changer la taille de notre tableau, notez que nous devons recompiler notre programme.
Problèmes liés à l'allocation automatique et/ou statique
      • De la mémoire est réservée mais inutilisée.
      • Risque de débordement de tableau.
      • Chaque modification de la taille d’un tableau implique de recompiler le programme.

L’allocation dynamique de mémoire va nous permettre de régler ces problèmes. Nous allons demander au système, au cours de l’exécution du programme, de nous réserver en mémoire un espace correspondant à la quantité de donnée que nous devons manipuler. Ainsi, pas de mémoire inutilisée, de débordement de tableau causé par une valeur saisie par l’utilisateur ni de nécessité de recompiler notre programme. Formidable non ?

Les bases de l’allocation dynamique

L’allocation dynamique permet de réserver un espace en mémoire (dans le tas pour être précis). L’intérêt de cette méthode est que nous allons pouvoir utiliser exactement la quantité de mémoire dont nous avons besoin au cours du programme, même si cette quantité nous était inconnue avant son exécution.

La fonction malloc

Nous allons voir tout de suite comment réserver de la mémoire grâce à la fonction malloc. Les autres fonctions d’allocation mémoire constituent des variantes de cette fonction. Il est donc primordiale de la maitriser :

La fonction malloc
La fonction malloc permet de réserver un espace en mémoire. La taille de cet espace doit être exprimé en octets. La fonction retourne l’adresse du début du bloc qui aura été réservé. Si l’opération d’allocation échoue, la valeur NULL est retournée.
Prototype de la fonction : void *malloc(size_t size);

Attention :

  • La fonction malloc n’initialise pas le contenu de l’espace mémoire réservé. Cet espace risque donc de contenir des valeurs résiduelles.
  • Le type size_t correspond à un entier non signé.
  • La fonction malloc retourne un pointeur de type void *.

Soyez attentif au type de retour de la fonction malloc : void *. La raison est simple. La fonction malloc va réserver un espace d’un certain nombre d’octets en mémoire. Cet espace mémoire n’est pas typé en lui même. C’est la manière dont on va lire et écrire dans ce bloc mémoire qui va donner son type aux données. Par exemple, si on considère qu’un int est enregistré sur 4 octets et qu’un char est enregistré sur un octet, on peut se rendre compte qu’un int occupe 4 fois plus de place qu’un char. Si on réserve 4 octets par la fonction malloc, s’agit-il d’un espace pour un int ou d’un espace pour enregistrer 4 char ?

C’est là qu’intervient l’opération de trans-typage. Malloc retourne une adresse dont on ne connait pas le type, ce qui est représenté par le type void *. On va « transformer » ce type par défaut en le type de données que l’on va manipuler dans cet espace. Voici un exemple complet :

Un exemple d'allocation en mémoire grâce à la fonction malloc

Ce programme va réserver un espace mémoire suffisant pour enregistrer un nombre entier. La fonction malloc retourne un pointeur de type void que nous transformons (trans-typons) en pointeur d’entier (soit int *) car nous savons que nous allons manipuler un entier.

Voici l’affichage de ce programme :

exemplealloc11

Bonne pratique
Après un appel à la fonction malloc, vous devez impérativement vérifier si l’allocation s’est bien déroulée. Si l’adresse retournée vaut NULL, c’est qu’un problème a eu lieu et que la mémoire n’a pas été allouée. Lire ou écrire à l’adresse NULL ferait planter le programme, vous ne devez surtout pas tenter d’y accéder.

la fonction free

La mémoire du tas (là où les fonctions d’allocation dynamique réservent la mémoire) est persistante. Cela signifie que si nous réservons de la mémoire, cet espace va rester réservé durant toute l’exécution du programme. Bien entendu, ce qui nous intéresse c’est de n’utiliser la mémoire que quand nous en avons besoin. Donc, des que l’espace mémoire que nous avons réservé ne nous est plus utile, nous devons le libérer. Cette opération de libération de mémoire est TRÈS importante car de nombreux programmes possèdent ce que l’on appelle des fuites de mémoire. Il s’agit de mémoire allouée que l’on a oublié de libérer. Au fur et à mesure de l’évolution du programme, les oublis s’accumulant, la quantité de mémoire disponible va diminuer. On risque ainsi de ne plus pouvoir effectuer le reste de notre programme. Du coup, bugs, plantages, la catastrophe quoi !

La fonction free
La fonction free permet de libérer un espace mémoire réservé au préalable. Pour libérer cet espace, il suffit d’indiquer l’adresse du début du bloc à libérer.
Prototype de la fonction : void free(void *ptr);

En reprenant l’exemple précédent, nous allons juste ajouter la libération de la mémoire allouée :

Un exemple de libération de mémoire grâce à la fonction free

Ce programme va produire l’affichage suivant :

liberationfree

Notez bien que la fonction free n’est appelée que si la mémoire à bien été allouée. Si on essaye de libérer de la mémoire qui n’est pas allouée, cela risque (fortement) de produire une erreur et de faire planter votre programme.

La fonction calloc

Nous allons maintenant voir calloc, une autre fonction d’allocation mémoire, similaire à la fonction malloc.

La fonction calloc
Tout comme la fonction malloc, la fonction calloc va réserver un espace en mémoire. Cette fonction accepte deux arguments, le premier étant le nombre de variables que l’on souhaite réserver et le second étant la taille en octets occupée par chacune de ces variables. Tout comme la fonction malloc, si l’opération échoue alors la valeur NULL est retournée.
Outre la différence de syntaxe avec la fonction malloc, la fonction calloc va initialiser l’espace réservé avec des 0.
Prototype de la fonction : void *calloc(size_t nmemb, size_t size);

Vous l’aurez compris, outre une syntaxe légèrement différente, la vraie différence avec la fonction malloc, c’est que la fonction calloc initialise l’espace mémoire réservé en le remplissant de 0. Plus précisément, tous les bits de l’espace réservé sont placés à 0.

Pourquoi faire deux fonctions ? malloc est plus rapide que calloc. Donc si nous n’avons pas besoin d’initialiser le contenu de l’espace mémoire réservé, il est préférable de faire appel à malloc. Au contraire, si on doit initialiser le contenu de l’espace mémoire à 0, calloc sera plus rapide qu’un malloc suivi d’une initialisation.

Allocation dynamique de tableaux

Nous savons désormais comment réserver de la mémoire. Mais ce que je n’ai pas dit, c’est que ce que nous avons vu permet en fait d’allouer des tableaux de manière dynamique.

En effet, si on réserve de l’espace avec ces fonctions, nous allons obtenir un espace contigu de la taille demandée. Cet espace sera manipulable à partir de l’adresse de son premier octet (retourné par les fonctions d’allocation).

Par exemple, la fonction malloc permet de réserver un espace mémoire pouvant contenir x octets, avec x le nombre d’octets d’un type de variable. Si dans l’appel à la fonction malloc nous ne demandons pas x octets, mais … x*1000, que va-t-il se passer ? malloc va nous réserver un espace en mémoire pouvant contenir 1000 données de x octets et nous retourner un pointeur sur cet espace.

Comment peut-on manipuler cet espace ? Petit exemple :

Un exemple d'allocation en mémoire grâce à la fonction malloc

Pour affecter une valeur au premier espace pouvant contenir un entier (dans les 4 premiers octets), on peut écrire :

Ensuite, pour affecter une valeur au deuxième espace pouvant contenir un entier (dans les 4 octets suivants), on peut écrire :

En effet, il faut se souvenir que lorsqu’on ajoute 1 à un pointeur, on ajoute en fait 1 fois la taille en octets du type pointé, donc dans notre cas, 4.
Plus généralement, pour affecter une valeur au i-ème espace pouvant contenir un entier, on peut écrire :

Or, en langage C, il y a équivalence entre les notations *(ptr+i) et ptr[i]. On peut donc manipuler le pointeur ptr comme un tableau ! La phrase suivante devrait donc prendre tout son sens :

La phrase magique du cours sur les pointeurs
Le nom d’un tableau est un pointeur sur son premier élément !

Voici un exemple complet d’allocation dynamique de tableau :

Un exemple d'allocation en mémoire grâce à la fonction malloc

Ce programme va produire le résultat suivant :

tableau

Les tableaux à deux dimensions

Les choses peuvent se compliquer un tout petit peu si on souhaite allouer dynamiquement un tableau à plusieurs dimensions. Pour comprendre comment faire, analysons le programme suivant, qui va allouer plusieurs tableaux dynamiquement :

Un exemple d'allocations multiples

Ce programme alloue dynamiquement 5 tableaux d’entiers, tous de taille 10, et tab1, tab2, tab3, tab4 et tab5 sont des pointeurs d’entiers qui pointent chacun vers le premier élément d’un tableau différent.

Il est tout à fait possible de regrouper ces pointeurs dans un tableau de pointeurs. Un tableau de pointeurs d’entiers est donc un tableau dont les éléments sont de type int* :

Un exemple d'allocations multiples

Ce tableau de pointeurs peut lui même être alloué dynamiquement. Pour cela, on doit déclarer un pointeur vers des éléments de type pointeur d’entier puis allouer de la mémoire pour stocker des éléments de type int * :

Un exemple d'allocations multiples

Notez bien que tab est donc un tableau de pointeurs. Chacune des cases contient un pointeur vers un espace mémoire que l’on va manipuler comme un tableau. Donc, pour accéder au premier tableau, nous le ferons en écrivant tab[0]. Or, tab[0] étant un pointeur vers le premier élément d’un tableau, on peut accéder à la première case de ce tableau en écrivant : tab[0][0].

Et voila ! Nous venons d’allouer un tableau à deux dimensions !

Pour résumer
  • Pour allouer dynamiquement un tableau d’entier, on déclare un pointeur d’entiers et on alloue de la mémoire pour des entiers.
  • Pour allouer dynamiquement un tableau d’entiers à deux dimensions, on va déclarer un pointeur de pointeurs d’entiers, allouer un tableau de pointeurs d’entiers puis pour chacune des cases de ce tableau on va allouer un tableau d’entiers.
  • On peut continuer de la sorte en allouant des tableaux à 3 dimensions, 4, bref autant qu’on veut 😉

Voici un exemple complet de programme utilisant un tableau à deux dimensions et qui va nous calculer le triangle de pascal :

Un exemple d'allocation en mémoire grâce à la fonction malloc

J’ai volontairement utilisé trop de mémoire dans ce programme. En effet, lorsqu’on commence à allouer dynamiquement des tableaux à deux dimensions, on a tendance à allouer des tableaux dont les dimensions sont régulières. Or, le triangle de Pascal n’a besoin que d’une seule case sur la première ligne, puis de deux sur la deuxième, de trois sur la troisième,…, de i cases sur la ième case. Pour optimiser ce programme et n’utiliser que la bonne quantité de mémoire, il suffit de modifier la ligne 16 par celle-ci :

Maginifique isn’t ?

La ré-allocation de mémoire

Ce que nous venons de voir, c’est que l’allocation dynamique nous permet de réserver de l’espace mémoire même si nous ne connaissons pas la quantité nécessaire avant l’exécution de notre programme. Cependant, nous avons considéré jusqu’ici qu’il existe un certain moment de notre programme à partir duquel nous avons connaissance de la quantité de mémoire à réserver.

Mais supposons un instant que la quantité de mémoire nécessaire à la bonne exécution de notre programme change régulièrement. Comment allons nous faire ?
On pourrait allouer dynamiquement un nouveau tableau à la bonne taille, recopier les données de l’ancien tableau vers le nouveau, puis liberer l’ancien tableau. heureusement, il existe une fonction optimisée qui peut faire cela pour nous :

La fonction realloc
prototype : void *realloc(void *ptr, size_t size);
La fonction realloc permet de changer la taille du bloc mémoire alloué pointé par ptr en le redimensionnant à size octets .

  • Si on diminue la taille du bloc mémoire : Le contenu est inchangé pour l’ensemble du bloc restant.
  • Si on augmente la taille du bloc : la mémoire ajoutée n’est pas initialisée.
  • La fonction realloc retourne un pointeur vers le nouvel espace mémoire alloué.
  • Si la fonction realloc echoue à modifier la taille du bloc, le bloc original n’est pas modifié, ni libéré.

Voici en exemple un programme qui va modifier la taille d’un tableau tant que l’utilisateur ne rentre pas la valeur -1:

Un exemple d'allocation en mémoire grâce à la fonction malloc

Ce programme va produire le résultat suivant :

realloc

Voila ! C’est la fin de ce cours 😉
N’hésitez pas à me faire part de vos remarques, suggestions et critiques !
[yop_poll id= »2″]
[yop_poll id= »3″]

6 Comments

  1. ss12
    mars 1, 2015 @ 10:19

    Bonjour,
    le realloc sert à diminuer et augmenter le taille du tableau .
    voici un programme :
    void afficher(int *T , int N){
    /* Affichage des composantes du tableau */
    while(N)
    {
    printf(« %d « , *T);
    T++;
    N–;
    }
    printf(« \n »);

    }
    main()
    {
    int *T ;
    int i , dim = 5 ;
    T = malloc(dim * sizeof(int));

    for(i=0; i<dim ; i++)
    {
    scanf("%d",&T[i]);

    }
    afficher(T, dim);
    int *ptr_realloc ;
    // la dimension maintenant 3
    ptr_realloc = realloc(T, 3*sizeof(int));
    // j'appel la fonction affichage une autre fois , le probleme il va afficher le même tableau, au lieu qu'il affiche des valeurs erronées dans la case 3 et 4
    afficher(ptr_realloc , 5);
    }

  2. François Delbot
    mars 1, 2015 @ 2:44

    Bonjour,

    Il y a plusieurs raisons. La première, c’est qu’après avoir changé la taille de votre tableau, en la faisant passer de 5 à 3, vous demandez tout de même à afficher 5 cases.

    On pourrait s’attendre à ce que les deux dernières valeurs soient incohérentes, vu qu’elles ne font plus partie du tableau.

    Mais, les fonctions d’allocation dynamique utilisent des algorithmes qui favorisent la vitesse d’allocation/reallocation. C’est pour cette raison que ces fonctions allouent souvent un peu plus de mémoire que nécessaire.

    Ainsi, lorsqu’on demande de réallouer avec une taille de 3, la fonction va allouer un peu plus, et recopier un peu plus que demandé (de l’ancien vers le nouveau tableau).

    Le phénomène que vous souhaitez vérifier avec ce code risque d’apparaitre avec des tailles plus importantes. Par exemple dim=100 puis une reallocation de taille 50. La vous devriez voir des valeurs incohérentes, puisque non initialisées.

    Amicalement,
    fr

  3. ss12
    mars 2, 2015 @ 1:10

    merci j’ai testé avec 100 puis avec 50 j’ai un résultat un peu incohérent j’ai rempli mon tableau avec des 1. jusqu’à 53 case il affiche 1 après seulement trois valeurs erronées et après il affiche 1. alors le realloc il ne fonctionne pas bien. Amicalement

  4. François Delbot
    mars 2, 2015 @ 1:21

    Hello !

    Attention ! Le realloc va utiliser de la mémoire à l’endroit le plus simple pour lui. Si on ne fait que diminuer la taille du tableau, cela ne va pas effacer le contenu des « anciennes » cases…
    Qu’appelles tu un résultat incohérent ?

    fr

  5. ss12
    mars 3, 2015 @ 11:31

    merci j’ai compris , résultats comme exemple 567869, -17860689. mais quand même je trouve que ce n’est pas normal qui ne supprime pas , parce que dans les livres ils disent tronque
    j’ai une autre question
    main()
    {
    int mat[12][13] = {{1,2}, {1,2}}
    afficher_matrice(mat);
    }
    en fait il n’aime pas que je donne en paramétre un matrice et pas un pointeur
    void afficher(int ** mat , int dim ) {}

    merci beaucoup

    • François Delbot
      mars 7, 2015 @ 9:54

      Alors, un tableau n’a pas le même type qu’un pointeur. C’était vrai dans les anciennes versions du langage (K&R par exemple), mais plus en C ANSI. Donc, si on déclare un tableau : int tab[10]; et qu’on souhaite le passer en argument à une fonction nommée test (par exemple et qui retourne un entier), il faut appeler test(tab); et le prototype de la fonction doit être : int test(int tab[10]);

      On pourra en rediscuter lorsque vous serez à l’aise avec l’allocation dynamique, car en calculant la mémoire utilisée par un tableau à deux dimensions, et la mémoire allouée dynamiquement pour enregistrer la même quantité de données, on se rends compte que l’allocation dynamique va utiliser un peu plus de mémoire…

Leave a Reply