Delphi Container Library : les listes

Jean-Philippe BEMPEL

- Titre : Delphi Container Library : les listes

- Auteur : Jean-Philippe BEMPEL

- Parution : 2 avril 2002

- Mise à jour : 23 décembre 2019

- 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 ® 2002 Jean-Philippe BEMPEL. 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

- I. Introduction

- II. Architecture

- III. Listes chaînées et tableaux dynamiques

- III-A. Listes chaînées

- III-B. Tableaux dynamiques

- III-C. Listes chaînées vs tableaux dynamiques

- III-C-1. Ajout/suppression

- III-C-2. Parcours

- III-C-3. Accès aléatoire

- IV. Les listes dans la DCL

- IV-A. ArrayList

- IV-B. LinkedList

- IV-C. Vector

- V. Conclusion

I - Introduction

Cet article est le premier d'une série concernant la bibliothèque Delphi Container Library (DCL) que j'ai développée. la DCL est une bibliothèque de classes et d'interfaces conteneurs de types listes, maps, ensembles, arbres, etc. Elle est largement inspirée de la bibliothèque équivalente du langage Java et de la STL C++. Les interfaces tiennent une part importante dans l'architecture de la DCL, car elles permettent une gestion automatique de la mémoire par compteur de référence (reference counting). La connaissance de leur fonctionnement reste indispensable à la bonne compréhension de la bibliothèque.

Cette série d'articles a pour but à la fois de tutoriel de la DCL et de la bonne utilisation des structures de données qu'elle introduit. En effet chaque structure n'est pas optimale pour toutes les utilisations. Chacune d'entre elles a son domaine de prédilection. Par exemple un Vector sera très rapide pour le parcours, mais plutôt mauvais pour l'insertion ou la suppression d'éléments alors que la LinkedList est bien adaptée pour cela.

Dans le présent article, nous verrons une brève introduction à l'architecture de la DCL et les concepts généraux que l'on retrouvera tout au long de la manipulation des structures de données et une comparaison tableau dynamique/Liste chaînée.  Puis nous présenterons les trois types de listes (ArrayList, LinkedList et Vector) et comment les utiliser de façon optimale.

La DCL est téléchargeable ici.

II - Architecture

Les interfaces sont la colonne vertébrale de la DCL. Elles définissent les opérations de base supportées que devra implémenter chaque structure. La plupart des interfaces sont doublées pour la gestion d'objets interfacés ou non. Ainsi, IIntfCollection est l'interface permettant de gérer une collection d'objets interfacés (IInterface) et ICollection est l'interface permettant de gérer une collection d'objets simples (TObject).

Les interfaces de base sont IIntfCollection/ICollection, IIntfMap/IMap, IIntfStack/IStack et IIntfQueue/IQueue. IIntfList/IList hérite de IIntfCollection/ICollection. Ces dernières interfaces sont celles qui vont être implémentées pour les listes. Les interfaces d'ensembles IIntfSet/ISet dérivent elles aussi de IIntfCollection/ICollection. Les Maps sont des conteneurs permettant d'associer une clé à une valeur. Les descendantes IIntfSortedMap/ISortedMap sont des maps triées.

Une entité très importante dans la bibliothèque est l'itérateur (IIntfIterator/IIterator). Comme dans la STL  C++ ou en Java, un itérateur permet d'itérer dans une collection. Il permet aussi de référencer un objet et d'effectuer des manipulations sur ce dernier. Ils seront très utiles dans les algorithmes liés aux collections.

Les interfaces IIntfComparator/IComparator servent à implémenter les comparaisons entre objets. Cette externalisation de la comparaison sous forme de méthode à implémenter permet d'effectuer des comparaisons spécifiques sur des objets et une comparaison dite profonde, c'est-à-dire non pas simplement basée sur la référence de l'objet, mais sur ses attributs internes.

Enfin, les interfaces IIntfCloneable/ICloneable permettent d'implémenter une copie profonde avec le même mécanisme que les comparateurs. Chaque structure de la DCL implémente ces interfaces.

Les classes implémentant les interfaces IIntf* attendent des variables de type IInterface. Il faut donc passer des objets implémentant au moins cette interface. La classe TInterfacedObject implémente IInterface en dérivant la classe TObject et introduit le mécanisme de compteur de référence permettant la libération automatique de l'objet dès qu'il n'y a plus de référence sur celui-ci. Donc tout objet dérivant de la classe TInterfacedObjet pourra être manipulé par les classes conteneurs TIntf* (TIntfArrayList, TIntfLinkedList, TIntfHashMap…) en bénéficiant du référence counting.

