Comment implémenter une class iterator dans un Deque

Version imprimable

06/05/2019, 19h33
Flexxi

1 pièce(s) jointe(s)

Comment implémenter une class iterator dans un Deque

Bonjour :)
J'essaye actuellement d'implementer moi-même un Deque (à mon niveau, avec une simple structure et une class) Cependant je bloque au niveau des itérator, j'aimerais les definir aussi moi-même (une simple class) mais je ne sais pas comment ils sont implémentés (le peu de code que j'ai pu trouver (STL) est incompréhensible pour moi)
Alors j'ai fait ça, j'aimerais avoir votre avis là-dessus.
Car avec un simple pointeur comme j'ai pu le faire je n'arrive pas à implémenter les opérator ++ -- etc..

Pièce jointe 472572

Je voulais donc votre avis, vos idées, savoir si je peux implémenter mon iterator de cette facon avec 1 seul pointeur ou si je me trompe complètement et qu'il manque des choses dans ma class

Merci d'avance :)

Salut,

Pourrais tu, au lieu de nous fournir une impression écran de ton code, nous le fournir sous la forme d'un copier / coller, en utilisant la balise [ CODE ] ... le code [ / CODE ] (sans tous les espaces entre les crochets), que tu obtiendras en cliquant sur le bouton # qui se trouve au dessus, à droite de la zone d'édition :question:

Cela nous simplifierait énormément la vie, car nous pourrions alors faire nous aussi un copier collé dans notre éditeur de texte préféré, et lancer la compilation afin de voir les éventuels problèmes qui n'apparaissent peut-être pas forcément à première vue ;)

Ceci étant dit, un itérateur est une classe qui présentera une "certaine interface", typiquement, dans le cas d'un deque, composée

d'un opérateur ++ permettant de passer à "l'élément suivant"
d'un opérateur -- permettant de passer à "l'élément précédant"
d'un opérateur == permettant de comparer deux itérateurs (pour savoir s'ils donnent accès au même élément)
d'un opérateur != permettant de comparer deuxitérateurs (pour savoir s'ils donnent accès à des éléments différents)
d'un opérateur *, qui permet de récupérer l'élément itéré sous la forme de T & value = *iterateur;, modulo la constance imposée ou non
d'un opérateur ->, qui permet de récupérer l'élément itéré sous la forme de iterateur->someMember;, modulo la constance imposée ou non

Et dont le but est de cacher à l'utilisateur (de ta deque, en l'occurrence) la structure interne que la collection (ta deque) utilise pour représenter les différents éléments qu'elle contient; le tout en... utilisant justement la même structure interne (mais cachée à l'utilisateur) que ta collection.

