Delphi Container Library : les listes

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.

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.

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

III-C-1. Ajout/suppression▲

III-C-2. Parcours▲

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

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.

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 !

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.