Delphi Container Library: Les listes - Club d'entraide des développeurs francophones

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 conteneures 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 à pour but à la fois de tutorial 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'entres 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ément alors que la LinkedList est bien adaptée pour cela.

Dans le présent article, nous verrons une bref 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 3 types de listes (ArrayList, LinkedList et Vector) et comment les utiliser de façon optimale.

Architecture

La colonne vertébrale de la DCL sont les interfaces. Elles définissent les opérations de bases supportées que devront 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'objet simple (TObject).

Les interfaces de bases sont IIntfCollection/ICollection, IIntfMap/IMap, IIntfStack/IStack et IIntfQueue/IQueue. IIntfList/IList héritent 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é 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érences 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 reference 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;

Listes chaînées et tableaux dynamiques

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:

Ces 3 points pénalisent cette structure au niveau des performances: Les points 1. et 2. sont pénalisant 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'une item à l'autre est une opération qui n'est pas optimale au niveau des performances.

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

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ères celui que l'on veut insérer ou supprimer.

Listes chaînées vs tableaux dynamiques

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'une 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 reparcourir 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 quelque 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.

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.

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 42ème é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é.

Les listes dans la DCL

ArrayList

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

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;

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 reference 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 le reference 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 2 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é 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 reference 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 parcours la liste avec un iterateur (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é. 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 iterateur 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:

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ée. Mais je vous conseille de passer par les iterateurs qui vous permettront d'avoir une écriture homogène quelque 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 simple dérivant de TObject en gérant leur libération de façon manuelle:

var
List: IList;
APerson: TPerson;
It: IIterator;
begin
List := TArrayList.Create; // par défaut la liste gére elle-meme 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.

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.

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és en bleu !! Il est donc très facile de cette manière de passer d'une implémentation à l'autre.

var
List: IList;
APerson: TPerson;
It: IIterator;
begin
List := TLinkedList.Create; // par défaut la liste gére elle-meme 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;

Attention: 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 !

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ême 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) ralenti 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 a 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 reste 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.

Conclusion

Nous avons vu Les avantages et inconvénients des deux types d'implémentation de listes, soit sous forme de liste chaînée, soit sous forme de tableau dynamique. En générale 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.

Introduction