PROFDINFO.COM

Votre enseignant d'informatique en ligne

Les indexeurs

Les indexeurs sont une petite fonctionnalité toute simple mais bien pratique dans une collection qui peut être ordonnée d'une façon quelconque. Ils permettent d'accéder à un item de la collection à partir de son numéro, comme pour un tableau, ou à partir de n'importe quelle information voulue, peu importe son type - remplaçant alors possiblement une fonction de recherche de façon fort élégante.

Un indexeur se déclare à peu près comme une propriété et pourra avoir une section get et une section set. Son nom est toujours this et on doit lui déclarer un paramètre entre crochets, paramètre qui sera utilisé pour identifier l'item à retourner. Ce paramètre est généralement un int, mais peut être n'importe quoi selon les désirs du créateur.

Un indexeur a également un type de retour, selon ce que l'on veut qu'il retourne (dans une collection générique, ce sera souvent T).

Un exemple concret: notre super pile d'assiettes

Voici de quoi pourrait avoir l'air un indexeur pour notre pile d'assiettes:

public T this[int i]
{
   get
   {
      return objets[i];
   }
   
   set
   {
      objets[i] = value;
   }
}

C'est très simple ici puisque nos données sont en fait stockées dans un tableau indexé. Une fois la pile indexée elle aussi, on peut faire simplement:

Console.WriteLine(p[1].couleur);