Je ne vais pas te fournir le code "tout fait", car ce serait trop facile, mais, en gros, tu devrais définir une classe (imbriquée, dans l'accessibilité publique) qui serait proche de
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Iterator{ public: Iterator operator++(){ /* renvoi un itérateur sur l'élément suivant */ } Iterator operator--(){ /* renvoi un itérateur sur l'élément précédant */ } bool operator == (Iterator const & other) const{ /* renvoi true si les deux itérateur donnent accès au meme élément */ } bool operator != (Iterator const & other) const{ return ! *this==other; } T & operator *(){ /* Renvoie une référence sur la donnée de type T */ } T * operator ->(){ renvoie un pointeur sur la donnée de type T } protected: friend class Deque<T>; // seule la classe Deque et la classe Iterator sont en mesure de créer un nouvel itérateur Deque(Node<T> * node = nullptr):node_{node}{ } private: Node * node_; }
Et, par la suite, tu pourras alors ajouter à ta classe Deque une fonction begin(), qui renvoie un itérateur sur le premier élément de la liste, et une fonction end() qui renvoie un itérateur sur ... ce qui suit le dernier élément de la liste (typiquement : sur nullptr) ;)

07/05/2019, 15h14
Flexxi

Merci pour ta réponse, je vais essayer de modifier ma classe et la poster :)
J'ai pu comprendre l'idée des itérators, cependant je pense me tromper sur ses attributs, car c'est pour moi un simple pointeur qui pointe vers l’élément d'une cellule non? :?
Je peux donc pas avoir d'accès aux autres cellules, est ce que sans me donner le code tu aurais une idée de ce qu'il contient en terme d'attribut ? Ou des informations qui pourrait me donner une idée de sa structure
Car les informations que j'ai pu avoir sont trop complexe pour moi et traitent d'allocators (chose que je ne connais pas car j'essaye de faire ça modestement avec mon niveau) :)
07/05/2019, 15h24
Bousk

Un itérateur c'est un genre de pointeur vers un élément de la collection.
Mais son intérêt est surtout de pouvoir passer d'un élément à l'autre.
Sinon ça s'appelle un pointeur ou une référence, et on se serait pas embêté à créer les itérateurs.
07/05/2019, 15h51
Flexxi

Je devrais donc avoir un pointeur qui pointe sur un Noeud ?
07/05/2019, 17h27
dalfab
Citation:

Envoyé par Flexxi

Je devrais donc avoir un pointeur qui pointe sur un Noeud ?

Oui. L'itérateur contient bien un pointeur sur un Noeud.
D'où incrémenter l'itérateur revient tout simplement à incrémenter ce pointeur.
Par contre déréférencer l'itérateur, revient à accéder à element
Code:

1 2 3 T& operator*()const { return noeud_courant->element; }

Merci ! J'ai pu résoudre quelques problèmes ! :)

Cependant j'ai encore quelques questions de compréhension :
*Pourquoi les opérateurs doivent retourner (iterator&) ?
Courant étant un pointeur vers un Noeud, ce n'est pas correct de faire comme ceci ?
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 const T& operator*() const{ return courant->element; } operator++() { if(courant->suivant!=nullptr)courant=courant->suivant; } operator--() { if(courant->prec!=nullptr)courant=courant->prec; } bool operator==(const iterator& x) const { return courant== x.courant; } bool operator!=(const iterator& x) const { return courant!= x.courant; } operator+=(const int &x) { if(x>0){ for(int tmp=0; tmp<x && courant->suivant!=nullptr; tmp++){ courant=courant->suivant; } }else{ for(int tmp=0; tmp<x && courant->prec!=nullptr; tmp++){ courant=courant->prec; } } }
*Je me suis amusé pour les implémenter à tester de moi-même et voir ce qu'ils donnaient comme resultat, par contre lorsque je fais sortir mon itérateurs du deque (le vrai de la STL) il m'affiche des données que je ne comprends pas
Par exemple sur ce code :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include<deque> #include <iostream> using namespace std; int main() { deque<int> d(5,9999); //Une deque de 5 éléments valant 9999 deque<int>::iterator it; //Un itérateur sur une deque d'entiers //AFFICHAGE for(it = d.begin(); it!=d.end(); ++it) { cout << *it << " - " ; } //DEPLACEMENT DE L'ITERATEUR A 42 it = d.begin(); it+=42; cout << *it << " - " ; return 0; }
La sortie affichée sera "9999 - 9999 - 9999 - 9999 - 9999 - 1886404956"

Encore merci :)

Héhé... il y a juste une petite erreur (mais aux très grandes conséquences) dans ton implémentation de operator ++...

Ce n'est pas
Code:

1 2 3 4 iterator operator++() { if(courant->suivant!=nullptr) courant=courant->suivant; }
que tu dois faire, car cela implique que, l'itérateur n'est pas mis à jour s'il n'y a plus d'éléments suivant (et donc, que l'itérateur courant ne sera jamais égal à celui renvoyé par end() ), mais bien
Code:

1 2 3 4 iterator operator++() { if(courant) // correspond trait pour trait à if(courant != nullptr), car nullptr est implicitement convertible en false ;) courant=courant->suivant; }
En outre, il existe une exclamation en Xtrem Programming qui dit

Citation:

DRY

et qui signifie Don't Repeat Yourself (autrement dit : ne vous répétez pas :D).

Cette exclamation essaye de te convaincre de l'intérêt de baser le fonctionnement des fonctionnalités "fort proches des autres" (comme l'opérateur de comparaison != qui n'est que l'inverse de l'opérateur == ou l'opérateur += qui n'est qu'une succession d'utilisations de l'opérateur ++) sur le fonctionnement des fonctionnalités déjà implémentées.

L'idée qui se cache derrière ce conseil, c'est que cela va te permettre de découvrir plus facilement l'endroit où se logent les éventuelles erreurs et surtout de n'avoir à chaque fois qu'un seul point du code à corriger.

Car, soyons clairs : tu as -- très certainement -- commencé par implémenter l'opérateur == (ou l'opérateur ++), puis, quand tu as voulu implémenter l'opérateur != (ou l'opérateur +=), tu auras sans doute décidé de... faire un copier coller du premier dans le deuxième, avant d'en adapter la logique. Me trompes-je :question:

