Les tableaux dynamiques

Eric Sigoillot

Comment créer un tableau dynamique ?

Comment utiliser un tableau dynamique ?

Commentez

- Titre : Les tableaux dynamiques

- Auteur : Eric Sigoillot

- Parution : 16 avril 2004

- Licence : Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright ® 2004 Eric Sigoillot. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- Avant-Propos

- 1. Qu'est-ce qu'un tableau dynamique ?

- 1-1. Les tableaux

- 1-2. Tableaux statiques et tableaux dynamiques

- 1-2-1. La gestion statique : avantages et inconvénients

- 1-2-2. La solution : une gestion dynamique

- 2. Déclarer et utiliser un tableau dynamique

- 2-1. La gestion native

- 2-1-1. Déclaration

- 2-1-2. Allocation et désallocation

- 2-1-3. Redimensionner un tableau dynamique

- 2-1-4. Manipuler un tableau dynamique

- 2-1-4-1. Copie

- 2-1-4-2. Paramètres tableaux ouverts

- 2-2. La gestion manuelle

- 2-2-1. Déclaration

- 2-2-2. Allocation et désallocation

- 2-2-3. Redimensionnement

- 2-2-4. Manipulation

- 2-2-5. Vers une implémentation plus générale

- 2-2-5-1. Analyse du problème

- 2-2-5-2. Implémentation du tableau

- 2-2-5-3. Exemple d'utilisation

- 2-2-5-4. Téléchargement

- 3. Tableaux semi-dynamiques

- Conclusion

Avant-Propos

Dans cet article vous apprendrez à gérer les tableaux dynamiques (dits aussi tableaux ouverts) en Pascal, indépendamment du compilateur utilisé.

Qu'il faille les créer de toute pièce ou bien simplement savoir s'en servir, vous saurez à la fin de ce tutoriel comment manipuler les tableaux dynamiques.

1 - Qu'est-ce qu'un tableau dynamique ?

1-1 - Les tableaux

Avant de parler de tableau dynamique, peut-être serait-il plus prudent de commencer par parler des tableaux en général. Alors, qu'est-ce qu'un tableau ?

