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