====== Partie II – Création d’itérateurs ====== [[in204:tds:sujets:td4|TD4]] Nous considérons un ensemble de nombres entiers correspondant à un interval fermé entre [''minValue'', ''maxValue''] défini par la classe suivante : class interval { private: int minValue; int maxValue; public: typedef int value_type; typedef size_t size_type; typedef ptrdiff_t difference_type; interval(int theMinValue, int theMaxValue) : minValue(theMinValue), maxValue(theMaxValue) {} interval(const interval& anotherInterval): minValue(anotherInterval.minValue), maxValue(anotherInterval.maxValue) {} interval& operator = (const interval& anotherInterval) { minValue = anotherInterval.minValue; maxValue = anotherInterval.maxValue; return *this; } size_type size() const { return (size_type)(maxValue - minValue); } int operator[](size_type anIndex) const { if (anIndex > size()) throw std::out_of_range("Index out of range"); return minValue + (int)anIndex; } bool operator == (const interval& anotherInterval) const { return anotherInterval.maxValue == maxValue && anotherInterval.minValue == minValue; } bool operator != (const interval& anotherInterval) const { return anotherInterval.maxValue != maxValue || anotherInterval.minValue != minValue; } }; Nous souhaitons pouvoir définir des itérateurs pour pouvoir itérer sur cet interval. Pour ce faire, nous devons ajouter au moins les méthodes suivantes et champs suivants : friend class interval_iterator; typedef interval_iterator const_iterator; const_iterator begin() const noexcept; const_iterator end() const noexcept; En supposant que la classe itérateur s’appelle ''interval_iterator.'' Il ne reste plus qu’à créer une classe ''interval_iterator'' dont le squelette serait le suivant : class interval_iterator : public std::iterator { private: friend class interval; const interval* mInterval; // Référence à l'interval. int mCurrent; // la valeur courante dont on fait référence. interval_iterator(const interval& anInterval, int aCurrentValue) : mInterval(&anInterval), mCurrent(aCurrentValue) {} public: interval_iterator(const interval_iterator& anotherIterator): mInterval(anotherIterator.mInterval), mCurrent(anotherIterator.mCurrent) {} interval_iterator& operator = (interval_iterator& anotherIterator) { mInterval = anotherIterator.mInterval; mCurrent = anotherIterator.mCurrent; return *this; } const reference operator*() const; const pointer operator->() const; interval_iterator& operator++(); interval_iterator& operator++(int); bool operator ==(const interval_iterator&) const; bool operator !=(const interval_iterator&) const; }; ===== Question 1.0 ===== Complétez les classes ''interval'' et ''interval_iterator'' afin de pouvoir supporter les itérateurs. Nous débutons par compléter la classe ''interval''. La classe ''interval'' doit exposer au moins deux méthodes que sont les méthodes : iterator begin(); // Itérateur faisant référence au premier élément // contenu dans le containeur iterator end(); // Itérateur indiquant que l'on a dépassé le dernier // élément de la séquence d'éléments contenus // dans le containeur. De plus nous devons définir aussi les types suivants: value_type // le type des valeurs contenues dans le containeur. // habituellement ''T'' reference // un type faisant référence aux valeurs contenues dans // habituellement ''T&'' const_reference // un type faisant référence aux valeurs contenues dans // mais empêchant la modification de ces valeurs, // habituellement ''T&'' iterator // iterateur faisant référence aux valeurs contenues dans le containeur // permettant un accès en lecture et écriture de ces valeurs si l'accès // en écriture est supportée par le containeur. const_iterator // itérateur faisant référence aux valeurs contenues dans le containeur // ne permettant qu'un accès en lecture. difference_type // un type d'entier signé qui correspond à la distance entre deux itérateurs, size_type // Un type d'entier non-signé qui correspond au type taille du containeur. Dans le cas de notre classe ''interval'', le type des valeurs est ''int'', les valeurs ne peuvant pas être modifiées, ce qui induit les définitions suivantes : class interval { public: ... typedef const int value_type; typedef reference const int&; typedef const_reference const int&; ... }; Pour la classe ''iterator'', nous ne pouvons définir que des itérateurs ne pouvant pas modifier les valeurs contenues dans l'interval. Donc nous définissons les champs comme suit : class interval { public: ... typedef interval_iterator iterator; typedef interval_iterator const_iterator; typedef ptrdiff_t difference_type; typedef size_t size_type; ... }; Il reste dés lors à définir les fonctions ''begin'' et ''end''. Pour ce faire, nous définissons les fonctions comme suit : class interval { public: ... inline iterator begin() const; inline iterator end() const; ... }; class interval_iterator { }; inline interval::iterator interval::begin() const { return iterator(*this, minValue); } inline interval::iterator interval::end() const { return iterator(*this, maxValue + 1); } \\ La fonction ''begin'' retourne un objet de type ''interval_iterator'' qui fait référence à l'interval courant et qui fait référence à ''minValue'' qui correspond à la première valeur de l'interval d'entier. \\ La fonction ''end'' retourne un objet de type ''interval_iterator'' qui fait référence à l'interval courant et qui fait référence à ''maxValue'' qui correspond à la valeur situé après la dernière valeur valide de l'interval, donc fait bien référence à la première valeur située en dehors de la séquence de valeur. \\ Les fonctions ''begin'' et ''end'' font appel à un constructeur de la classe ''interval_iterator''. En C++, avant de pouvoir appeller un constructeur, il faut que la classe soit définie. Comme la classe ''interval_iterator'' est définie après la classe ''interval'', il est nécessaire que le code des fonctions ''begin'' et ''end'' soit située après la classe ''interval_iterator''. Il n'est pas possible de les définir dans le corps de la classe ''interval''. \\ Pour la classe ''interval_iterator'' nous devons implanter les exigences relatives à un [[https://en.cppreference.com/w/cpp/named_req/ForwardIterator|forward iterator]]. \\ - En ce qui concerne les définitions de type, il est attendu que l'itérateur expose les types suivants : \\ difference_type // un type d'entier signé servant à indiquer la distance entre deux itérateurs value_type // le type des valeurs qui sont référencés par l'itérateur // habituellement ''T'' pointer // le type d'un pointeur pointant sur les valeurs qui sont référencés par l'itérateur // habituellement ''T*'' reference // le type d'une référence sur les valeurs qui sont référencés par l'itérateur, // habituellement ''T&'' iterator_category // Le type qui indique la nature de l'itérateur, comme [https://en.cppreference.com/w/cpp/iterator/iterator_tags|std::random_access_iterator_tag]], [https://en.cppreference.com/w/cpp/iterator/iterator_tags|std::bidirectional_iterator_tag]], [https://en.cppreference.com/w/cpp/iterator/iterator_tags|std::forward_iterator_tag]] ou enfin [https://en.cppreference.com/w/cpp/iterator/iterator_tags|std::input_iterator_tag]]. \\ \\ Pour effectuer la définition de ces types, nous pouvons soit les définir directement (attention: les valeurs stockées dans l'interval n'est pas modifiable, il s'agit donc de ''const int''. : \\ class interval_iterator { public: typedef ptrdiff_t difference_type; typedef const int value_type; typedef const int* pointer; typedef const int& reference; typedef std::forward_iterator_tag iterator_category; }; \\ \\ On peut voir que l'on aurait pu faire références aux définitions faites dans la classe ''interval'', ce qui aurait donné le code suivant : \\ class interval_iterator { public: typedef ptrdiff_t difference_type; typedef interval::value_type value_type; typedef value_type* pointer; typedef value_type& reference; typedef std::forward_iterator_tag iterator_category; }; \\ L'avantage est que dans ce cas là, si nous modifions le type manipulé par la classe ''interval'', automatiquement, les types sont bien mis à jour dans la classe ''interval_iterator'' \\ \\ Pour éviter d'avoir trop à écrire, nous pouvons au contraire hériter de la classe [[https://en.cppreference.com/w/cpp/iterator/iterator|std::iterator]] qui fournit une implantation par défaut de ces types. \\ class interval_iterator: std::iterator { public: ... }; \\ Cependant cette méthode est déclarée obsolète depuis l'introduction de C++17. - En ce qui concerne les déclarations des opérateurs et fonctions membres, nous devons définir les opérateurs suivants : \\ reference operator*(); // retourne la valeur à laquelle l'itérateur fait référence. pointer operator->(); // retourne un pointeur sur la valeur à laquelle l'itérateur fait référence. iterator& operator++(); // avance à la valeur suivante de la séquence et retourne l'itérateur courant iterator operator++(int); // copie l'itérateur à la position actuelle, avance l'itérateur courant // à la valeur suivante de la séquence et retourne la copie de l'itérateur. bool operator ==(iterator) const; // compare si l'itérateur courant et l'itérateur passé en argument // font référence à la même valeur, bool operator !=(iterator, iterator) const; // compare si l'itérateur courant et l'itérateur passé en argument // ne font pas référence à la même valeur, \\ En ce qui concerne l'opérateur ''*'', il s'agit de l'opération de déréférencement qui va retourner une référence sur la valeur à laquelle l'itérateur fait référence et qui est défini par ''mCurrent''. Le code de cette fonction s'écrit : reference operator*() const { return mCurrent; } \\ Par similitude l'opérateur ''->'' qui retourne un pointeur sur la valeur référencée par l'itérateur va retourner un pointeur sur le champ interne ''mCurrent''. \\ reference operator->() const { return &mCurrent; } \\ \\ Il faut désormais implanter les opérateurs d'incrémentation de l'itérateur (ie. pour passer à la valeur suivante). C'est l'opérateur ''++'' qui a est sélectionné, cependant cet opérateur possède deux syntaxes : (1) ''++it'' qui signifie applique l'opération ''++'' à l'objet ''it'' et retourne une référence à cet objet après que l'opération ''++'' a été effectuée; (2) ''it++'' qui signifie fait une copie de l'objet //copy//, applique l'opération à l'objet ''it'' et retourne l'objet //copy// comme résultat de l'opération. L'opérateur ''operator ++()'' correspond à la première synataxe, l'opérateur ''operator ++(int)'' correspond à la seconde syntaxe. Ce qui se traduit par : iterator& operator++() { // Passe à la valeur suivant si nous ne sommes pas // déjà à la fin de l'interval. if(mCurrent <= mInterval->maxValue) mCurrent ++; return *this; } iterator operator++(int) { interval_iterator it(*this); // Crée une copie de l'itérateur. ++(*this); // Incrément l'itérateur courant en appellant // l'opérateur iterator& operator() return it; // Retourne la copie de l'itérateur (avant modification). } \\ Il ne reste plus qu'à implanter les opérateurs relatifs à la comparaison. Deux itérateurs sont égaux s'ils font références à la même valeur située dans le même containeur. Dans ce cas, nous devons avoir les champs ''mCurrent'' et ''mInterval'' qui doivent être égaux. bool operator ==(const interval_iterator& anotherIterator) const { return mCurrent == anotherIterator.mCurrent && *mInterval == *anotherIterator.mInterval; } bool operator !=(const interval_iterator& anotherIterator) const { return mCurrent != anotherIterator.mCurrent || *mInterval != *anotherIterator.mInterval; } - Enfin, l'itérateur doit aussi être [[https://en.cppreference.com/w/cpp/named_req/CopyConstructible|constructible par recopie]], [[https://en.cppreference.com/w/cpp/named_req/CopyAssignable|supporter l'affection]] et [[https://en.cppreference.com/w/cpp/named_req/Swappable|supporter les permutations]]), ce qui impose de définir en complément le constructeur de recopie, les fonctions membres ''swap'' et l'opérateur ''='' comme suit: \\ public: // Définition du constructeur de recopie. // Crée un itérateur qui fait référence au même élément que l'itérateur // passé en argument. interval_iterator(const interval_iterator& anotherIterator): mCurrent(anotherIterator.mCurrent), mInterval(anotherIterator.mInterval) {} // Définition de l'opération d'affectation consistant à ce que // l'itérateur courant fait référence au même élément que l'itérateur // passé en argument. interval_iterator& operator=(const interval_iterator& anotherIterator) { mCurrent = anotherIterator.mCurrent; mInterval = anotherIterator.mInterval; return *this; } // Opération de permutation. // A la fin de l'opération, // - anotherIterator fait référence à l'élément // qui était référencé par l'itérateur courant avant l'opération, // - l'itérateur courant fait référence à l'élément // qui était référencé par l'itérateur anotherIterator avant l'opération, void swap(interval_iterator& anotherIterator) { std::swap(mCurrent, anotherIterator.mCurrent); std::swap(mInterval, anotherIterator.mInterval); } \\ Et normalement l'ensemble des éléments ont été définis pour à la classe ''interval_iterator'' pour que ce dernier puisse répondre aux exigences auxquelles un itérateur de type [[https://en.cppreference.com/w/cpp/named_req/ForwardIterator|forward iterator]] doit répondre. ===== Question 2.0 ===== Tester le bon fonctionnement de classe avec le code suivant : #include"interval.hpp" #include #include #include template void print(inputIterator beginIt, inputIterator endIt) { if(beginIt == endIt) { std::cout << "[]" << std::endl; return; } for(;;) { std::cout << *beginIt; beginIt++; if(beginIt == endIt) break; std::cout << ", "; } std::cout << "]" << std::endl; return; } void testInterval() { interval inter(5, 15); std::cout << "Contenu de l'interval : "; print(inter.begin(), inter.end()); // Recherche du plus grand élément. auto maxIt = max_element(inter.begin(), inter.end()); std::cout << "Element maximal de la séquence: " << *maxIt << std::endl; // Duplication des valeurs dans un vecteur std::vector vec(inter.begin(), inter.end()); std::cout << "Contenu du vecteur : "; print(vec.begin(), vec.end()); } int main() { testInterval(); return 0; } * La fonction ''print'' prend une séquence d'éléments définie par un itérateur de début ''beginIt'' et un itérateur marquant la fin de la séquence ''endIt'' et affiche cette séquence sur la console. La seule particularité, c'est qu'en fonction de la position de l'élément, le séparateur "," est placé entre les valeurs ou non. * Dans le cas de la fonction ''testInterval()'', le code interval inter(5, 15); crée un interval allant de 5 à 15. Nous appelons la fonction ''print'' en passant l'itérateur référençant la première valeur contenue dans l'interval ainsi que l'itérateur marquant la fin de la séquence et nous vérifions que la fonction ''print'' peut bien afficher les valeurs contenues dans l'interval. print(inter.begin(), inter.end()); . Nous vérifions en utilisant une fonction [[https://en.cppreference.com/w/cpp/algorithm/max_element|max_element]] de la bibliothèque standard qui recherche le plus grand élément d'une séquence que notre containeur fonctionne aussi avec des fonctions de la bibliothèque standard. auto maxIt = max_element(inter.begin(), inter.end()); std::cout << "Element maximal de la séquence: " << *maxIt << std::endl; Nous affichons l'élément retourné qui est bien entendu la borne supérieure de l'interval. Enfin, nous créons un vecteur auquel nous affectons l'ensemble des valeurs contenues dans l'interval ''inter''. Et nous vérifions que notre fonction ''print'' fonctionne aussi avec un containeur de type ''std::vector''. // Duplication des valeurs dans un vecteur std::vector vec(inter.begin(), inter.end()); std::cout << "Contenu du vecteur : "; print(vec.begin(), vec.end());