type
IIntfMyObject = interface
['{BA33CBCC-9CB2-4672-BF54-F52C2A0BEFFE}']
function GetInt: Integer;
function GetStr: string;
procedure SetInt(Value: Integer);
procedure SetStr(const Value: string);
property Int: Integer read GetInt write SetInt;
property Str: string read GetStr write SetStr;
end;

TIntfMyObject = class(TInterfacedObject, IIntfMyObject)
private
FInt: Integer;
FStr: string;
protected
{ IIntfMyObject }
function GetInt: Integer;
function GetStr: string;
procedure SetInt(Value: Integer);
procedure SetStr(const Value: string);
end;

var
MyObject: IIntfMyObject;
begin
MyObject := TIntfMyObject.Create;
MyObject.Int := 42;
MyObject.Str := 'Coucou';
end; // Libération automatique de l'objet, car sortant de la portée de la variable, seule référence sur l'objet

III - Listes chaînées et tableaux dynamiques

III-A - Listes chaînées

Quand on parle de liste, on pense tout de suite aux listes chaînées que l'on a pu apprendre dans les cours d'algorithmique, mais pour faire des listes d'objets ce n'est pas forcément celles-ci qui sont les plus adaptées.

Pour rappel, une liste chaînée est une collection d'entités (Items) ayant au moins la structure suivante : une cellule permettant de stocker l'objet à contenir et un pointeur sur l'item suivante.

Le grand avantage d'une telle structure est sa grande souplesse pour la gestion d'un nombre indéterminé d'objets. Cependant cette structure possède les inconvénients suivants :

1. Allocation d'un item à chaque ajout.

2. Gestion des items relativement lourde.

3. Déréférencement en chaîne lors d'un parcours.

Ces trois points pénalisent cette structure au niveau des performances : les points 1. et 2. sont pénalisés lors des opérations d'ajout et/ou de suppression. En effet une allocation d'objet reste une opération complexe prenant un temps non négligeable lors d'ajout massif. Ajoutez à cela la gestion des pointeurs qu'il faut maintenir à jour. Enfin, lors d'un parcours de liste, le déréférencement des pointeurs pour passer d'un item à l'autre est une opération qui n'est pas optimale au niveau des performances.

III-B - Tableaux dynamiques

On oublie souvent les tableaux, car on les associe à une structure figée. Mais c'est oublier les possibilités de réallocation qui sont mises à notre disposition. En effet il est possible à partir d'une structure préalablement allouée, de modifier sa taille par une méthode telle que ReallocMem. Ainsi, si on veut étendre un tableau, l'appel à cette fonction va permettre de repousser les précédentes limites de celui-ci sans toucher aux données déjà présentes.

Une liste utilisant un tableau dynamique stocke dans chaque cellule l'objet qu'elle doit contenir.

Les avantages d'une gestion de liste par tableau dynamique sont les suivants :

1. Ajout en fin de liste très simple.

2. Allocations moins fréquentes.

3. Parcours indexé très rapide.

Mais cette technique possède un inconvénient majeur concernant l'ajout et la suppression en milieu de liste. Ceci implique le déplacement des objets qui sont derrière celui que l'on veut insérer ou supprimer.

III-C - Listes chaînées vs tableaux dynamiques

Nous allons effectuer la comparaison par opération élémentaire.

III-C-1 - Ajout/suppression

Pour un ajout/suppression en fin de liste, le tableau dynamique est le plus adapté, car il suffit de placer/retirer l'objet à la dernière case. Il n'y a pas d'autre instruction qu'une affectation. L'allocation  de nouvelles se faisant par bloc est moins fréquente que pour la liste chaînée et donc moins coûteuse. Une liste chaînée doit maintenir à jour les pointeurs et faire une allocation d'un item. On considère quand même que la liste chaînée conserve un pointeur sur le dernier élément permettant ainsi de ne pas parcourir la liste entière pour se positionner à la fin.

Pour un ajout/suppression en milieu de liste, la liste chaînée est en moyenne plus efficace (en ayant au préalable une référence sur l'endroit ou l'on insert/supprime). L'insertion prend le même temps, quel que soit l'endroit où l'on se trouve dans la liste chaînée. Par contre pour le tableau dynamique, ce temps est proportionnel au nombre d'objets se trouvant après l'endroit où l'on ajoute/supprime l'élément, car on doit effectuer un déplacement de ces objets.

III-C-2 - Parcours

