9 min read Apprendre

Introduction aux itérateurs en C#

Introduction aux itérateurs en C#
Photo by Daria Nepriakhina 🇺🇦 / Unsplash

Cet article présente les itérateurs tels qu’ils sont définis dans le framework 1.0/1.1 et 2.0. Il propose tout d’abord une présentation de l’implémentation dans le framework 1.0, présente ensuite les nouveautés dans la version 2.0 et donne finalement quelques exemples d’utilisations bien pratiques.

Définition d’un itérateur

Un itérateur est un design pattern utilisé couramment dans les langages objets de haut niveau comme Java ou C#. Il permet de parcourir une liste d’éléments de manière ordonnée dans avoir à se soucier de la manière dont sont stockés les éléments. C’est un design pattern de comportement qui permet de parcourir de manière unique une collection d’objet. Pour plus d’informations sur les designs pattern en général, je vous invite à consulter l’excellent article trouvé sur Wikipédia: Design Pattern, Iterateur

Fonctionnement des itérateurs dans .NET 1.0/1.1

Utilisation d’un itérateur

Vous avez peut être déjà utilisé des itérateurs dans .NET sans le savoir. Microsoft a développé un ensemble de classes dont beaucoup sont utilisables comme des itérateurs. En réalité, il est possible d’itérer sur un objet dès le moment qu’il implémente l’interface IEnumerable.

Beaucoup de collections, listes, tables de hashages implémentent cette interface. Grâce à cela, il est possible d’utiliser l’opérateur foreach de C# pour itérer sur une collection d’objet.

Voici un exemple très simple:

ArrayList liste = new ArrayList();
liste.Add("hello");
liste.Add("bonjour");
liste.Add("au revoir");
liste.Add("bye");
foreach (string element in liste)
{
  Console.WriteLine(element);
}

Cet exemple affiche ceci sur la sortie console:

hello
bonjour
au revoir
bye

Rien d’extraordinaire c’est vrai mais nous avons tout de même réussi à parcourir une liste de manière très simple. Ce fonctionnement est utilisable pour n’importe quel type d’objet tant que le conteneur implémente IEnumerable.

Implémentation

L’interface IEnumerable contient la méthode suivante:

IEnumerator GetEnumerator()

Cette méthode doit retourner une instance de type IEnumerator. Cette interface contient les méthodes suivantes :

object Current { get; }
bool MoveNext();
void Reset();

La propriété Current retourne l’élément courant de la collection. La méthode MoveNext permet de passer à l’élément suivant. Elle retourne false quand la collection est arrivée à la fin. La méthode Reset permet de réinitialiser la collection pour retourner sur le premier élément.

Exemple simple

Voyons de plus près comment créer un itérateur simple. Dans mon exemple, j’utilise comme nom de classe OldIterator, en référence aux itérateurs de .NET 1.0/1.1. Les itérateurs de .NET 2.0 fonctionnent un peu différemment. (Le code source est proposé à la fin de cette partie)

Première étape: créer une classe qui implémente IEnumerable
class OldIterator: IEnumerable
{
  private string[] m_Values = {
  "a","
  "b",
  "c",
  "d"
  };
  
  #region IEnumerable Members
  
  public IEnumerator GetEnumerator()
  {
  return new OldIteratorEnumerator(this);
  }
  
  #endregion
}

Cet exemple présente deux parties: un liste d’éléments fixe qui contient nos valeurs et la méthode GetEnumerator qui permet d’utiliser cette classe avec foreach.

Deuxième étape: créer une classe qui implémente IEnumerator

Une pratique courante est d’inclure la classe énumerateur dans la classe IEnumerable. Ceci permet de partager facilement les données de deux classes (la sous-classe aura accès aux membres de la classe parente). Il suffit donc d’ajouter le code suivant dans la classe OldIterator :

internal class OldIteratorEnumerator : IEnumerator
{
  private OldIterator m_Parent;
  private int m_Index;
  public OldIteratorEnumerator(OldIterator parent)
  {
    m_Parent = parent;
    m_Index = -1;
  }

  #region IEnumerator Members