Pour faire simple, disons qu'un tableau - au sens informatique du terme - est une structure de donnée. Cette structure permet d'organiser de façon pratique des données possédant un type unique prédéfini. On peut ainsi déclarer des tableaux d'entiers, de réels, ou encore d'enregistrements, mais aussi des tableaux de tableaux...
Dans ce dernier cas, on parlera plutôt de tableaux à plusieurs dimensions. Le tableau le plus simple qu'il soit possible de créer ne possède qu'une seule dimension, et il est possible de créer des tableaux possédant un nombre quelconque de dimensions, dans la limite de la mémoire disponible (même s'il est difficile de trouver un intérêt à posséder un tableau à 50 dimensions !).
De fait, les tableaux qu'on utilise possèdent la plupart du temps une, deux ou trois voire quatre dimensions, très rarement plus. Pour les deux premiers, on utilisera souvent les termes de ligne et de colonne pour désigner un emplacement dans le tableau.

En Pascal, les tableaux se déclarent au moyen du mot réservé array, suivi entre crochets de sa taille (borne inférieure et borne supérieure), puis de of et du type de donnée dont le tableau sera constitué.

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

Chaque dimension additionnelle sera ajoutée à la précédente soit en la séparant d'une virgule, soit en ayant recours à array comme type de donnée.
L'exemple suivant illustre ces différentes possibilités :

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

{ ou }

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

On accèdera ensuite à chaque cellule du tableau en mentionnant son adresse entre crochets. Si le tableau possède plusieurs dimensions, alors les positions successives seront ajoutées en se suivant, séparées des précédentes par une virgule, ou bien en ajoutant une paire de crochets supplémentaire :

begin
...
T[5] := 1;

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

1-2 - Tableaux statiques et tableaux dynamiques

Si les tableaux resteront toujours des tableaux, deux manières de les gérer se distinguent : la gestion dite statique et la gestion dite dynamique. La première - qui s'avère être la plus simple à mettre en oeuvre - se contente de déclarer un tableau comme n'importe quelle autre variable. La seconde, elle, passe par une gestion dynamique, donc s'appuyant sur le caractère volatile de la mémoire.

1-2-1 - La gestion statique : avantages et inconvénients

Le premier avantage de la gestion statique est sans doute sa simplicité de mise en oeuvre. 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 exclus de retailler un tableau statique en cours d'exécution. Par conséquent, le programmeur est obligé de prévoir par avance 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.

1-2-2 - La solution : une gestion dynamique

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.

2 - Déclarer et utiliser un tableau dynamique

Les tableaux dynamiques ont vu leur importance croître ces dernières années avec les quantités de plus en plus importantes de données à manipuler. De manière logique, les tableaux dynamiques ont donc eu tendance à être gérés nativement par les nouveaux compilateurs. Ce n'est toutefois pas le cas de tous, et il est parfois nécessaire de les implémenter manuellement.

2-1 - La gestion native

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.

2-1-1 - Déclaration

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.

2-1-2 - Allocation et désallocation

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;

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.

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;

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.

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

2-1-3 - Redimensionner un tableau dynamique

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;

2-1-4 - Manipuler un tableau dynamique

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

2-1-4-1 - Copie

Pour copier un tableau dynamique, il ne faut pas utiliser l'assignation directe :=. En effet, les tableaux dynamiques sont considérés comme des pointeurs. Ainsi, si A et B sont déclarés comme tableaux dynamiques, en utilisant l'affectation B := A, B désignera le même tableau que A. Autrement dit, si vous modifiez une valeur dans le tableau A, cette valeur sera aussi modifiée dans le tableau B.

Afin d'éviter ce désagrément, plusieurs solutions sont possibles. Vous pouvez vous servir de la procédure Move.

var
A, B: array of Integer;

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

On lui préfèrera peut-être la procédure Copy, qui gère plus naturellement les tableaux dynamiques :

var
A, B: array of Integer;

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

2-1-4-2 - Paramètres tableaux ouverts

Certaines procédures et fonctions acceptent comme paramètre des tableaux ouverts :

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

Ces paramètres ne sont pas des tableaux dynamiques. Ils se comportent toutefois de la même manière. On peut ainsi passer en paramètre un simple tableau statique. Par contre, à l'intérieur de la procédure, le tableau sera toujours indicé à partir de 0, quelle que soit sa borne inférieure en dehors de celle-ci.

On peut avec ces paramètres se servir de la fonction Low qui renverra la borne inférieure du tableau (0 normalement) et de la fonction High qui renverra la borne supérieure du tableau.
Ainsi, pour parcourir tout le tableau, on pourra écrire :

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

Certaines fois, il est nécessaire de ne passer qu'une partie d'un tableau en tant que paramètre à une telle procédure. On se servira alors de la fonction Slice :

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;

2-2 - La gestion manuelle

Si certains compilateurs gèrent nativement les tableaux dynamiques, ce n'est pas le cas de tous. Malheureusement, il est souvent nécessaire de créer soit même ses propres outils pour gérer les tableaux dynamiques. Bien entendu, si tout ce qui va être décrit n'utilise que des méthodes que l'on peut qualifier de "légales" au niveau de la programmation, certaines méthodes relèvent toutefois de l'astuce, toujours pratique...

2-2-1 - Déclaration

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 sensé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-}.

2-2-2 - Allocation et désallocation

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

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é.

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

2-2-3 - Redimensionnement

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

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 .

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;

2-2-4 - Manipulation

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

2-2-5 - Vers une implémentation plus générale

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 quoiqu'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.

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.

2-2-5-1 - Analyse du problème

Avant de se lancer dans une implémentation objet, il faut auparavant cerner le problème et rendre compte des différents éléments à prendre en considération.

