Les tableaux dynamiques

Le premier avantage de la gestion statique est sans doute sa simplicité de mise en œuvre. Aucune précaution n'est à prendre, un tableau statique se manipule comme on manipulerait un ensemble de variables séparées. De fait, aucune connaissance particulière n'est requise, et un novice apprend très vite à apprivoiser une structure si pratique.

Autre avantage peut-être : la possibilité de recopier rapidement le contenu d'un tableau statique dans un autre en une unique instruction, pour peu que les deux tableaux soient déclarés de la même manière…

type
  TIntArray = array[1..10] of Integer;
  
var
  A, B: TIntArray;
  
begin
  ...
  B := A;  { Le contenu de B est le même que celui de A }
  ...
end.

Malheureusement, les tableaux statiques possèdent également un inconvénient majeur : ils sont statiques ! En d'autres termes, ceci signifie que leur taille est fixée lors de la compilation. Il est totalement exclu de retailler un tableau statique en cours d'exécution. Par conséquent, le programmeur est obligé de prévoir quelle sera la taille maximale du tableau dont il aura besoin. Si pour les cas les plus courants, cette limitation ne pose pas de problème gênant, elle se révèle très vite handicapante pour nombre d'applications.

Le seul moyen de passer outre cette limitation intrinsèque du tableau statique était de le rendre dynamique. Autrement dit, il était nécessaire d'allouer la mémoire réservée au tableau lors de l'exécution, quitte à retailler cette zone mémoire en fonction des besoins de l'application.

Les tableaux dynamiques ne sont donc en réalité que des pointeurs vers des tableaux statiques. Encore une fois, c'est la gestion par pointeurs qui nous aide. Encore faut-il savoir s'en servir…

Bien entendu, l'utilisation de la mémoire dynamique ne facilite pas la gestion générale de tels tableaux. Les règles inhérentes aux pointeurs doivent ainsi s'appliquer. Il est donc nécessaire de penser à allouer, puis désallouer le tableau en fin d'utilisation. De plus, la copie est plus complexe et passe par des instructions particulières. Nous allons les découvrir plus tard.

Un tableau dynamique se déclare de la même manière qu'un tableau statique à un détail près : la taille du tableau n'est plus requise. De fait, il est impossible de définir la borne inférieure du tableau. Par conséquent, tous les tableaux dynamiques seront nécessairement indicés à partir de 0.

var
  A: array of Integer;

De fait, si l'on souhaite déclarer un tableau dynamique à plusieurs dimensions, il ne reste plus qu'une seule des deux méthodes citées précédemment pour les tableaux statiques : on doit se servir de array.

{ Déclaration d'un tableau dynamique à 2 dimensions }
var
  B: array of array of Integer;

Si jusqu'ici, tout semble extrêmement simple, l'allocation peut s'avérer plus ardue.

Comme un tableau dynamique ne possède pas de taille prédéfinie, il convient de l'allouer (dynamiquement s'entend) avant de pouvoir s'en servir. Si vous utilisez Delphi, alors vous devrez avoir recours à la procédure SetLength(var T; Len: Integer).

Pour allouer un tableau unidimensionnel de 10 éléments, on écrira donc :

var
  A: array of Integer;
 
begin
  ...
  SetLength(A, 10);
  ...
end;

La situation se complique lorsque le tableau possède plus d'une dimension. En fait, deux cas de figure se présentent. Pour les cas que nous qualifierons de « classiques », il suffit d'ajouter la taille de chaque dimension à la suite de la première dans SetLength, comme ceci :

var
  B: array of array of Integer;

begin
  ...
  SetLength(B, 10, 10);
  ...
end;

Là où les tableaux dynamiques multidimensionnels se distinguent singulièrement de leurs cousins statiques, c'est pour le cas des tableaux dynamiques multidimensionnels non rectangulaires. Autrement dit, chaque ligne peut ne pas avoir le même nombre de colonnes et vice-versa. Il est ainsi possible de créer un tableau de forme triangulaire si le besoin s'en fait sentir. Pour ce faire, il suffit de faire appel à SetLength pour chaque ligne.
L'exemple suivant alloue un tableau triangulaire de 10x10 :