Le parcours d'une collection d'objets du début jusqu'à la fin sera plus performant sur un tableau dynamique qu'une liste chaînée du fait que ce parcours est indexé. En effet le passage d'un élément à l'autre correspond à une simple instruction d'incrément qui correspond la plupart du temps à une instruction du processeur. Pour la liste chaînée, il est nécessaire de faire plusieurs affectations correspondant au déréférencement.

III-C-3 - Accès aléatoire

un accès aléatoire consiste à récupérer un objet se trouvant à une position quelconque de la liste. Par exemple on voudrait accéder au 42e élément de la liste. Du fait que le tableau dynamique est indexé de par sa nature, il est le plus performant pour ce genre d'opération. Pour une liste chaînée, il faudra parcourir les 41 premiers objets pour accéder à celui désiré.

IV - Les listes dans la DCL

IV-A - ArrayList

Les classes TIntfArrayList/TArrayList implémentent les couples d'interfaces IIntfCollection/ICollection et IIntfList/IList avec un tableau dynamique pour stocker les objets.

Nous voulons avoir une liste d'objets TPerson définis de la manière suivante :

IPerson = interface
['{755C857B-A9E2-4D9D-8418-541CAEA79679}']
function GetAge: Integer;
function GetMarried: Boolean;
function GetName: string;
procedure SetAge(Value: Integer);
procedure SetMarried(Value: Boolean);
procedure SetName(const Value: string);
property Age: Integer read GetAge write SetAge;
property Married: Boolean read GetMarried write SetMarried;
property Name: string read GetName write SetName;
end;

TPerson = class(TInterfacedObject, IPerson)
private
FAge: Integer;
FMarried: Boolean;
FName: string;
protected
{ IPerson }
function GetAge: Integer;
function GetMarried: Boolean;
function GetName: string;
procedure SetAge(Value: Integer);
procedure SetMarried(Value: Boolean);
procedure SetName(const Value: string);
end;

On définit alors la liste de la façon suivante :

var
List: IIntfList;
APerson: IPerson;
It: IIntfIterator;
begin
List := TIntfArrayList.Create;
APerson := TPerson.Create;
APerson.Age := 42;
APerson.Name := 'Hari Seldon';
APerson.Married := True;
List.Add(APerson);
APerson := TPerson.Create;
APerson.Age := 30;
APerson.Name := 'Golan Trevize';
APerson.Married := False;
List.Add(APerson);

APerson := IPerson(List.GetObject(0)); // Récupère le premier élément de la liste
ShowMessage(APerson.Name);

// Iteration
It := List.First;
while It.HasNext do
begin
APerson := IPerson(It.Next); // Récupère l'objet courant et incrémente l'itérateur
ShowMessage('Name: ' + APerson.Name + ' Age: ' + IntToStr(APerson.Age));
end;
end;

La variable List est de type IIntfList. On passe donc par cette interface pour avoir un référence counting permettant ainsi de ne pas se soucier de sa libération. Les méthodes de la classe TIntfArrayList sont en protected pour forcer à l'utilisation de l'interface. De plus on est ainsi indépendant au niveau des méthodes appelées de la manière dont sont implémentées les méthodes. On pourrait en changeant seulement l'instanciation utiliser la classe TIntfLinkedList.

De même pour la variable APerson : on manipule l'interface pour la référence counting et pour appeler les méthodes ou propriétés propres à l'objet. La définition d'interfaces pour ce genre d'objet peut paraître lourde, mais le gain apporté par la gestion automatique de l'objet permet d'éviter des problèmes de multiples références. Par exemple, supposons deux listes, chacune d'elles contient une référence sur un objet instancié une seule fois en mémoire. On décide de supprimer cet élément d'une des listes et donc de le libérer. La deuxième liste n'est pas informée de la libération de l'objet et possède donc une référence sur un objet qui n'existe plus. Avec la méthode de référence counting, le compteur sera  supérieur à 0 après effacement de la première liste et l'objet ne sera pas libéré, restant valide pour la deuxième.

Dans l'exemple ci-dessus, on parcourt la liste avec un itérateur (It). Cette méthode permet d'être indépendante de l'implémentation (liste chaînée ou tableau dynamique) tout en restant très optimisée. En effet par le système d'interface, chaque classe implémente son propre mécanisme d'itération spécifique et donc le plus performant possible : incrémentation d'un compteur pour le tableau, déréférencement de pointeur pour la liste chaînée. La méthode First renvoie un itérateur pointant sur le premier élément de la liste. La méthode HasNext teste s'il existe encore des objets à la position courante de l'itérateur. Enfin, la méthode Next renvoie l'objet courant et avance l'itérateur à la position suivante.