Du coup, si tu as fais une erreur de logique dans la partie de logique qui n'est pas adaptée du premier opérateur dont tu as fourni l'implémentation, elle va se retrouver ... à deux endroits différents :aie:

La meilleure preuve en est que l'erreur de logique que j'ai mise en avant pour l'opérateur ++ se retrouve non pas une fois (ce qui serait déjà une fois de trop), mais ... deux fois dans l'opérateur += :mur::zekill::zekill:

Du coup, tu vas corriger l'opéateur ++, mais tu ne vas surement pas te dire que "tiens, mais j'ai utilisé une logique similaire dans l'opérateur += ...", si bien que l'opérateur ++ va fonctionner correctement, mais que, quand tu vas faire un test avec un code it+=0; tu auras de nouveau le même problème, que tu devras corriger, sans forcément penser que la logique reste la même dans la branche "vrai" du test if(x>0) si bien que, quand tu feras un test avec it+=15;, tu te retrouveras une troisième fois avec le même problème :aie:

Avoue que c'est pas cool, exprimé sous cette forme ;)

De plus, j'ai fait quelques erreur au niveau de l'interface de base d'une classe (imbriquée) représentant un itérateur. La forme correcte devrait d'avantage ressembler à
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class Iterator{ public: friend Iterator& operator++( Iterator & i){ // pre increment /* incrémenter i et le renvoyer */ } friend Iterator& operator--(Iterator & i){ // pre decrement /* décrémenter i et le renvoyer */ } friend Iterator operator++( Iterator & i, int){ // post increment /* créer une copie de i, incrémenter cette copie et la renvoyer */ } friend Iterator operator--(Iterator & i, int){ // post decrement /* créer une copie de i, décrémenter cette copie et la renvoyer */ } bool operator == (Iterator const & other) const{ /* renvoi true si les deux itérateur donnent accès au meme élément */ } bool operator != (Iterator const & other) const{ return ! *this==other; } T & operator *(){ /* Renvoie une référence sur la donnée de type T */ } T * operator ->(){ renvoie un pointeur sur la donnée de type T } protected: friend class Deque<T>; // seule la classe Deque et la classe Iterator sont en mesure de créer un nouvel itérateur Deque(Node<T> * node = nullptr):node_{node}{ } /* Incrémentation et décrémentation des iterateurs */ void increment(){ /* passer à l'élément suivant */ } void decrement(){ /* passer à l'élément précédant */ } private: Node * node_; }
(le fait de déclarer friend les opérateurs de pré et de post incrémentation/décrémentation en fait de facto des fonctions libres ;) )

Au final, tu devrais donc fournir la logique que l'on a vue dans operator++ et [c]opertor--[c] dans les fonction increment et decrement, sous une forme proche de
Code:

1 2 3 4 5 6 7 8 void increment(){ if(courant) courant = courant->suivant; } void decrement(){ if(courant) courant = courant->precedent; }
les opérateurs de pré incrémentation et pré décrémentations pourront alors prendre une forme "toute simple de
Code:

1 2 3 4 5 6 7 8 9 /* je présente la version longue pour que la logique apparaisse clairement ;) */ Iterator & operator ++(Iterator & i){ i.increment(); return i; } Iterator & operator ++(Iterator & i, int){ i.decrement(); return i; }
et les opérateur de post incrementation prendront la forme de
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 /* toujours avec la version longue :d */Iterator operator ++(Iterator & i, int){ Iterator copy{i}; return ++copy; /* OU OU OU copy.increment(); return copy; */ } Iterator & operator ++(Iterator const & i, int){ Iterator copy{i}; return --copy; /* OU OU OU copy.decrement(); return copy; */ }
Quant à l'opérateur de comparaison !=, il doit renvoyer vrai si l'opérateur == renvoie faux et inversement. Faisons donc les choses le plus simplement possible, car ! true == falseet ! false == true, si bien que l'on peut parfaitement utiliser l'opérateur == dans l'opérateur !=, ce qui évite les copies de code inutiles ;).

L'opérateur != pourra donc prendre la forme "toute simple" de
Code:

1 2 3 bool operator != (Iterator const & other) const{ return ! (*this == other); }
Enfin, pour ce qui concerne les opérateurs += et -=, il faut déjà savoir que leur présence n'est clairement pas obligatoire, car on s'attend, a priori, à ce que ces opérateurs présentent une complexité algorithmique dite "en temps constant" (symbolisée par une complexite en O(1) ), alors que la structure interne de ton deque fait qu'ils vont présenter une complexité algorithmique dite "proportionnelle" (symbolisée par une complexité en O(N) ) vu que le temps nécessaire à passer au Nième élément suivant (ou précédant) dépend du nombre d'éléments qu'il faut parcourir pour y arriver.

Enfin soit, comme leur présence ne posera pas de problème vraiment plus grave que des performances moindres que celles auxquelles on s'attendait, je ne vois pas vraiment d'objection à ce qu'ils soient implémentés (il serait cependant très intéressant d'indiquer le problème en lettres de feu dans la documentation :D ).

