Discussion :

[Kaluza]

Bonjour.

Je suis en train de coder un octree pour un code de maillage adaptatif où j'ai un arbre de classes "AbstractGrid". Chacune de ces "AbstractGrid" contient un pointeur vers sa grille parent et un tableau de pointeurs vers ses grilles filles si elle en a.

Avant de passer à la suite, 2 précisions :
- je connais assez mal les itérateurs, mon utilisation s'étant limitée à faire des boucles sur le contenu de vectors...
- je n'utilise pas boost::graph car j'ai besoin d'optimisations liées à mon octree spécifique pour à terme pouvoir optimiser la gestion de plusieurs centaines de milliards de grilles de façon parallèle en minimisant l'empreinte mémoire

J'aimerai créer des itérateurs persos pour parcourir mon arbre de grilles de plusieurs façons et j'aurai plusieurs questions
1) Existerait-il un tutorial expliquant par l'exemple comment créer des iterateurs pour des conteneurs spéciaux ?
2) J'aurai besoin de parcourir mon arbre de plusieurs façons (par exemple pouvoir itérer sur des plus proches voisins ou pouvoir itérer sur des grilles filles), est-ce que cela signifie que je devrais coder un itérateur associé à chaque façon de me balader dans mon arbre ?
(3) je sens que je vais me faire crier dessus mais ce n'est pas grave: je n'ai jamais bien compris la différence entre des iterator et des const iterator (est-ce juste que le const iterator est un itérateur "en lecture seule" permettant uniquement d'utiliser les méthodes constantes de ce vers quoi il pointe ?))

Merci beaucoup.

[Flob90]

Bonjour,

1/ Dans l'idée, fournir une classe d'itérateur pour un conteneur, c'est juste founir une classe qui respecte les conditions fournit par la norme pour être un itérateur. Prends un draft de la norme, choisi quel genre d'itérateur tu veux faire, et implémentes l'ensemble des fonctions indiqués.

NB: Si tu as déjà utilises des itérateurs tu devrais savoir quelles sont ces fonctions (++,*,ect).

http://www.boost.org/doc/libs/1_49_0...doc/index.html devrait aussi pouvoir te donner des idées et sera plus lisible que la norme pour une première approche.

2/ Oui, après selon comment tu mets ca en place soit tu peux avoir une classe par type d'itérateur, soit une seule classe template avec une tag classe, c'est à toi de voir

3/ Oui c'est ca, un itérateur non constant permet d'itérer sur un ensemble et d'en modifier les valeurs, un itérateur constant permet juste de parcourir l'ensemble sans en modifier les valeurs (et ni l'un ni l'autre ne permettent de modifier la structure du conteneur : ajouter/enlever un élément).

[Rewpparo]

Personellement dans le cas d'arbres, plutot que des itérateurs j'aime faire des listes intrusives, c'est a dire que la liste est contenue dans les node. Chaque node a les fonctions suivantes :

Node* getFirstChild()
Node* getNextSibling()
Node* getPreviousSibling() (optionnel)
Node* getParent()

Chaque node stocke son parent, un enfant, et le frère suivant (+ précédent ?).
Ca permet d'itérer ton arbre comme tu veux, ou de faire du bon petit récursif allègrement.
Par contre chaque node ne peut faire partie que d'un arbre à la fois, mais c'est rarement une limitation.

Astuce suplémentaire : Tu peux rendre les listes de frères circulaires, c'est a dire que quand tu arrives en bas de la liste, tu peux toujours appeller next qui te renverras au début de la liste. Ton critère pour savoir si tu as tout parcouru est de vérifier si tu ne retombes pas sur l'élément par lequel tu as commencé.
Ca permet de simplifier largement le code, en se débarassant de tous les cas particuliers des limites de la liste, et donc d'accélérer le code. Ca permet également d'itérer la liste des enfants en disposant uniquement d'un enfant quelconque, et sans avoir besoin de toucher ni même de connaitre le parent.

Boost propose une implémentation je crois, mais je ne l'ai pas étudiée en détail.
Explication du concept sur un blog anglophone


Juste pour te présenter d'autres options que la facon de voir très STL que tu as. Ta démarche reste tout à fait valable.