  ///
  /// Retourne l’objet courant.
  ///
  public object Current
  {
    get
    {
      Console.WriteLine("### Appel de Current");
      if (m_Index > 0)
        throw new ApplicationException("L’index n’a pas encore été initialisé. Il faut appeler la méthode MoveNext en premier.");

      return m_Parent.m_Values[m_Index];
    }
  }
  ///
  /// Passer à l’élément suivant.
  ///
  /// true s’il y a encore des éléments après, false si c’est la fin.
  public bool MoveNext()
  {
    bool resultat;

    m_Index++;
    if (m_Index >= m_Parent.m_Values.Length)
      resultat = false;
    else
      resultat = true;
    Console.WriteLine("### Appel de MoveNext(resultat={0})", resultat);
    return resultat;
  }
  ///
  /// Réinitialise le pointeur d’élément pour retourner au premier.
  ///
  public void Reset()
  {
    Console.WriteLine("### Appel de Reset");
    m_Index = -1;
  }

  #endregion
}
Troisième étape: écriture d’une classe de test

Nous avons fait la plus grosse partie du travail, la classe de test montre comme utiliser notre itérateur.

class TestIterateur
{
  static void Main(string[args)
  {
    OldIterator iterator = new OldIterator();
    Console.WriteLine("Les valeurs de l’iterateur:");
    foreach (string value in iterator)
    {
      Console.WriteLine("> " + value);
    }
    Console.ReadLine();
  }
}

Les valeurs de l'itérateur:

Appel de MoveNext(resultat=True)
Appel de Current --> a
Appel de MoveNext(resultat=True)
Appel de Current --> b
Appel de MoveNext(resultat=True)
Appel de Current --> c
Appel de MoveNext(resultat=True)
Appel de Current --> d
Appel de MoveNext(resultat=False)

Fonctionnement interne

En analysant le résultat de l’exemple précédant, nous pouvons imaginer le fonctionnement de l’opérateur foreach.

foreach (string element in iterator)
{
  Console.WriteLine(element);
}

Le compilateur génère l’équivalent du code suivant :

while (iterator.MoveNext())
{
  string element = iterator.Current as string;
  Console.WriteLine(element);
}

Et voilà pourquoi il est plus facile d’utiliser l’opérateur foreach. La syntaxe est plus simple à coder et plus facile à comprendre. Ce chapitre vous a présenté le fonctionnement des itérateurs dans .NET 1.0/1.1. C’est un concept simple mais qu’il faut connaître car ils sont utilises partout dans le framework .NET. De plus, les itérateurs vous apportent de la souplesse dans le codage. Plus besoin de connaître la taille d’une liste, d’initialiser un curseur au premier élément, etc. Le chapitre suivant présentera les itérateurs dans .NET 2.0.

Fonctionnement des itérateurs dans .NET 2.0

Utilisation d’un itérateur

.NET 2.0 introduit un nouveau moyen pour implémenter facilement des itérateurs. Néanmoins, l’utilisation d’un itérateur est identique:

foreach TypeElement element in liste_elements
{
// Traiter ‘element’.
}

La nouveauté par rapport à .NET 1.0/1.1 est l’introduction du mot clé yield. De plus, avec la possiblité d’utiliser des generics depuis .NET 2.0, il est désormais possible de créer des itérateurs typés ce qui rend le code plus robuste (les erreurs sont détectables plus tôt par le compilateur).

Implémentation

Grâce au mot-clef yield, vous pourrez créer des itérateurs typés très facilement puisque le compilateur va générer un grande partie du code. yield permet de retourner une collection d’élément automatiquement. Le compilateur s’occupe de générer le code nécessaire.

Exemple simple

Voyons un petit exemple. Nous allons créer un itérateur qui retourne des entiers. Par contre, par rapport à l’exemple de .NET 1.0/1.1, désormais nous n’avons plus besoin de mettre en place l’index, la méthode MoveNext, Reset et la propriété Current. Tout ceci est fait par le compilateur.

public class PowerIterator : IEnumerable<T>
{
  private int m_Number, m_Exponent;
  public PowerIterator(int number, int exponent)
  {
    m_Number = number;
    m_Exponent = exponent;
  }
  //
  // Méthode statique qu’on peut appeler simple par PowerIterator.Power.
  // Elle retourne un itérateur d’entiers qui représente la suite q^n avec
  // q = number et n = exponent.
  //
  public static IEnumerable Power(int number, int exponent)
  {
    int counter = 0;
    int result = 1;
    while (counter & lt; exponent)
    {
      result = result * number;
      yield return result;
      counter++;
    }
  }

