Les tableaux dynamiques

16/04/2004

Par Hdd34 (Les outils du programmeur)
 

Comment créer un tableau dynamique ?
Comment utiliser un tableau dynamique ?

var
  T: array[1..10] of Integer;

var
  U: array[1..10, 1..10] of Integer;
  
{ ou }
  
var
  U: array[1..10] of array[1..10] of Integer;

begin
  ...
  T[5] := 1;
  
  U[1, 2] := 1;  { ou }  U[1][2] := 1;
  ...
end.

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.

L'exemple type du compilateur gérant nativement les tableaux dynamiques est certainement Delphi de Borland, depuis sa version 3. Nous nous servirons donc celui-ci pour illustrer notre propos.

var
  A: array of Integer;

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

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

Il est possible que d'autres compilateurs utilisent une instruction différente. Si cette procédure n'est pas présente sur votre compilateur alors que celui-ci gère les tableaux dynamiques nativement, regardez si la syntaxe de New n'a pas été étendue. Vous pouvez aussi rechercher du côté de GetMem. Quoiqu'il en soit, parcourez l'aide de votre compilateur concernant le mot réservé array.

var
  B: array of array of Integer;

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

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;

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

• 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;

Il convient de toujours désallouer un tableau dynamique qui a été alloué précédemment. En effet, même si Delphi le fait seul grâce à une gestion évoluée des tableaux dynamiques, ce n'est pas forcément le cas de tous les compilateurs gérant nativement les tableaux dynamiques.

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 plus de sécurité, il est préférable d'inclure les allocations de tableaux dynamiques entre blocs try...except ou try...finally.

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

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;

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;

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

PDynArray = ^TDynArray;

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

On n'utilisera jamais New. En effet, New calcule seule la taille de la zone mémoire à allouer. Or, notre tableau possède une taille redéfinissable. Ce n'est donc pas un outil approprié.

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

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

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

Utilisateurs de Turbo Pascal attention ! Le gestionnaire de mémoire de Turbo Pascal ne permet pas de redimensionner une zone mémoire. Pour pouvoir retailler un tableau dynamique, il faut donc allouer un nouveau tableau, recopier le contenu de l'ancien dans le nouveau pour finalement libérer la mémoire allouée à l'ancien tableau dynamique. Cette méthode est assez lourde à gérer, et surtout pénalisante au niveau mémoire, car elle peut réclamer plus de deux fois la mémoire nécessaire au tableau. On pourra alors pour passer outre cette limitation, soit reprogrammer un gestionnaire de mémoire propriétaire, soit utiliser des tableaux semi-dynamiques.

• 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;

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;

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.

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

Ceux qui ne connaissent pas la Programmation Orientée Objet doivent au préalable se documenter sur le sujet. On pourra notamment se reporter au cours de Cyberzoïde.

• Les champs
  
  Notre objet doit conserver en mémoire différents éléments :
  
  - La taille du tableau
  - La taille de chaque cellule
  - Le contenu des cellules
  
  
• Les méthodes
  
  Notre objet doit être en mesure :
  
  - D'allouer une zone mémoire
  - De désallouer une zone mémoire
  - De retailler une zone mémoire
  - De renvoyer la taille du tableau
  - De récupérer et modifier une cellule
  

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;

On peut remarquer que le type de donnée est un pointeur. Ce type de donnée permet de s'affranchir d'un type de donnée fixe. Notre tableau peut donc contenir n'importe quel type de variable.

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;

• Le tableau dynamique implémenté ici ne permet d'accéder qu'au plus à 64 Ko de mémoire, comme un simple tableau statique. Bien entendu, il est tout à fait possible de créer un objet en mesure d'accéder à plus de mémoire, la seule nécessité étant de maintenir une table de pointeurs liés à des zones mémoires contiguës.
  Dans un soucis de simplicité, cette implémentation ne sera pas menée ici.

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);
  
  { A 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.

L'objet TDynamicArray a été inclus dans l'unité DynArray celle-ci peut être téléchargée ici :

Télécharger l'unité

Les deux exemples sont téléchargeables ici :

Télécharger l'exemple 1
Télécharger l'exemple 2

{ Une structure quelconque }
type
  PStruct = ^TStruct;
  TStruct = record
    A, B, C, D, E, F: Longint;
  end;
  
{ Déclare un tableau d'au maximum 100 éléments TStruct }
type
  TSemiDynArr = array[0..99] of PStruct;

var
  A: TSemiDynArr;
  i: Integer;

begin
  for i := 0 to 9 do
    New(A[i]);
  ...
  for i := 0 to 9 do
    Dispose(A[i]);
end.

var
  A, B: TSemiDynArr;
  i: Integer;

begin
  for i := 0 to 9 do New(A[i]);
  for i := 0 to 9 do New(B[i]);
  
  for i := 0 to 9 do B[i]^ := A[i]^;
  
  for i := 0 to 9 do Dispose(A[i]);
  for i := 0 to 9 do Dispose(B[i]);
end.