Les classes TIntfArrayList/TArrayList et TIntfVector/TVector implémentent aussi les interfaces IIntfArray/IArray fournissant une propriété Items permettant un raccourci syntaxique :

APerson := IPerson(List[0]); // ou APerson := IPerson(List.Items[0]);

Items est une propriété tableau par défaut utilisant les méthodes GetObject et SetObject des interfaces IIntfList/IList. Cette propriété n'est pas disponible au niveau de IIntfList/IList, car cette utilisation n'est pas optimisée pour les listes chaînées. Mais je vous conseille de passer par les itérateurs qui vous permettront d'avoir une écriture homogène, quel que soit le type de liste choisi et surtout compatible pour les algorithmes que vous pourrez appliquer sur ces collections.

Si la gestion des interfaces pour les objets ne vous convient pas, il est tout à fait possible de revenir à des objets simples dérivant de TObject en gérant leur libération de façon manuelle :

TPerson = class(TObject)
private
FAge: Integer;
FMarried: Boolean;
FName: string;
public
property Age: Integer read FAge write FAge;
property Married: Boolean read FMarried write FMarried;
property Name: string read FName write FName;
end;

var
List: IList;
APerson: TPerson;
It: IIterator;
begin
List := TArrayList.Create; // par défaut la liste gère elle-mème la libération des objets (OwnsObjets = True)
APerson := TPerson.Create;
APerson.Age := 42;
APerson.Name := 'Hari Seldon';
APerson.Married := True;
List.Add(APerson);
APerson := TPerson.Create;
APerson.Age := 30;
APerson.Name := 'Golan Trevize';
APerson.Married := False;
List.Add(APerson);

APerson := TPerson(List.GetObject(0)); // Récupère le premier élément de la liste
ShowMessage(APerson.Name);

// Iteration
It := List.First;
while It.HasNext do
begin
APerson := TPerson(It.Next); // Récupère l'objet courant et incrémente l'itérateur
ShowMessage('Name: ' + APerson.Name + ' Age: ' + IntToStr(APerson.Age));
end;
List.Clear; // Libération des objets par un Free, car OwnsObjets = True
List := nil;  // Libération de la liste
end;

On remarque que le code est très similaire à la version avec interface des objets. La DCL oblige tout de même à utiliser la liste en tant que telle par interface (IIntfList/IList), car les méthodes sont déclarées en protected dans les classes TIntfArrayList/TArrayList. On peut forcer la libération de la liste par une affectation à nil de la dernière et seule référence.

IV-B - LinkedList

Les classes TIntfLinkedList/TLinkedList implémentent les couples d'interfaces IIntfCollection/ICollection et IIntfList/IList avec une liste simplement chaînée pour stocker les objets.

On reprend la définition de TPerson en interface d'abord :

var
List: IIntfList;
APerson: IPerson;
It: IIntfIterator;
begin
List := TIntfLinkedList.Create;
APerson := TPerson.Create;
APerson.Age := 42;
APerson.Name := 'Hari Seldon';
APerson.Married := True;
List.Add(APerson);
APerson := TPerson.Create;
APerson.Age := 30;
APerson.Name := 'Golan Trevize';
APerson.Married := False;
List.Add(APerson);

APerson := IPerson(List.GetObject(0)); // Récupère le premier élément de la liste
ShowMessage(APerson.Name);

// Iteration
It := List.First;
while It.HasNext do
begin
APerson := IPerson(It.Next); // Récupère l'objet courant et incrémente l'itérateur
ShowMessage('Name: ' + APerson.Name + ' Age: ' + IntToStr(APerson.Age));
end;
end;

Les différences avec le code utilisant la classe TArrayList sont notées en bleu !! Il est donc très facile de cette manière de passer d'une implémentation à l'autre.

Maintenant la version avec une classe TPerson dérivant de Tobject :

var
List: IList;
APerson: TPerson;
It: IIterator;
begin
List := TLinkedList.Create; // par défaut la liste gère elle-même la libération des objets (OwnsObjets = True)
APerson := TPerson.Create;
APerson.Age := 42;
APerson.Name := 'Hari Seldon';
APerson.Married := True;
List.Add(APerson);
APerson := TPerson.Create;
APerson.Age := 30;
APerson.Name := 'Golan Trevize';
APerson.Married := False;
List.Add(APerson);

APerson := TPerson(List.GetObject(0)); // Récupère le premier élément de la liste
ShowMessage(APerson.Name);