var
  T: array of array of Integer;
  i: Integer;
  
begin
  ...
  SetLength(T, 10);  { On alloue 10 lignes, de taille non définie }
  
  { Chaque ligne possède une taille allant de 1 à 10 }
  for i := 0 to 9 do
    SetLength(T[i], i + 1);
    
  { On a donc un tableau qui ressemble à ça : }
  
  { *                                         }
  { **                                        }
  { ***                                       }
  { ****                                      }
  
  { Etc...                                    }
  
  ...
end;

Si vous le souhaitez, vous pouvez initialiser votre tableau dynamique à zéro une fois alloué. Il suffit d'appeler la procédure Initialize, même si celle-ci n'est que rarement utilisée.

var
  A: array of Integer;
begin
  ...
  SetLength(A, 10);
  Initialize(A, 10);
  ...
end;

Comme vous pouviez vous y attendre, un tableau dynamique, s'il a besoin d'être alloué, a bien entendu aussi besoin d'être désalloué. Pour cela, vous avez deux solutions à votre disposition :

• soit vous appelez SetLength avec une taille nulle
• soit vous appelez Finalize

var
  A: array of Integer;
  
begin
  ...
  SetLength(A, 10);
  ...
  SetLength(A, 0);   { ou }   Finalize(A);
  ...
end;

Pour connaître la taille d'un tableau précédemment alloué, vous pouvez faire appel à la fonction Length, ainsi qu'aux fonctions Low et High qui renverront respectivement les bornes inférieures et supérieures de votre tableau.

var
  A: array of Integer;
  i: Integer;
  
begin
  ...
  SetLength(A, 10);
  
  for i := 0 to Length(A) - 1 do
    A[i] := i;
    
  SetLength(A, 0);
  ...
end;

Pour redimensionner un tableau, il n'est pas nécessaire de libérer au préalable la mémoire qui ne serait plus utilisée. Il suffit d'appeler SetLength avec la nouvelle taille désirée. Si plus de mémoire est nécessaire, celle-ci est allouée dans la mesure du possible. Si de la mémoire doit être libérée, alors elle l'est automatiquement.

var
  A: array of Integer;
  
begin
  ...
  SetLength(A, 10);
  ...
  SetLength(A, 20);
  ...
  SetLength(A, 15);
  ...
  SetLength(A, 0);
  ...
end;

Les tableaux dynamiques sont en général fournis avec un certain nombre de procédures et fonctions permettant de les manipuler.

II-A-4-a. Copie▲

var
  A, B: array of Integer;

