Differences

This shows you the differences between two versions of the page.

--- cpp:stl:iterator [2021/04/07 09:29]
bmonsuez [L'itérateur : un moyen d'énumérer des valeurs dans une structure de données]
+++ cpp:stl:iterator [2022/11/18 10:48] (current)
@@ Line 57: / Line 57: @@
 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''.
+Certains algorithmes de [[https://en.cppreference.com/w/cpp/header/algorithm|''<algorithm>'']] nécessitent des opérateurs supportant des opérations complémentaires comme par exemple
+<code cpp>
+template< class randomIterator>
+void sort(randomIterator first, randomIterator last);
+</code>
+qui classe l'ensemble des éléments situés dans la séquence délimitée par deux itérateurs ''first'' et ''last''. Cependant ces itérateurs ne sont pas des itérateurs simples que l'on qualifie [[https://en.cppreference.com/w/cpp/named_req/InputIterator|d'input itérator]] mais des itérateurs supportant des accès par indexation que l'on qualifie [[https://en.cppreference.com/w/cpp/named_req/RandomAccessIterator|de random iterator]].
+===== Les différents types d'itérateur =====
+C++ introduit différentes types d'itérateur qui sont rapidement énumérés ici :
+|[[https://en.cppreference.com/w/cpp/named_req/InputIterator|''input iterator'']] | itérateur permettant d'accéder en lecture à une donnée, supportant l'opération de comparaison et enfin le passage à l'élément suivant.|
+|[[https://en.cppreference.com/w/cpp/named_req/OutputIterator|''input iterator'']] | itérateur permettant d'écrire des données par exemple dans un flux supportant le passage à l'élément suivant.|
+|[[https://en.cppreference.com/w/cpp/named_req/ForwardIterator|''forward iterator'']] | ajoute à l'itérateur ''input operator'' la garantie que si ''a'' et ''b'' sont deux itérateurs de même type, si ''a == b'' alors ''++a == ++b''.|
+|[[https://en.cppreference.com/w/cpp/named_req/BidirectionalIterator|''bidirectional iterator'']] | ajoute à l'itérateur ''forward iterator'' la possibilité de revenir à l'élément précédent ((''operator --()'').|
+|[[https://en.cppreference.com/w/cpp/named_req/RandomAccessIterator|''random access iterator'']] | ajoute à l'itérateur ''bidirectional iterator'' la possibilité de se déplacer par saut de x éléments en avant ou en arrière.|
+Un algorithme peut ne fonctionner qu'avec un type particulier d'itérateur. Ainsi un algorithme de tri comme [[https://gist.github.com/svdamani/dc57e4d1b00342d4507d|quicksort ou merge sort]] auront le plus souvent besoin que l'on leur fournissent un ''random access iterator''.

Cours

User Tools

Site Tools

Differences

Page Tools