Ecrire un iterator

J'ai essayé d'écrire un iterator afin de l'utiliser avec les <algorithm>s. Mais il y a des petits soucis lorsque les algos appellent implicitement std::advance() ou std::distance(), entre autres.
J'ai donc un peu farfouillé les sources de VC6 puis VS2005, mais l'approche semble différente, difficile donc de faire du code compatible/portable. L'approche est d'ailleurs un peu lourdingue: il faut hériter son iterator de certaines classes de base (ranit par exemple). Oui mais lesquelles, et est-ce standard ?

Vendredi soir donc une réponse rapide :
Tu peux regarder ici, c'est expliqué.
Exemple :

Code:

---

1 2 3 4 5 6

template<class T> class CMonIterateur :public std::iterator<std::input_iterator_tag,T> { // .. blabla };

---

Sinon, boost.Iterator fournit des classes pour t'aider à construire tes propres itérateurs.

Boost propose Iterator Facade, qui rend l'écriture d'itérateurs plus facile.

3Darchi, merci, ça marche très bien !

J'ai écrit un iterator permettant d'accéder à des données sur disque (un fichier, ça aurait pu être un pipe ou autre). Les données ne sont donc pas en mémoire dans un conteneur quelconque.
Lors du déréférencement via l'operator*() je renvois un smart pointer (par valeur). En général l'operator*() renvoit une référence sur un objet conservé dans un conteneur, donc quelque part en mémoire, ce qui n'a pas de sens dans mon cas. J'ai donc un truc comme ceci:

Code:

---

1 2 3 4 5 6 7 8 9

class iterator: public std::iterator<std::random_access_iterator_tag,smart_ptr<T> > { ... public: smart_ptr<T> operator*() const {...} ... };

---

Je me demande s'il y a des règles à respecter pour l'écriture d'un iterator. Ici par exemple, j'ai dérogé aux "habitudes" de la stl en écrivant value_type operator*() const au lieu de reference operator*() const, mais je n'avais pas le choix. Est-ce grave docteur ?

Salut,

Sauf erreur, tu as un smart pointer qui se "balade quelque part en mémoire", qui est accessible et qui manipule les données de ton fichier...

Or il est (toujours sauf erreur) tout à fait possible de... renvoyer une référence sur smart pointer.

Dés lors, pourquoi déroger à la règle, et risquer des problèmes :question:

Citation:

---

Envoyé par koala01

Sauf erreur, tu as un smart pointer qui se "balade quelque part en mémoire", qui est accessible et qui manipule les données de ton fichier...

---

Comment puis-je renvoyer une référence sur un objet local ? Car bien sûr le smart pointer est créé dans la fonction operator*(). Conceptuellement le code est comme ceci:

Code:

---

1 2 3 4 5 6 7 8

smart_ptr<T> operator*() { create buffer for T; read from file into buffer; declare a local smart pointer and assign the buffer to it; return the smart pointer; //let die the buffer with the smart pointer anywhere else, but here }

---

Mais, en toute logique, l'itérateur te permet "uniquement" d'accéder aux différents éléments d'une collection...

Or, pour lire ton fichier (car c'est quand même de cela qu'il s'agit), tu dois l'ouvrir et créer un buffer qui contient (tout ou partie) de ce fichier.

L'itérateur devrait donc te permettre d'accéder... au contenu du buffer, et non au buffer lui-même...

Cela implique donc qu'il te faut une classe qui soit responsable... de la gestion du buffer, et que ton itérateur renvoie... une référence sur l'élément du buffer qui t'intéresse ;)

Ah ben non.
La popote de l'itérateur c'est d'itérer sur une collection. Or la collection ne se trouve pas en mémoire, rien du tout, nada. Et pour cause puisqu'elle est dans un fichier (disons de 387 TerraBytes). L'itérateur ignore l'implémentation de l'accès au fichier, et il n'a pas à la connaitre. Il sait juste qu'il peut faire une lecture dans un fichier à une position donnée en fournissant un buffer et sa taille (seek and read).
Il n'emprunte pas de buffer au fichier, mais il demande au fichier de lui remplir un buffer créé localement. Tous les stream fonctionnent ainsi il me semble:

Code:

---

1 2	int i; cin >> i;//i is a local buffer, it is not provided by cin

---

En bref, l'itérateur n'a conceptuellement que deux membres, un nombre représentant un "seek" dans le fichier (sur lequel s'opère les opérations d'itérations "habituelles" ++, +, +=, ==, !=, etc) et, pour faire simple, un pointeur vers un objet de type GenericRandomAccesFile dont la seule méthode qui lui est utile serait bool ReadFromFile(unsigned atposition, void *buffer, unsigned buffersize).

Bon, ok, supposons que la classe d'accès au fichier gère un buffer et le renvoit par référence à l'itérateur. Comment cette classe fait-elle pour savoir que le buffer n'est plus utilisé nulle part afin de pouvoir le réutiliser lors d'un accès ultérieur au fichier ?

J'aurais tendance à appuyer en ton sens et dire que le buffer est dans l'itérateur; mais plutôt qu'en variable locale, en membre puisqu'il contient les données couramment lues - ce qui évite aussi de les relire plusieurs fois si l'itérateur est déréférencé plusieurs fois de suite sans être incrémenté.

Mais c'est justement parce que l'itérateur n'a pas à connaitre l'implémentation de la collection qu'il gère qu'il faut avoir une classe qui se charge de cette collection...

Quand on y réfléchit, une définition "simple" (mais pourtant correcte) d'un itérateur est

Citation:

---

un objet permettant de parcourir différents éléments d'une collection de données

---

Cela doit t'inciter à te poser la question de ce qu'est la collection et de ce que sont les données ;)

Mettons que tu aies un fichier binaire, et que tes données considérées comme "atomiques" soient composées de 50 bytes (arbitrairement choisis pour l'exemple)...

Tu ne peux effectivement pas choisir de charger les Tbyte en mémoire, et je le comprends parfaitement... Mais, tu peux choisir de charger, mettons, 1000 (ou... un nombre qui te semble adéquat de) données atomiques, soit, l'équivalent de 1000*50 bytes dans... un buffer, qui sera ta collection de données

Et ce sera la tache de ce buffer d'aller chercher les 50.000 bytes qui l'intéressent dans le fichier ;)

Tout ce qu'il faut, c'est être en mesure de lui dire "charge la Nieme partie du fichier" (ou N correspond à la partie du fichier qui t'intéresse et ne dépasse pas le quotient de la taille totale du fichier par 50.000 bytes, selon l'exemple)

Lorsque tu donnes cette instruction à ton buffer, ce qu'il fait, c'est:
ouvrir le fichier,

• se positionner à la bonne place pour lire les informations qui t'intéressent (peek)
• lire (édit: en fait les récupérer) les 50.000 bytes qui suivent
• fermer le fichier

et tu te retrouve au final avec une collection de... 1000 données atomiques auxquelles ton itérateur te donne accès ;)

Je suis plus sceptique quand à ça. Il me semble, pour prendre un exemple, que l'itérateur de vector dans l'implémentation de Visual possède en membre un pointeur sur la zone des données du vecteur. Donc il sait très bien comment est implémenté un vecteur... Et ça ne me choque pas. Un itérateur 'générique' n'existe pas. Il est toujours lié à un conteneur: std::list<A>::iterator, ...
Un itérateur est instancié relativement à un conteneur, donc c'est normal qu'il sache à quel conteneur il est relié.

[EDIT] et concernant son problème, son itérateur peut très bien lire les données qu'au fur et à mesure que l'itérateur est incrémenté. Ca présente quand même de gros avantage de type de chose (comme éviter de tout lire si on ne va pas aller jusqu'au bout)...

Bien sur que l'itérateur est sensé s'adapter à la collection...

C'est bien pour cela que tu dois passer par vector<type> pour en profiter ;)

Mais, dans le cas qui nous intéresse, la collection n'est qu'une partie du fichier (quil est préférable de ne pas devoir relire "à chaque fois", et dont on peut estimer intéressant de ne pas garder le fichier ouvert en permanence).

C'est pour cela qu'il faut passer par un "buffer" "mémoire" et non fichier.

A l'extrême limite, ce buffer serait implémenté sous une forme (simplifée) 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 38

/* La structure de 50 bytes */ struct Data { char[50] values; }; class Buffer { public: class Myiterator :public iterator <RandomAccessIterator, Data> { Data *p; public: myiterator(Data* x) :p(x) {} myiterator(const myiterator& mit) : p(mit.p) {} myiterator& operator++() {++p;return *this;} myiterator& operator++(int) {p++;return *this;} bool operator==(const myiterator& rhs) {return p==rhs.p;} bool operator!=(const myiterator& rhs) {return p!=rhs.p;} Data& operator*() {return *p;} }; myiterator begin(){return buf[0]} myiterator end(){return buf[lastutil+1];} void readSection(size_t sectionNumber) { if(sectionNumber!=section) // on ne lit la section que si ce n'est // pas celle qu'on a déjà lue avant { std::ifstream ifs(/* ouverture du ficher "classique" */); /* on se place sur la bonne section et on lit */ } } private: Data buf[1000]; size_t lastutil; // pour le cas où on n'a pas su lire les 1000 données size_t section; // pour savoir quelle section a été lue std::string filename; // pour pouvoir ouvrir le fichier   };

---

Au final, la logique à suivre pour en profiter est:

1. déclarer le buffer
2. demander la lecture d'une section
3. utiliser l'itérateur sous la forme de
   Code:

   ---

   Buffer::iterator it = mybuf.begin()

   ---

   pour parcourir cette section
4. retour au [2]

Ajoute la gestion d'erreurs, la défaut initialisation et quelques fonctions qui iront bien à tout cela, et tu obtiens quelque chose de parfaitement viable ;)

Ce que tu proposes est un itérateur sur un buffer alors que si j'ai bien compris ce qu'il veut c'est un itérateur sur un fichier. Cet itérateur lit le fichier bloc par bloc et renvoi le bloc lu. D'où le besoin d'avoir dans son itérateur : le fichier, une position courante, et le buffer du bloc lu. Cet itérateur pourrait être rattaché à une classe 'LecteurFichierParBloc' qui jouerait le rôle du conteneur. Non?

Cela pourrait se faire, mais implique une autre restriction dont il faut tenir compte:

Si tu en arrive à obtenir un fichier de plusieurs terabyte (mais on pourrait déjà dire pareil pour quelques centaines de megabytes ;)) qui est encore en cours d'utilisation (que d'autres applications utilisent éventuellement pour écrire dedans), tu ne peux pas te permettre de garder ce fichier ouvert (donc indisponible pour l'écriture) tout le temps que nécessitera ton traitement...

Il faut donc accepter l'idée de le "tronçonner" en partie suffisamment petites pour qu'elles "tiennent en mémoire" et suffisamment grandes pour qu'on puisse accéder à toutes les partie, et donc de travailler sur un buffer mémoire, pour ne pas rendre ce fichier indisponible pendant la semaine que durera le traitement :P;)

Koala, non, ce n'est pas du tout ce que je cherche. L'implémentation de l'accès au fichier n'est pas du ressort de l'itérateur. Le fichier est à voir comme une collection en entier. Toutes les optimizations éventuelles pour y accéder ainsi que les problèmes de simultanéité sont faites en ailleurs. Et heureusement.

Dans ta proposition je ne vois qu'un cache d'accès au fichier, pas un itérateur.
Comment te positionnes-tu sur le tout premier élément avec begin(), comment te positionnes-tu juste derrière le dernier élément avec end() ? Comment fais-tu l'appel std::lower_bound(v.begin(),v.end(),v) par exemple ?

Citation:

---

Envoyé par 3DArchi

Ce que tu proposes est un itérateur sur un buffer alors que si j'ai bien compris ce qu'il veut c'est un itérateur sur un fichier. Cet itérateur lit le fichier bloc par bloc et renvoi le bloc lu. D'où le besoin d'avoir dans son itérateur : le fichier, une position courante, et le buffer du bloc lu. Cet itérateur pourrait être rattaché à une classe 'LecteurFichierParBloc' qui jouerait le rôle du conteneur. Non?

---

C'est parfaitement ça, tu as tout compris :D
Ainsi le "fichier" n'est réellement "lu" que lors du déréférencement, jamais à aucun autre moment. Et encore, je mets "fichier" et "lu" entre guillement car c'est ce qu'on pourrait croire. En réalité il y a une gestion optimisée implicite et automatique de l'accès au fichier (ouverture, fermeture, cache, etc). Dans son concept, koala suppose déjà que le fichier est mal géré... Si c'était le cas, ce n'est pas en écrivant l'itérateur qu'il faudrait s'en soucier.

Là où j'ai les même sueurs que Koala, c'est le risque à gérer le fichier associé à l'itérateur... Mais, bon, on ne connait pas ton projet en entier :mrgreen: Tout ce que je te souhaite c'est une bonne dose de café pour la validation (la conception devant déjà être faite) ...

Citation:

---

Envoyé par 3DArchi

D'où le besoin d'avoir dans son itérateur : le fichier, une position courante, et le buffer du bloc lu.

---

J'épingle ce petit extrait de 3DArchi car c'est là que se situe la "difficulté". Contrairement aux conteneurs classiques de la stl où tout est en mémoire, ici rien n'est en mémoire. Il est ainsi difficile de retourner par référence un élément du conteneur ne se trouvant pas vraiment en mémoire.

J'avais donc choisi d'en faire une copie locale en mémoire et de le retourner via un smart pointer par valeur. Mais l'idée de 3Darchi n'est pas mauvaise, càd d'attacher le smart pointer à l'itérateur afin de pouvoir le retourner par référence.

En fait les deux sont possibles, tout dépend si on accède au conteneur en lecture uniquement, ou en lecture et en écriture. Dans le premier cas le retour par valeur est suffisant et aucunement contraignant me semble-t-il (on n'utilise que la valeur "à droite"). Dans le second cas la solution de 3Darchi s'impose car le déréférencement doit pouvoir permettre la modification du conteneur (valeur "à gauche").
A ce propos, il me vient une autre question: comment savoir au sein de l'opérateur si le déréférencement est utilisé "à droite" ou "à gauche" ?

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class iterator: public std::iterator<std::random_access_iterator_tag,T > { ... public: T & operator*() {//ici, comment savoir si je suis à gauche ou à droite ? ... } ... };   *T_it = V;//à gauche V = *T_it;//à droite

---

Citation:

---

Envoyé par 3DArchi

Là où j'ai les même sueurs que Koala, c'est le risque à gérer le fichier associé à l'itérateur... Mais, bon, on ne connait pas ton projet en entier :mrgreen: Tout ce que je te souhaite c'est une bonne dose de café pour la validation (la conception devant déjà être faite) ...

---

Ça tourne depuis quelques jours.
Mais j'avais un soucis de compatibilité avec les std::advance() et autre std::distance() enfoui dans les <algorithm>, raison pour laquelle j'avais ouvert ce thread. L'héritage de std::iterator<> fut la solution ;)
Et... euh.. à propos de "conception", "validation", "analyse", "diagramme", "flux"... euh... ça fait tellement longtemps que je ne les ai plus entendu prononcer ces mots-là :oops::roll::aie:

Mais un fichier n'est, à la base, qu'une succession "sans queue ni tête" de bits (ou plutôt de bytes)

Pour pouvoir manipuler ces bytes, il faudra, de toutes manières, à un moment donner indiquer le contexte dans lequel ils doivent l'être.

De plus, selon le mode d'ouverture du fichier, tu ne peux pas forcément répercuter directement les éventuelles modifications apportées au données.

Tout cela pour te faire comprendre qu'il faudra bien à un moment donné (si tu ne veux pas commencer à chipoter uniquement avec des valeurs hexadécimales) en finir par disposer de ces informations "ailleurs que simplement dans le fichier", c'est à dire, en mémoire, que ce soit sous la forme de simple long long ou sous la forme de structures (éventuellement POD) plus complexes...

Alors, bien sur que tu peux utiliser les itérateurs sur le rdbuf, mais, l'un dans l'autre, cela va impliquer un tas de problèmes qu n'apparaitraient pas si tu passait par un "buffer" en mémoire.

Ne serait-ce que parce que le rdbuf, il doit bien exister quelque part :P

Sans oublier le fait que, comme je l'ai si mal exprimé dans mon message précédent, un fichier de plusieurs tera ne se fait pas en un jour, et que l'on peut donc raisonnablement penser qu'il y a une (ou plusieurs) applications qui se chargent de le remplir (éventuellement depuis différents ordinateurs), et qu'il n'est donc pas forcément opportun de le "verrouiller à l'écriture" pour ces applications le temps que durera le traitement

Pour ma part, je reste persuadé que la seule optique qui soit de nature à aplanir toutes ces restrictions reste de travailler sous la forme d'un buffer "personnalisé".

Au pire, si tu as plusieurs fichiers qui utilisent des types différents, tu peux toujours transformer ton buffer en template ;)

Citation:

---

Envoyé par camboui

Koala, non, ce n'est pas du tout ce que je cherche. L'implémentation de l'accès au fichier n'est pas du ressort de l'itérateur. Le fichier est à voir comme une collection en entier. Toutes les optimizations éventuelles pour y accéder ainsi que les problèmes de simultanéité sont faites en ailleurs. Et heureusement.

Dans ta proposition je ne vois qu'un cache d'accès au fichier, pas un itérateur.
Comment te positionnes-tu sur le tout premier élément avec begin(), comment te positionnes-tu juste derrière le dernier élément avec end() ? Comment fais-tu l'appel std::lower_bound(v.begin(),v.end(),v) par exemple ?

---

Autant pour moi...

Le code pour iterator begin() est plutôt du genre de

Code:

---

1 2 3 4

iterator begin() { return iterator(buf[0]); }

---

et, pour end() proche de

Code:

---

1 2 3 4

iterator end() { return iterator(buf[lastutil+1]); }

---

Citation:

---

Envoyé par camboui

J'épingle ce petit extrait de 3DArchi car c'est là que se situe la "difficulté". Contrairement aux conteneurs classiques de la stl où tout est en mémoire, ici rien n'est en mémoire. Il est ainsi difficile de retourner par référence un élément du conteneur ne se trouvant pas vraiment en mémoire.

---

A mon avis, tu as intérêt à lire les données au premier déréférencement et à les garder dans l'itérateur jusqu'à ce qu'il bouge. Ca évite d'avoir à le relire si tu déréférences plusieurs fois de suite sans le bouger.

Citation:

---

Envoyé par camboui

A ce propos, il me vient une autre question: comment savoir au sein de l'opérateur si le déréférencement est utilisé "à droite" ou "à gauche" ?

---

En général, cela se traduit par que tu va avoir un itérateur à gauche et un const itérateur à droite.

Citation:

---

Envoyé par 3DArchi

En général, cela se traduit par que tu va avoir un itérateur à gauche et un const itérateur à droite.

---

Non, c'est une erreur de le croire...
Si l'itérateur est constant, c'est la version const qui sera utilisée (à droite généralement, la gauche demandant une référence non constante).
Si l'itérateur n'est pas constant, c'est la version non const qui sera utilisée, que ce soit à droite ou à gauche.

Le seul moyen de différencier ça (mais qui a ses problèmes), c'est de faire retourner un proxy à l'opérateur de référencement, puis si on appelle l'opérateur = sur le proxy, c'est qu'on était à gauche, si on appelle l'opétateur de cast en T, c'est qu'on était à droite.


Maintenant, à mon avis, et n'ayant que survolé les discussion, ne rien avoir en mémoire est une bêtise. Je verrais bien une structure fichier, qui maintient en mémoire une liste de buffers vivants (un buffer est vivant si au moins un itérateur pointe sur un élément de son contenu, et éventuellement un peu après pour optimiser). Une façon de gérer ça est la possibilité d'aliaser les shared_ptrs :

Citation:

---

template<class Y> shared_ptr(shared_ptr<Y> const & r, T * p); // never throws

Effects: constructs a shared_ptr that shares ownership with r and stores p.

---

Tu retournes des pointeurs qui pointent sur un élément, mais qui font vivre non pas l'élément lui même, mais le buffer.

Citation:

---

Envoyé par JolyLoic

Non, c'est une erreur de le croire...
Si l'itérateur est constant, c'est la version const qui sera utilisée (à droite généralement, la gauche demandant une référence non constante).
Si l'itérateur n'est pas constant, c'est la version non const qui sera utilisée, que ce soit à droite ou à gauche.

---

Je l'ai probablement mal dit car ça n'a pas été compris comme ça, mais c'est ce que je voulais dire...

En conclusion, il n'y a pas de moyen simple pour savoir si on est à gauche ou à droite. On peut juste supposer que si on à affaire à une valeur à gauche, il y des chances qu'un operator=() soit juste derrière.
Ou operator+=() ou operator-=() ou...

En fait il faut trouver le moyen de savoir si le buffer a été modifié par un déréférencement ou pas. C'est peut-être ce que tu exprimais JolyLoic dans la 2ème partie de ton intervention avec les shared_ptr() mais je n'ai rien compris... :oops:

Je vais situer mon souhait dans son contexte, car, bien sûr, quand je parlais de terrabytes, c'était une manière ironique de dire qu'il n'était pas voulu ou possible de tout charger en mémoire.

J'utilise assez souvent des std::vector (par exemple) qui, après construction et remplissage, sont figés et consultés en lecture seule. Je souhaitais donc tout simplement ne pas modifier le code qui consulte ces std::vector.
Ainsi, à la fin de la phase de construction et remplissage du std::vector, je fais l'équivalent d'un file.write(&*vector.begin(),vector.size()*size(T)).
Reste donc l'autre partie du code que je ne souhaite pas changer, mais pour laquelle il faut créer un conteneur (avec son itérateur ? :mrgreen:) qui doit pouvoir se comporter de manière transparente pour les algorithmes du type std::find, std::find_if, std::lower_bound, std::upper_bound, std::equal_range, etc, des algorithmes de consultation qui ne modifient pas le conteneur (dont le contenu se trouverait désormais ailleurs qu'en mémoire).

D'un point de vue plus générique, on pourrait voir mon souhait comme un exercice de création de conteneurs se comportant de la même manière que ceux de la STL, à ceci près qu'il n'y a pas à supposer que le contenu est effectivement mémoire.
Il n'y a pas de "projet conceptualisé" derrière, mais un outil permettant de continuer à utiliser la STL en ayant des dizaines et des dizaines de conteneurs "actifs" simultanément sans trop se soucier de savoir si les limites de mémoire de la machine sont atteintes.

Comme je le disais, j'ai du code qui fonctionne depuis quelques jours. Le conteneur "simule" un vector sur fichier, et l'iterator associé fonctionne très bien avec les quelques algos déjà cités. Il y a juste le déréférencement de l'iterator qui se fait par valeur et non par référence. Tant que le contenu du conteneur n'a pas à être modifié, c'est sans problème. Peut-être devrais-je appeler l'iterator const_iterator.

Si t'avais utilisé Iterator Facade comme je l'avais recommandé, tu n'aurais pas eu à te poser toutes ces questions.

Citation:

---

Envoyé par camboui

D'un point de vue plus générique, on pourrait voir mon souhait comme un exercice de création de conteneurs se comportant de la même manière que ceux de la STL, à ceci près qu'il n'y a pas à supposer que le contenu est effectivement mémoire.

---

Mmm, ce besoin ressemble énormément à la description de SLXXL (la STL version XXL :D)
Il y a peut être quelques bonnes idées à pécher ?

Désolé Loufoque, ta réponse laconique du 27/2 est passé inaperçue derrière celle de 3Darchi.

Ah ben voilà ! Merci Arzar :D

J'ai trouvé un cas concret pour lequel il vaut mieux retourner une référence plutôt qu'une valeur lors du déréférencement d'un iterator: c'est indispensable si on utilise les std::reverse_iterator.

EDIT: non, pas indispensable finalement. Le 3ème paramètre template permet de spécifier à reverse_iterator ce qu'est "une référence".

EDIT2: ah ben ça dépend du compilateur. Sous VC++6 c'est OK mais pas sous VS2005...