Discussion :

[camboui]

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 ?

[3DArchi]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[loufoque]

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

[camboui]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

[koala01]

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

[camboui]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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
}

[koala01]

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

[camboui]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

[3DArchi]

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é.

[koala01]

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

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

[3DArchi]

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)...

[koala01]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

   Sélectionner tout - Visualiser dans une fenêtre à part

   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

[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?

[koala01]

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

[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 ?

[camboui]

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
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.

[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 Tout ce que je te souhaite c'est une bonne dose de café pour la validation (la conception devant déjà être faite) ...

[camboui]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[camboui]

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 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à

[koala01]

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

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