Cours

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Les itérateurs en C++ ======

===== Généraliser les algorithmes =====

Considérons un algorithme de recherche d'un plus grand élément :

<code cpp>
template<class T> 
T find_greatest_element(T theArray[], size_t theNumberOfElements)
{
    if (theNumberOfElements == 0)
        return T();
    T greatestElement = theArray[0];
    for (int index = 1; index < theNummberOfElements; index++)
    {
        if (theArray[index] > greatestElement)
            greatestElement = theArray[index];
    }
    return greatestElement;
}
</code>

Ce code ne fonctionne qu'avec des tableaux, cependant ce code pourrait fonctionner a priori pour tout ensemble de données quelqu'il soit. En effet il suffirait de le réécrire cette manière en pseudo-code :

<code>
find_greatest_element(aCollection)
    si aCollection est vide:
        aucun plus grand élément.
    greatestElement <= premier élément de aCollection.
    tant qu'il existe un élément suivant de aCollection:
        nextElement <= élément suivant de aCollection
        si nextElement > greatestElement:
            greatestElement = nextElement;
  
    retourne greatestElement.
</code>

On constate donc que le code peut-être généraliser pour fonctionner avec n'importe quelle collection si on peut "énumérer" les éléments dans la cette collection d'éléments.

L'idée consiste donc à fournir une abstraction permettant d'énumérer les éléments dans une structure de données quelque soit.


===== L'itérateur : un moyen d'énumérer des valeurs dans une structure de données  =====

Pour pouvoir énumérer les éléments stockés dans une structure de données, il est nécessaire que cette structure de données fournissent une classe qui va permettre d'énumérer les données. Cette classe que l'on appeller iterateur va devoir fournir les opérateurs suivants : 

|''operator ==(iterator)''|test si deux iterateurs font référence au même élément stocké dans la structure de données.|
|''value_type operator *()''|retourne une référence sur l'élément stocké dans la structure de données.|
|''operator +()''|passe à l'élément situé après l'élément actuellement référence par l'itérateur.|

Il s'agit là des opérations minimales qu'un itérateur doit fournir. Il existe des énumérateurs plus riches qui ajoutent des opérations supportées comme notamment :

|''operator --()''|passe à l'élément situé avant l'élément actuellement référence par l'itérateur.|

pour des itérateurs qui sont dits réversibles. 

Désormais, il est possible de réécrire le code précédent comme suit :

<code cpp>
template<class iterator>
iterator find_greatest_element(iterator itStart, iterator itEnd)
{
    if (itBegin == itEnd)
        return itEnd;
    iterator itGreatest = itStart;
    itStart ++;
    while(itStart != itEnd)
    {
        if(*itStart > *itGreatest)
            itGreatest = itStart;
        itStart ++;
    }
    return itGreatest;
}
</code>

La fonction prend en entrée un interval qui est défini par l'itérateur référençant le premier élément de la séquence et l'itérateur référençant le premier élément n'étant plus dans la séquence, celui situé après le dernier élément de la séquence (souvent appelé l'itérateur de fin). Le séquence est vide si l'itérateur ''itStart'' correspond à l'itérateur de fin ''itEnd''. Dans ce cas, nous retournons l'itérateur de fin ''itEnd'' indiquant qu'aucun élément n'a été trouvé. Sinon, nous considérons que le premier élément de la séquence est l'élément le plus grand, c'est pour cela que nous affectons à ''itGreatest'' la valeur ''itStart''. Puis nous parcourons la séquence d'élément en élément en "incrémentant" l'itérateur, incrémenter l'itérateur consiste à passer à l'élément suivant. Nous vérifions que l'élément auquel fait référence l'itérateur ''itStart'' est bien plus petit que l'élément auquel fait référence l'itérateur ''itGreatest''. Si ce n'est le cas, nous mettons à jour ''itGreatest'' avec la valeur d'''itStart'' qui correspond à l'élément courant et nous continuons d'énumérer les éléments de la séquence jusqu'à arriver au dernier élément de la séquence. La fonction retourne alors l'itérateur ''itGreatest'' qui fait référence au plus grand élément de la séquence d'éléments.

L'intérêt des itérateurs est de permettre d'énumérer des éléments stockées dans une structure de données sans avoir à connaitre ni la structure de données, ni l'implantation. C'est à la structure de données de fournir un objet ''iterator'' qui permettre d'accéder aux données selon l'interface.

De fait, il devient possible d'écrire des algorithmes qui sont indépendant des structures de données. C'est d'ailleurs le cas de la plupart des fonctions qui sont fournies par la STL dans le module [[https://en.cppreference.com/w/cpp/header/algorithm|''<algorithm>'']] fournissant des fonctions comme par exemple :

<code cpp>
template< class inputIterator, class T >
inputIterator find( inputIterator first, inputIterator last, const T& value );
</code>

qui recherche l'élément ''value'' dans une séquence délimitée par deux itérateurs ''inputIterator'' ''first'' et ''last''.
Cours

User Tools

Site Tools

Page Tools