- 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

Afin de pouvoir créer un tableau de type triangulaire, on choisit de créer un tableau à dimension unique, mais pouvant contenir comme type d'élément un autre tableau dynamique unidimensionnel.

2-2-5-2 - Implémentation du tableau

Pour des raisons de stabilité, on choisit ici de dériver notre objet d'un ancêtre. Ce sera TObject, présent dans l'unité Objects ou System en fonction du compilateur utilisé.

Nous allons ici faire une implémentation sous Turbo Pascal. Ce code ne nécessitera que des modifications mineures pour être exploitable confortablement avec un autre compilateur.

Déclarons donc notre tableau dynamique, que nous appellerons TDynamicArray :

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.

C'est la procédure SetLength qui va jouer un rôle central dans l'allocation et la désallocation de la mémoire du tableau. Le constructeur et le destructeur ne sont là que pour des raisons d'héritage principalement.

Le fait de déclarer la fonction At permet à la fois d'obtenir la valeur d'une cellule et de la modifier. En utilisant un type Pointer, cela oblige à utiliser un transtypage. Néanmoins, on gagne singulièrement en flexibilité.

Passons de suite à l'implémentation des méthodes...

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;

Il est possible d'ajouter d'autres méthodes. Par exemple, on pourrait en ajouter une qui se chargerait d'effacer le contenu du tableau. Ce n'est pas notre but ici, et nous laissons cela à votre charge.

Remarque :

- 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.

2-2-5-3 - Exemple d'utilisation

Les deux exemples qui suivent utilisent l'objet déclaré précédemment. Le premier déclare un tableau unidimensionnel, et le second un tableau bidimensionnel triangulaire, tous deux constitués d'entiers.

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.

L'exemple suivant déclare un tableau à 2 dimensions, triangulaire. Le transtypage peut rendre l'utilisation un peu lourde, du fait de l'utilisation du nom TDynamicArray. On pourra donc au besoin simplifier ce nom en TDArray par exemple.

Attention ! Cet exemple n'est sûrement pas à la portée du premier venu. Il nécessite une bonne connaissance des pointeurs pour ne pas se fourvoyer dans les déréférencements par exemple. Si vous ne le comprenez pas du premier coup, c'est normal. Il est inutile de paniquer, une compréhension parfaite de cet exemple va de paire avec une compréhension parfaite des pointeurs.

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.

2-2-5-4 - Téléchargement

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

3 - Tableaux semi-dynamiques

Lorsque la gestion des tableaux dynamiques n'est pas gérée nativement par le compilateur, on peut parfois recourir aux tableaux que nous qualifierons de semi-dynamiques. Ces tableaux sont en fait statiques, car ils possèdent un nombre maximal d'éléments. Par contre, la mémoire nécessaire au stockage des données n'est allouée qu'en cas de besoin.

Au lieu de déclarer un pointeur vers un tableau, on se contente ainsi de créer un tableau de pointeurs.

Ce type de tableau n'est rentable que pour des tableaux d'enregistrements de taille supérieure à 4 octets, sans quoi ils ne feraient que faire perdre de la mémoire.

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

En fonction du besoin, on alloue avec New les cellules du tableau dont il est fait usage. Une fois leur utilisation terminée, on libère la mémoire avec Dispose.

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.

Leur gestion ne nécessite pas de connaissances particulières. La seule difficulté réside peut-être dans la copie de tels tableaux. Il faut en effet copier les éléments un à un.

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.

Conclusion

Vous avez appris ici à manipuler les tableaux dynamiques, qu'ils soient ou non inclus à la base dans votre compilateur.

Vous êtes à présent en mesure d'en faire bon usage. N'oubliez jamais qu'un tableau dynamique ne doit être utilisé que s'il s'avère nécessaire, car il consomme de la mémoire et s'avère être d'une gestion aussi bien plus complexe que plus lente qu'un simple tableau statique.

Bonne programmation !