  #region IEnumerable Members

  public IEnumerator GetEnumerator()
  {
    return Power(m_Number, m_Exponent).GetEnumerator();
  }
  #endregion

  #region IEnumerable Members

  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
  {
    return Power(m_Number, m_Exponent).GetEnumerator();
  }
  #endregion

}
  • Tout d’abord, on commence par indiquer qu’on implémente un itérateur de type int avec l’interface IEnumerable,
  • Il y a deux méthodes dans cette interface: une méthode typée et une autre méthode non typée (pour rester compatible avec la version 1.0/1.1),
  • Chacun de ces méthodes retourne un énumérateur de type IEnumerator grâce à la méthode Power,
  • La méthode Power retourne une suite de nombres qui représente les puissances d’un entier passé en argument.

Pour utiliser cet itérateur, voici une petite classe de démonstration. Elle propose deux moyens d’accès:

  • soit en instanciant l’itérateur et en utilisant le mot-clef foreach sur cette instance (méthode utilisée avec .NET 1.0/1.1),
  • soit en appelant directement la méthode Power qui retourne l’itérateur sous la forme IEnumerable.
class Program
{
  static void Main(string[args)
  {
    PowerIterator iterator = new PowerIterator(2, 5);
    // L’utilisation d’un itérateur typé permet de détecter une erreur
    // si on utilise le mauvais type en tant qu’élément.
    Console.WriteLine("Puissances de 2:");
    foreach (int n in iterator)
    {
      Console.WriteLine(n);
    }
    Console.WriteLine();
    // Un moyen encore plus simple pour accéder à l’itérateur:
    Console.WriteLine("Puissances de 3:");
    foreach (int n in PowerIterator.Power(3, 5))
    {
      Console.WriteLine(n);
    }
    Console.ReadLine();
  }
}

Cependant, avant d’utiliser ce mécanisme partout dans votre code, il convient de savoir ce que fait vraiment le compilateur. En effet, en ignorant son fonctionnement, on pourrait se retrouver avec une application lente ou qui ne fonctionne pas comme il faut.

Fonctionnement interne

Première approche

Pour arriver à comprendre le fonctionnement de l’opérateur yield, j’ai utilisé l’outil Reflector .NET (de Lutz Roeder) qui permet de désassembler le code et de générer une représentation équivalente en C#. Voici une représentation du code généré par le compilateur pour notre itérateur (les noms générés ont été traduits à la main pour plus de compréhension) :

internal class PowerIterator : IEnumerable, IEnumerable
{
  // Methods
  public PowerIterator(int number, int exponent);
  public IEnumerator GetEnumerator();
  public static IEnumerable Power(int number, int exponent);
  IEnumerator IEnumerable.GetEnumerator();
  // Fields
  private int m_Exponent;
  private int m_Number;
  // Nested Types
  private sealed class InternalPowerIterator : IEnumerable, IEnumerable,
  IEnumerator, IEnumerator, IDisposable
  {
    // Methods
    public InternalPowerIterator(int state);
    private bool MoveNext();
    IEnumerator IEnumerable.GetEnumerator();
    IEnumerator IEnumerable.GetEnumerator();
    void IEnumerator.Reset();
    void IDisposable.Dispose();
    // Properties
    int IEnumerator.Current { get; }
    object IEnumerator.Current { get; }
    // Fields
    private int m_state;
    private int m_current;
    public int m_exponent;
    public int m_number;
    public int m_counter;
    public int m_result;
    public int exponent;
    public int number;
  }
}

La méthode PowerIterator.Power est décrite par le code suivant :

public static IEnumerable Power(int number, int exponent)
{
  PowerIterator.InternalPowerIterator result = new PowerIterator.InternalPowerIterator(-2);
  result.m_number = number;
  result.m_exponent = exponent;
  return result;
}

Cette méthode instancie la classe InternalPowerIterator, initialise ses membres puis retourne le résultat. Nous pouvons donc en déduire que le compilateur génère automatiquement une classe interne qui sera utilisée pour notre itérateur. La méthode Power permet d’instancier cette classe généré.

Etude de la classe générée

Cette classe contient un ensemble de méthodes que nous allons analyser en détails.

Constructeur

Le constructeur de InternalPowerIterator prend en paramètre un entier qui indique un état (state).

MoveNext

private bool MoveNext()
{
  switch (this.m_state)
  {
    case 0:
      this.m_state = -1;
      this.m_counter = 0;
      this.m_result = 1;
      while (this.m_counter < this.exponent)
      {
        this.m_result *= this.number;
        this.m_current = this.m_result;
        this.m_state = 1;
        return true;
      Label_0060:
        this.m_state = -1;
        this.m_counter++;
      }
      break;
    case 1:
      goto Label_0060;
  }
  return false;
}

Cette méthode nous en apprend plus sur l’attribut m_state. Il s’agit très probablement de l’état d’un automate. En effet, en regardant le code switch, nous remarquons qu’il s’agit du code d’un automate à état très simple. Celui-ci ne gère que trois états: -2, 0 et 1. L’état -2 est réservé et indique probablement que l’automate n’est pas dans un état correcte. L’état 0 est celui qui initialise les membres de la classe est début la boucle while. L’état 1 permet de continuer la boucle while à l’aide du goto.

GetEnumerator

IEnumerator IEnumerable.GetEnumerator()
{
  PowerIterator.InternalPowerIterator result;
  // Comparaison de l’état actuel avec l’état -2 (non initialisé).
  if (Interlocked.CompareExchange(ref this.m_state, 0, -2) == -2)
  {
    // Si m_state = -2, alors m_state = 0 et retourner la même instance.
    result = this;
  }
  else
  {
    // Sinon retourner une nouvelle instance initialisée.
    result = new PowerIterator.InternalPowerIterator(0);
  }
  result.number = this.m_number;
  result.exponent = this.m_exponent;
  return result;
}
IEnumerator IEnumerable.GetEnumerator() {
  // Retourne une énumérateur à partir de la méthode IEnumerable.GetEnumerator().
  return this.System.Collections.Generic.IEnumerable.GetEnumerator();
}

La première méthode est très importante pour cette classe. C’est elle qui permet d’initialiser la valeur de m_state (l’état de l’automate). Elle utilise la méthode Interlocked.CompareExchange qui permet une comparaison/échange thread-safe et retourne une instance de son propre type. Pour le résultat, l’état est initialisé à 0.

Reset

Le code génère une exception indiquant que la méthode n’est pas implémentée. Reset() n’est donc pas supporté dans .NET 2.0.

Dispose

Cette méthode ne contient rien pour le moment.

La propriété Current

int IEnumerator.Current
{
  get
  {
    return this.m_current;
  }
}
object IEnumerator.Current
{
  get
  {
    return this.m_current;
  }
}

Analyse des observations

Nous remarquons que le code généré par le compilateur constitue un automate à état qui comporte quatre états:

  • l’état -2 indique que l’automate est invalide,
  • l’état 0 indique qu’il faut initialiser l’automate,
  • l’état 1 indique qu’il est initialisé et que l’on peut continuer le traitement,
  • l’état -1 indique que l’automate est en cours d’initialisation.

La méthode MoveNext contient le traitement qui permet de générer les éléments. La méthode GetEnumerator retourne un énumérateur dont l’automate se retrouve dans l’état initial. Etant donné que la méthode Reset n’est plus supportée, GetEnumerator retourne à chaque fois une nouvelle instance initialisé dans l’état 0 (indique le début de l’itération).

Bilan général

Nous avons vu qu’il devient très facile d’écrire des itérateurs grâce au mot-clef yield. Vous savez désormais que le compilateur génère une classe interne à notre implémentation qui permet de gérer un automate à états qui s’occupe de lister les éléments pendant les itérations. Il est important de noter que l’automate peut devenir complexe en fonction de votre traitement. Il ne faut pas non plus oublier que chaque boucle foreach va demander au runtime une nouvelle instance de la classe d’itération. Il faudra donc veiller à la consommation mémoire.

Pascal Lacroix

Pascal Lacroix