begin
  SetLength(A, 10);
  SetLength(B, 10);
  ...
  Move(Pointer(A)^, Pointer(B)^, SizeOf(A[0]) * Length(A);
  ...
end;

var
  A, B: array of Integer;

begin
  SetLength(A, 10);
  ...
  B := Copy(A, 0, Length(A) - 1);
  ...
end;

II-A-4-b. Paramètres tableaux ouverts▲

procedure Test(A: array of Integer);
begin
  ...
end;

procedure Test(A: array of Integer);
var
  i: Integer;
begin
  ...
  for i := Low(A) to High(A) do ...
  ...
end;

procedure Test(A: array of Integer);
begin
  ...
end;


var
  A: array of Integer;

begin
  SetLength(A, 20);
  ...
  Test(Slice(A, 5, 10));  { On ne transmet que les éléments 5 à 10 du tableau }
  ...
end;

Un tableau dynamique possède avant tout une structure de tableau. Notre type « tableau dynamique » doit donc être déclaré comme tableau. Par contre, sa taille n'est pas censée être connue à l'avance. On va donc se contenter de déclarer le plus petit tableau qu'il soit possible de déclarer. De plus, il est d'usage d'indicer les tableaux dynamiques à partir de 0. Si ce n'est pas du tout une obligation, nous allons ici suivre cette règle d'usage.

Déclarons donc un type tableau d'une taille de un élément par dimension. Dans les exemples qui suivront, nous utiliserons un tableau à deux dimensions.

type
  TDynArrayCell = Integer;
  TDynArray = array[0..0, 0..0] of TDynArrayCell;

Tel quel, notre tableau est toujours un tableau statique. Pour qu'il devienne dynamique, il convient de faire appel à la mémoire dynamique, et donc aux pointeurs. Nous allons donc déclarer un pointeur vers notre type de tableau :

  PDynArray = ^TDynArray;

Notre tableau est à présent déclaré comme il faut. Un dernier détail reste néanmoins à prendre en compte. Si nous l'utilisons tel quel, en laissant actives les protections inhérentes au compilateur, nous allons nous heurter à une erreur de domaine. En effet, il suffirait d'accéder à la ligne 2 pour provoquer une erreur, et ce, même si la mémoire est bien allouée comme il faut.

Pour éviter une telle erreur, nous allons donc désactiver la détection d'erreur de domaine, en utilisant la directive de compilation {$R-}.

Une fois notre tableau déclaré, il faut l'allouer avant de pouvoir l'utiliser. Pour cela, nous allons nous servir du gestionnaire de mémoire qu'offre le compilateur. La plupart du temps, il s'agit de la procédure GetMem. En mode protégé, on pourra se servir de GlobalAlloc.

• Turbo Pascal : GetMem
• TMT Pascal : GetMem ou AllocDosMemoryBlock
• DPMI : GlobalAllocPtr
• Windows : GlobalAlloc et GlobalLock

Toutes les procédures d'allocation réclament en paramètre la taille en octets de la zone mémoire à allouer. Cette taille correspond donc au nombre de cellules de notre tableau, multiplié par la taille en octets de chaque cellule.

Tel que notre tableau est déclaré, celui-ci est nécessairement rectangulaire. Nous verrons plus loin comment déclarer un tableau triangulaire.

La procédure suivante alloue un tableau dynamique en mémoire :

procedure AllocDynArray(var T: PDynArray; Size: Word);
begin
  GetMem(T, Size * SizeOf(TDynArrayCell));
end;

Cette procédure est incomplète. Nous allons l'améliorer par la suite. Size attend la taille générale du tableau. Autrement dit, si votre tableau doit comporter 4 lignes de 3 colonnes, alors Size devra prendre la valeur 4 * 3.



Une fois que notre tableau n'a plus d'utilité, il faut le désallouer. Pour cela, on utilisera la procédure associée à la procédure d'allocation utilisée précédemment, à savoir :

• Turbo Pascal : FreeMem
• TMT Pascal : FreeMem ou FreeDosMemoryBlock
• DPMI : GlobalFreePtr
• Windows : GlobalFree et GlobalUnlock

Créons donc une procédure dédiée à la désallocation du tableau.

procedure FreeDynArray(var T: PDynArray; Size: Word);
begin
  if Assigned(T) then
    FreeMem(T, Size * SizeOf(TDynArrayCell));
end;

En tant que tableau dynamique, celui-ci doit pouvoir être redimensionné.

Les autres compilateurs ne sont pas dotés en principe d'une telle limitation. On se servira donc des procédures suivantes :

• TMT Pascal : ResizeDosMemoryBlock
• DPMI : GlobalReallocPtr
• Windows : GlobalReAlloc

procedure ResizeDynArray(var T: PDynArray; Size: Word);
begin
  if Assigned(T) then
    ResizeMem(T, Size * SizeOf(TDynArrayCell))
  else
    AllocDynArray(T, Size);
end;

Ou bien alors :

procedure ReallocDynArray(var T: PDynArray; OldSize, NewSize: Word);
var
  P: PDynArray;
begin
  if Assigned(T) then
  begin
    { Allocation du nouveau tableau }
    GetMem(P, NewSize * SizeOf(TDynArrayCell));
    
    { Copie des éléments précédents }
    if OldSize < NewSize then
      Move(T^, P^, OldSize * SizeOf(TDynArrayCell))
    else
      Move(T^, P^, NewSize * SizeOf(TDynArrayCell));
    
    { Libération de l'ancien tableau }
    FreeMem(T, OldSize * SizeOf(TDynArrayCell));
    T := P;
  end
  else
    AllocDynArray(T, NewSize);
end;

Sans avoir à utiliser nécessairement les procédures déclarées plus haut, on peut simplement utiliser un petit tableau dynamique de la manière suivante :

type
  PDArray = ^TDArray;
  TDArray = array[0..0] of Integer;
  
var
  D: PDArray;
  i: Integer;
  
begin
  { On alloue un tableau de 10 éléments }
  GetMem(D, 10 * SizeOf(Integer));
  
  { On le remplit }
  for i := 0 to 9 do D^[i] := i;
  
  { On l'affiche }
  for i := 0 to 9 do WriteLn(D^[i]);  
  ReadLn;
  
  { Et on le libère }
  FreeMem(D, 10 * SizeOf(Integer));
end.

Je vous invite à utiliser les procédures énoncées plus haut pour le redimensionnement d'un tel tableau.

var
  D: PDynArray;
  i: Integer;
  
begin
  { On alloue un tableau de 10 éléments }
  AllocDynArray(D, 10);
  
  { On le remplit }
  for i := 0 to 9 do D^[i] := i;
  
  { On l'affiche }
  for i := 0 to 9 do WriteLn(D^[i]);  
  ReadLn;
  
  { On le retaille à 5 éléments }
  ReallocDynArray(D, 10, 5);

  { On l'affiche }
  for i := 0 to 4 do WriteLn(D^[i]);  
  ReadLn;

  { Et on le libère }
  FreeDynArray(D, 5);
end.

Télécharger l'exemple complet

L'implémentation que l'on a pu voir jusqu'ici peut parfois devenir lourde à gérer. Si à présent la plupart des gestionnaires de mémoire n'ont pas besoin de connaître la taille de la zone mémoire allouée pour la libérer, ce n'est pas le cas de tous. De plus, on peut avoir besoin de connaître la taille de notre tableau, qui doit être sauvée.

Si un programme simple peut se contenter d'une telle gestion, on peut quoi qu'il en soit tenter de créer une interface de gestion plus simple à manipuler.

La méthode de gestion qui doit venir immédiatement à l'esprit est la gestion par objet. Un tableau dynamique est une entité qui doit savoir se gérer par elle-même. Une implémentation en programmation objet semble donc toute naturelle.

II-B-5-a. Analyse du problème▲

II-B-5-b. Implémentation du tableau▲

uses
  Objects;

{$R-}  { Désactivation de la détection de domaine }

type
  PDynamicArray = ^TDynamicArray;
  TDynamicArray = object(TObject)
  private
    FSize: Word;
    FCellSize: Word;
    FValues: Pointer;
  public
    function At(APos: Word): Pointer;
    function SetLength(ASize: Word): Boolean;
    function Length: Word;
    constructor Init(ACellSize: Word);
    destructor Done; virtual;
  end;

function TDynamicArray.At(APos: Word): Pointer;
begin
  At := nil;
  { Vérification des bornes }
  if APos >= FSize then Exit; 
  { Renvoie un pointeur vers la valeur }
  At := Ptr(Seg(FValues^), Ofs(FValues^) + APos * FCellSize); 
end;



function TDynamicArray.SetLength(ASize: Word): Boolean;
var
  P: Pointer;
begin
  SetLength := False;
  if ASize = 0 then                            { Suppression du tableau }
  begin
    if Assigned(FValues) then                  { Si le tableau est alloué... }
    begin
      FreeMem(FValues, FSize * FCellSize);     { On le libère }
      FSize := 0;                              { Modification des paramètres }
      FValues := nil;
      
      SetLength := True;
    end;
  end
  else                                         { Redimensionnement }
  begin
    GetMem(P, ASize * FCellSize);              { Allocation du nouveau tableau }
    if not Assigned(P) then Exit;
    
    if FSize <> 0 then                         { S'il y a déjà eu allocation... }
    begin
      if ASize < FSize then
        Move(FValues^, P^, ASize * FCellSize)  { Copie des éléments précédents }
      else
        Move(FValues^, P^, FSize * FCellSize);
      
      FreeMem(FValues, FSize * FCellSize);     { Libération de l'ancien tableau }
    end;
    
    FSize := ASize;                            { Modification des paramètres }
    FValues := P;
    
    SetLength := True;
  end;
end;



function TDynamicArray.Length: Word;
begin
  Length := FSize;
end;



constructor TDynamicArray.Init(ACellSize: Word);
begin
  if not inherited Init then Fail;   { Appel de l'ancêtre }
  if ACellSize < 1 then              { Sauvegarde des paramètres }
    Fail
  else
    FCellSize := ACellSize;
end;



destructor TDynamicArray.Done;
begin
  if Assigned(FValues) then    { On libère le tableau s'il est encore alloué }
    SetLength(0);
  inherited Done;              { Appel de l'ancêtre }
end;

II-B-5-c. Exemple d'utilisation▲

var
  D: PDynamicArray;
  i: Integer;
  
begin
  { Allocation d'un tableau de 10 entiers }
  New(D, Init(SizeOf(Integer)));
  D^.SetLength(10);
  
  { La boucle qui suit remplit le tableau avec des entiers de 0 à 9. }
  { On peut remarquer l'utilisation du transtypage }
  for i := 0 to D^.Length - 1 do
    Integer(D^.At(i)^) := i;
    
  { On affichage le contenu du tableau }
  for i := 0 to D^.Length - 1 do
    WriteLn('Position ', i, ' :  ', Integer(D^.At(i)^));
    
  ReadLn;
    
  { On réduit le tableau à 5 éléments }
  D^.SetLength(5);
  
  { On affichage le contenu du tableau }
  for i := 0 to D^.Length - 1 do
    WriteLn('Position ', i, ' :  ', Integer(D^.At(i)^));
    
  ReadLn;
    
  { On libère le tableau }
  D^.SetLength(0);
  D^.Free;
end.

var
  D: PDynamicArray;
  i, j: Integer;
  
begin
  { Le tableau possèdera 10 lignes }
  D := New(PDynamicArray, Init(SizeOf(PDynamicArray)));
  D^.SetLength(10);
  
  { À chaque ligne est associé un tableau (les colonnes) } 
  { La i-ème ligne possèdera (i+1) colonnes }
  for i := 0 to D^.Length - 1 do
  begin
    PDynamicArray(D^.At(i)^) := New(PDynamicArray, Init(SizeOf(Integer)));
    PDynamicArray(D^.At(i)^)^.SetLength(i + 1);
  end;
  
  { On remplit le triangle avec les valeurs (ligne + 1) * (colonne + 1) }
  for i := 0 to D^.Length - 1 do
    for j := 0 to PDynamicArray(D^.At(i)^)^.Length - 1 do
      Integer(PDynamicArray(D^.At(i)^)^.At(j)^) := (i + 1) * (j + 1);
  
  { On affiche le contenu du tableau }
  for i := 0 to D^.Length - 1 do
  begin
    for j := 0 to PDynamicArray(D^.At(i)^)^.Length - 1 do
      Write(Integer(PDynamicArray(D^.At(i)^)^.At(j)^):4);
    WriteLn;
  end;
  
  ReadLn;
  
  { On commence par libérer la mémoire occupée par les colonnes }
  for i := 0 to D^.Length - 1 do
  begin
    PDynamicArray(D^.At(i)^)^.SetLength(0);
    PDynamicArray(D^.At(i)^)^.Free;
  end;
  
  { Enfin, on libère la mémoire des lignes }
  D^.SetLength(0);
  D^.Free;
end.

II-B-5-d. Téléchargement▲