// Iteration
It := List.First;
while It.HasNext do
begin
APerson := TPerson(It.Next); // Récupère l'objet courant et incrémente l'itérateur
ShowMessage('Name: ' + APerson.Name + ' Age: ' + IntToStr(APerson.Age));
end;
List.Clear; // Libération des objets par un Free, car OwnsObjets = True
List := nil;  // Libération de la liste
end;

Notez encore une fois la subtile différence avec la TArrayList !

Si vous utilisez GetObject avec une LinkedList, souvenez-vous que la méthode repart à chaque fois du début de la liste pour atteindre le ième élément indiqué par l'index passé en paramètre !

IV-C - Vector

Les classes TIntfLinkedList/TLinkedList implémentent les couples d'interfaces IIntfCollection/ICollection et IIntfList/IList avec un tableau dynamique pour stocker les objets. La grande différence avec les classes TIntfArrayList/TArrayList réside dans le fait que le tableau dynamique est déclaré dans une section public. Il est donc directement accessible depuis une instance. On utilisera donc le Vector par les classes elles-mêmes et non par les interfaces IIntfList/IList. L'avantage de disposer du tableau dynamique en public se situe au niveau des performances. En effet l'accès par l'intermédiaire de propriétés (et donc de méthodes Get/Set) ralentit considérablement l'accès aux éléments. Un accès direct indexé est directement optimisable par le compilateur ce qui donne des performances lors d'accès et de parcours du tableau impressionantes !

var
List: TIntfVector;
APerson: IPerson;
begin
List := TIntfVector.Create;
APerson := TPerson.Create;
APerson.Age := 42;
APerson.Name := 'Hari Seldon';
APerson.Married := True;
List.Add(APerson);
APerson := TPerson.Create;
APerson.Age := 30;
APerson.Name := 'Golan Trevize';
APerson.Married := False;
List.Add(APerson);

APerson := IPerson(List.Items[0]); // Récupère le premier élément de la liste
ShowMessage(APerson.Name);

// Iteration
for I := 0 to List.Size - 1 do
begin
APerson := IPerson(List.Items[I]); // Récupère l'objet a la position I
ShowMessage('Name: ' + APerson.Name + ' Age: ' + IntToStr(APerson.Age));
end;
end;

var
List: TVector;
APerson: TPerson;
begin
List := TVector.Create;
APerson := TPerson.Create;
APerson.Age := 42;
APerson.Name := 'Hari Seldon';
APerson.Married := True;
List.Add(APerson);
APerson := TPerson.Create;
APerson.Age := 30;
APerson.Name := 'Golan Trevize';
APerson.Married := False;
List.Add(APerson);

APerson := TPerson(List.Items[0]); // Récupère le premier élément de la liste
ShowMessage(APerson.Name);

// Iteration
for I := 0 to List.Size - 1 do
begin
APerson := TPerson(List.Items[I]); // Récupère l'objet a la position I
ShowMessage('Name: ' + APerson.Name + ' Age: ' + IntToStr(APerson.Age));
end;
end;

Du fait de l'accès direct au tableau dynamique, le Vector n'est pas Thread Safe, c'est-à-dire qu'il n'est pas protégé contre l'accès concurrent par plusieurs threads contrairement à l'ArrayList et à la LinkedList. Par défaut la DCL n'est pas compilé pour être Thread Safe pour des questions de performances. Si vous désirez être assuré de ne pas avoir de problème avec les threads accédant à vos listes, activez la directive de compilation $THREADSAFE se trouvant dans le fichier dcl.inc, puis recompilez la DCL. Les opérations de lecture et d'écriture seront alors protégées par une section critique.

Les classes TIntfVector/TVector sont donc conçues pour être utilisées là où la performance est primordiale, mais restent dans ce cas en marge du reste de la bibliothèque, car ne s'appuyant pas sur les interfaces IIntfList/IList. On peut toutefois référencer une classe Vector par une des interfaces de listes, mais on retombe alors sur une ArrayList classique.

V - Conclusion

Nous avons vu les avantages et inconvénients des deux types d'implémentations de listes, soit sous forme de liste chaînée, soit sous forme de tableau dynamique. En général c'est cette dernière méthode qui sera la plus efficace.

D'autre part, il a été présenté comment utiliser les listes ArrayList, LinkedList et Vector fournit par la bibliothèque DCL ainsi que son architecture à base d'interfaces la rendant très souple et pratique à l'utilisation, évitant par exemple une gestion manuelle de la libération.

Si vous avez des remarques, des idées d'améliorations, ou des bogues, n'hésitez pas à les reporter sur le site du projet: http://sourceforge.net/projects/dclx ou par E-Mail : rdm_30@yahoo.com.