On peut ainsi accéder à n'importe quel élément d'une pile p (dans nos exemples ces éléments étaient des Assiettes, mais ça pourrait être n'importe quoi).

Un équivalent possible à l'utilisation d'un indexeur serait de rendre notre tableau de données public ou de créer une propriété publique qui nous permettrait d'y accéder. Toutefois on sera alors de faire quelque chose comme p.Données[1] au lieu de p[1] pour accéder à l'objet, ce qui est tout de même moins pratique et moins intuitif.

Indexer par autre chose qu'un nombre

Il est permis de définir un paramètre de n'importe quel type pour un indexeur. Il est même bien entendu possible de les surcharger. Par exemple, je pourrais décider que je veux permettre d'aller chercher une Assiette par couleur dans ma pile plutôt que par numéro. Par exemple, je voudrais pouvoir faire p["rouge"], et obtenir la première Assiette rouge de la pile.

En théorie, c'est bien possible de faire un indexeur qui reçoit un string plutôt qu'un entier. Toutefois, dans ce cas-ci, comme ma pile est générique, je devrai utiliser un délégué pour pouvoir définir le critère de recherche, puisque ma pile ne connaît que des T et pas des Assiettes. Je ne peux pas lui permettre de recevoir un string interprété comme une couleur car rien ne dit que ce que j'empile aura toujours une couleur...

Je devrai donc déclarer un délégué de type prédicat qui permet à une Assiette de comparer sa couleur avec celle d'une autre et qui retourne un booléen. Ensuite je peux créer un indexeur qui accepte une fonction de ce type comme paramètre et qui retourne le premier item pour lequel le prédicat retourne vrai:

public delegate bool prédicat(T item);

public T this[prédicat fonction]
{
   get
   {
      foreach (T t in data)
         if (fonction(t))
            return t;
      return default(T);
   }
}

Notre indexeur accepte donc une fonction de type "prédicat" en paramètre plutôt qu'un nombre. Il parcourt notre tableau de données interne et retourne le premier item identifié par la fonction. Si rien n'a été trouvé, il retourne le T par défaut (généralement null).

Du côté de l'Assiette, je créerai une fonction de type prédicat qui compare les couleurs:

public bool mêmeCouleur(Assiette autreAssiette)
{
   if (autreAssiette.couleur.CompareTo(couleur) == 0)
     return true;
   else
     return false;
}

Puis, dans mon programme de test, je peux chercher une assiette rouge en faisant ceci:

a = new Assiette("rouge", 0);
Console.WriteLine(p[a.mêmeCouleur].épaisseur);

Ainsi je trouve la première assiette rouge de la pile et j'affiche son épaisseur.

Si je voulais réellement permettre d'indexer par la couleur, ma seule solution serait de créer une toute nouvelle classe utilisant la PileGénérique et l'Assiette pour exposer des fonctionnalités de "piles d'assiettes", un peu comme vous avez fait dans le laboratoire 4 pour permettre de gérer une liste de méchants à partir d'une liste générique.

Ça pourrait ressembler (minimalement) à ceci:

class PileAssiettes
{
   public PileGénérique<Assiette> pile = new PileGénérique<Assiette>();
   
   public Assiette this[string couleur]
   {
      get
         {
            Assiette a = new Assiette(couleur, 0);
            return pile[a.mêmeCouleur];
         }
   }
}

Notre PileAssiettes est conçue pour empiler des Assiettes, mais elle utilise les fonctionnalités de notre PileGénérique pour y arriver sans effort. Elle contient donc une PileGénérique<Assiette> et elle n'expose ici qu'une seule fonctionnalité: un indexeur par couleur. Cet indexeur crée une Assiette de la couleur voulue et appelle l'indexeur de la PileGénérique avec le prédicat comme on faisait tout à l'heure.

Évidemment, pour que cette classe soit complète, il serait bien de lui créer des méthodes de type Push, Pop et Peek prévues pour des Assiettes. En attendant, on peut toujours utiliser ces méthodes de "pile", son attribut PileGénérique<Asssiette> (qui a d'ailleurs été laissé public pour nous simplifier cette tâche).

On peut donc faire:

PileAssiettes pa = new PileAssiettes();
pa.pile.Push(new Assiette("rouge", 2));  // Pas trop élégant...
pa.pile.Push(new Assiette("jaune", 3));
Console.WriteLine(pa["jaune"].épaisseur);  // Voici notre indexeur!
Console.WriteLine();

System.Collections.Generic


Maintenant que vous avez bien compris le principe de la pile générique et que vous avez vous-mêmes créé votre propre liste doublement chaînée générique, voici le moment de dévoiler un grand secret: tout ceci a déjà été créé pour vous de façon à vous éviter de devoir réinventer la roue!

Bien entendu, nous ne sommes pas les premiers à avoir besoin d'une liste générique et il en existe une toute faite pour nous dans l'environnement .NET.

L'espace de nom System.Collections.Generic contient plusieurs structures de données génériques communes, prêtes à être utilisés et livrées complètes avec indexeurs et itérateurs.

Mentionnons:

Évidemment, on aurait pu utiliser tous ces outils pour faire tous les laboratoires jusqu'à présent (à l'exception de celui sur les graphes)... Mais ça aurait été beaucoup moins amusant (sans oublier: beaucoup moins formateur)!

Dans mon exemple de PileGénérique, je mentionnais que d'utiliser un tableau pour y stocker nos données, puis de redimensionner constamment ce tableau était une bien mauvaise idée. La chose à faire aurait plutôt été d'utiliser une List<>. On peut l'instancier aussi aisément qu'un tableau, son indexeur nous permet de retrouver les données aussi aisément que dans un tableau et ajouter des items est très facile. Voici ce que ça aurait donné:

class PileGénérique<T> :IEnumerable<T>
{
   private List<T> data = new List<T>();
   private int nbItems = 0;
   
   public void Push(T item)
   {
      data.Add(item);
      nbItems++;
   }
   
   public T Pop()
   {
      if (nbItems == 0)
         return default(T);
      else
      {
         T item = data[nbItems - 1];
         data.RemoveAt(nbItems - 1);
         nbItems--;
         return item;
      }
   }
   
   public T Peek()
   {
      if (nbItems == 0)
         return default(T);
      else
         return data[nbItems - 1];
   }
   
   public IEnumerator<T> GetEnumerator()
   {
      foreach (T item in data)
         yield return item;
   }
   
   IEnumerator IEnumerable.GetEnumerator()
   {
      return GetEnumerator();
   }
   
   public IEnumerable<T> énumérateurInverse
   {
      get
      {
         for (int i = nbItems - 1; i >= 0; i--)
            yield return data[i];
      }
   }
   
   public T this[int i]
   {
      get
      {
         return data[i];
      }
      set
      {
         data[i] = value;
      }
   }
   
   public delegate bool prédicat(T item);
   
   public T this[prédicat fonction]
   {
      get
      {
         foreach (T t in data)
         if (fonction(t))
            return t;
         return default(T);
      }
   }
}

Bien peu de changements ont été nécessaires pour conserver toutes les fonctionnalités de notre PileGénérique, tout en utilisant une List<> au lieu d'un tableau:

La grande différence est que maintenant notre PileGénérique est beaucoup plus efficace puisque Push et Pop ont un temps O(1) plutôt que O(n) lorsque n > 10... Ou est-ce bien le cas?

Pas tout à fait. Il se trouve qu'en réalité, une List<> est gérée approximativement comme notre première version de PileGénérique<>, c'est-à-dire avec un tableau interne qui grossit à mesure que le besoin s'en fait sentir. Par contre, une grande différence: le tableau n'est pas augmenté d'une case à la fois comme on l'avait fait. L'attribut Capacity d'une List<> indique sa taille (à ne pas confondre avec le nombre d'éléments qu'elle contient, indiqué par Count). Capacity commence à 0, passe à 4 dès qu'on insère un élément puis est ensuite doublée à chaque fois qu'on fait une insertion dans une liste pleine. Cet algorithme est évidemment beaucoup plus efficace puisque le tableau est redimensionné uniquement sur une base logarithmique.

Si on veut réellement utiliser une vraie de vraie liste chaînée avec des noeuds qui pointent vers d'autres noeuds, il faut utiliser LinkedList<>. Par contre si on insère toujours à la fin de la liste (comme on le fait dans notre PileGénérique<>), le temps de création de noeuds et les nombreuses assignations sont plus coûteux que l'utilisation d'une List<> à tableau interne, donc la performance se trouve en fait diminuée. La LinkedList<> est toutefois fort utile si on veut insérer des noeuds quelque part au milieu de la liste, à des endroits différents à chaque fois. Tenter de faire ça avec une List<> coûterait très cher en temps d'exécution comme en temps de programmation.

Sachant tout cela, que devrions-nous utiliser alors?

Bref, dans le cas de notre PileGénérique<>, si on suppose qu'on ne peut pas simplement utiliser un Stack<> parce qu'on décide d'y implémenter différentes méthodes personnelles, on peut conserver l'usage de la List<> si le nombre d'insertions ne sera jamais trop grand, question de garder le code simple. Si jamais le nombre d'insertions devenait énorme, on pourrait retourner au tableau, mais en implémentant une méthode d'agrandissement exponentielle.

On peut se convaincre de tout ça en utilisant le petit programme suivant, qui fait des insertions en boucle pour chaque différent type de collection et qui chronomètre le temps requis.

Notez au passage l'utilisation des structures DateTime, un type de données conçu pour stocker des dates et heures et y accéder par différentes unités de mesure de temps aisément. La méthode statique Now retourne l'heure courante du système, précise aux 10 millisecondes.

Un TimeSpan est utilisé pour stocker la différence entre deux DateTime, un pris avant le début des opération et un pris après. Cette différence est aisément exprimée en terme d'unités de temps et est donc précise au 20 millisecondes près (puisqu'elle dépend de deux structures DateTime avec chacune leur marge d'erreur).

static void Main(string[] args)
{
   // Détermine combien d'insertions seront faites dans chaque structure
   int nbInsertions = 1000000; 
   
   // Un tableau de Noeuds, avec sa capacité et son contenu
   Noeud[] t = new Noeud[0];
   int taille = 0, nbItems = 0;
   
   // Une liste (gérée via un tableau interne)
   List<Noeud> l = new List<Noeud>();
   // Utilisé simplement pour observer les variations de Capacity de la liste
   int old = -1;
   
   // Une liste chaînée
   LinkedList<Noeud> ll = new LinkedList<Noeud>();
   
   // Une pile
   Stack<Noeud> s = new Stack<Noeud>();
   
   DateTime start, end;  // Pour prendre l'heure du système
   TimeSpan ts; // La différence entre les DateTime = le temps écoulé
   
   Console.WriteLine("Nb d'insertions:  " + nbInsertions);
   Console.WriteLine("-------------------------------");
   
   // Insertion dans un tableau redimensionné comme une List<>
   start = DateTime.Now;
   for (int i = 0; i < nbInsertions; i++)
   {
      if (i == taille) // Si le tableau est "plein"
      {
         if (taille == 0) // La première fois
            taille = 4; // On le redimensionne à 4
         else
            taille *= 2; // Sinon on double
   
         Array.Resize<Noeud>(ref t, taille);
      }
      t[nbItems++] = new Noeud();  // Insertion d'un noeud après le dernier élément
   }
   end = DateTime.Now;
   ts = end - start;
   Console.WriteLine("Tableau augmenté: " + ts.Minutes + ":" + ts.Seconds + "." + ts.Milliseconds);
   
   Console.WriteLine("-------------------------------");

   // Insertions dans un tableau à grandeur convenable définie dès le départ
   nbItems = 0;  // On réinitialise
   start = DateTime.Now;
   t = new Noeud[nbInsertions]; // On crée un grand tableau
   for (int i = 0; i < nbInsertions; i++)
   {
      t[nbItems++] = new Noeud(); // On insère toujours à la suite
   }
   end = DateTime.Now;
   ts = end - start;
   Console.WriteLine("Tableau de " + nbInsertions + ": " + ts.Minutes + ":" + ts.Seconds + "." + ts.Milliseconds);
   
   Console.WriteLine("-------------------------------");
   
   // Insertions dans une List<> qu'on laisse se redimensionner au besoin
   start = DateTime.Now;
   for (int i = 0; i < nbInsertions; i++)
   {
      // Décommenter les lignes suivantes pour voir l'évolution de la Capacity
      // en fonction du nombre d'éléments dans la liste (ceci ne devrait pas
      // être fait lorsqu'on veut comparer les performances puisque ça a un
      // impact sur le temps de traitement
      //if (old != l.Capacity)
      //{
      //    Console.WriteLine(i +":"+l.Capacity);
      //    old = l.Capacity;
      //}
      l.Add(new Noeud());  // Insère à la fin
   }
   end = DateTime.Now;
   ts = end - start;
   Console.WriteLine("List<> augmentée: " + ts.Minutes + ":" + ts.Seconds + "." + ts.Milliseconds);
   
   Console.WriteLine("-------------------------------");
   
   // Insertions dans une List<> à capacité convenable dès le départ
   l.Clear();  // On vide la liste (opération hors du chrono)
   start = DateTime.Now;
   l.Capacity = nbInsertions; // On change la capacité
   for (int i = 0; i < nbInsertions; i++)
   {
      l.Add(new Noeud());
   }
   end = DateTime.Now;
   ts = end - start;
   Console.WriteLine("List<> à capacité " + nbInsertions + ": " + ts.Minutes + ":" + ts.Seconds + "." + ts.Milliseconds);
   
   Console.WriteLine("-------------------------------");
   
   // Insertions dans une LinkedList<>
   start = DateTime.Now;
   for (int i = 0; i < nbInsertions; i++)
   {
     ll.AddLast(new Noeud()); // On insère toujours à la fin
   }
   end = DateTime.Now;
   ts = end - start;
   Console.WriteLine("LinkedList<>: " + ts.Minutes +":"+ts.Seconds + "." + ts.Milliseconds);
   
   Console.WriteLine("-------------------------------");
   
   // Insertions dans un Stack<>
   start = DateTime.Now;
   for (int i = 0; i < nbInsertions; i++)
   {
      s.Push(new Noeud()); // On pousse chaque item sur la pile
   }
   end = DateTime.Now;
   ts = end - start;
   Console.WriteLine("Stack<>: " + ts.Minutes + ":" + ts.Seconds + "." + ts.Milliseconds);
   
   Console.ReadLine();
}