Ces opérateurs feront un usage particulièrement utile des opérateurs de pré incrémentation (pour ce qui est de l'opérateur +=) et de pré décrémentation (pour ce qui est de l'opérateur -= ), car on pourrait les définir sous une forme proche de
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 Iterator & operator+=(size_t count){ /* l'utilisateur est un imbécile distrait : il n'y a aucun sens à avoir un code it+= -1 */ assert(count>=0 && " only positive value are accepted"); /* l'utilisateur est un imbécile distrait : il n'y a aucun sens à avoir un code it+= 0 */ assert(count > 0 && "no sens to use it+=0"); /* nous pourrions même aller plus loin et obliger l'utilisateur à utiliser l'incrémentation * quand il veut passer au suivant assert(count >1 && "why don't y make use of the ++ operator?"); */ /* on va travailler sur une copie par sécurité */ Iterator copy{*this}; for(int c=0; c<count;++c){ /* l'utilisateur est un imbécile distrait, qui peut vouloir passer au 10 eme élément suivant alors qu'il n'y en a que 9 */ assert(copy.courant && "No more next element"); ++copy; } /* si on arrive ici, copy correspond à un élément valide (ou, au pire, à l'élément renvoyé par end() ) */ courant = copy.courant; return *this; } /* Le principe reste exactement le même pour l'opérateur -=... à ceci près qu'on décrémente l'itérateur au lieu de l'incrémenter * Les même causes ayant les mêmes effet, je ne m'amuserai pas à copier les commentaires :D */ terator & operator+=(size_t count){ assert(count>=0 && " only positive value are accepted"); assert(count > 0 && "no sens to use it-=0"); /* assert(count >1 && "why don't y make use of the -- operator?"); */ Iterator copy{*this}; for(int c=0; c<count;++c){ assert(copy.courant && "No more previous element"); --copy; } courant = copy.courant; return *this; }
Alors, tu vas sans doute me demander quel avantage il y a à travailler de la sorte, et d'utiliser les fonctionnalités qui existent déjà.

Hé bien, la réponse est toute simple : c'est que, quand tu vas faire tes tests (de préférence, en créant des tests unitaires), si erreur il y a dans ta logique, elle apparaîtra forcément dans le test associé à une fonctionnalité particulière, à moins, bien sur, que l'erreur n'apparaisse dans une fonctionnalité "réutilisée".

Par exemple, si ton opérateur == pose problème c'est un test sur l'opérateur == qui va foirer, et, accessoirement, certains tests sur l'opérateur != .

Mais, si tous les tests sur l'opérateur == passent sans problème, et qu'un test sur l'opérateur != venait à foirer, tu saurais que tu n'as pas à t'inquiéter de l'opérateur ==, qui lui, fonctionne parfaitement (dans la mesure dans où tu le testes suffisamment, bien sur), et que c'est donc au niveau de l'opérateur != que tu dois aller voir "ce qui ne va pas".

De la même manière, si tu testes suffisamment les opérateurs de pré incrémentation et de pré décrémentation, et que tous les tests réussissent évidemment, si un test de l'opérateur de post incrémentation (ou de post décrémentation) foire, tu sais que tu n'as pas à t'inquiéter de l'opérateur de pré incrémentation (ou de pré décrémentation).

Par contre, si tu as effectivement fait une erreur au niveau de la pré incrémentation (par exemple), ce devrait être une bonne partie des tests de post incrémentation et de l'opérateur += qui risquent effectivement de foirer :aie:

Mais cette augmentation de "tests foireux" sera -- justement -- l'indication que c'est l'une des fonctionnalités les plus "basiques" que tu as mise au point qui pose problème ;)