Discussion :

[Abstrus]

Bonjour !
Dans le cadre de mes cours, je n'ai jamais eu l'occasion de voir les fonctionnalités "programmation fonctionnelle" du C++ et je cherche des pistes pour un certain algo. Voici le contexte.

Code :

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

1
2
3
4
5
6
7
8
 
class foo{
public:
    void a(foo*);    // fonctions 
    int b();
private:
    HashTable<key, foo*> enfants;
}

J'ai donc un arbre de foo, avec un nombre indéterminé de foo à chaque niveau.

Je voudrais une sorte de forEach qui appliquerais a() ou b() à chaque enfant et sous enfant de mon arbre. Une fonction qui ne sert qu'à parcourir l'arbre et appliquer une fonction membre à chaque élément (ou, éventuellement, à chaque élément répondant à un critère).

Par contre, je n'ai aucune idée de comment travailler avec des pointeurs sur fonction, etc.

Quelqu'un a une piste ?

Merci beaucoup d'avance !

EDIT : Je ne peux utiliser que Qt et la STL, puisque c'est dans le cadre d'un cours (je tiens à spécifier que ce n'est pas l'essence du cours du tout (c'est un cours d'OpenGL), c'est un petit ajout personnel, pour satisfaire ma curiosité et donner un plus value à mon apprentissage)

[cycloop]

Je ne connais pas l'implémentation de HashTable mais tu dois pouvoir récupérer le nombre d'éléments et l'accès à chaque élément, non ?

A partir de là une fonction de parcours d'arbre toute bête :

Code :

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

1
2
3
4
5
6
7
8
void parcourir(foo* f) {
 
	f->b()
 
	for(int i = 0 ; i < f->children.size() ; i++) { // remplace size par ce qui permet de récupére la taille
		parcourir(f->children.get(i)); // remplace get par la méthode de récupération d'un élément de la hashtable
	}
}

[Feriaman]

Bonjour,

Je voudrais une sorte de forEach qui appliquerais a() ou b() à chaque enfant et sous enfant de mon arbre.

Ca existe dans la STL et ça s'appelle std::foreach.

Tu peux écrire ton propre foncteur, tu as un exemple ici.

Bonne journée

[3DArchi]

Bonjour,



Ca existe dans la STL et ça s'appelle std::foreach.

Tu peux écrire ton propre foncteur, tu as un exemple ici.

Bonne journée

En fait, la vrai difficulté est d'écrire un itérateur adéquat pour parcourir l'arbre. Ensuite comme tu dis, les algos de la STL sont assez efficaces
Pour construire ses itérateurs : Boost.Iterator.

[Feriaman]

Pour construire ses itérateurs : Boost.Iterator.

+1

Le problème c'est que :

Je ne peux utiliser que Qt et la STL, puisque c'est dans le cadre d'un cours

[EDIT]
Cela dit, tu as complètement raison : ce n'est pas évident de construire l'itérateur en question. Si en plus cela sort du cour, ce n'est pas forcément la peine d'y passer une demi-journée.

En gros, je pense qu'il suffit de faire une classe :
- qui se déréférence en foo
- qui s'incrémente (de façon à parcourir ton arbre quand même)
- il doit falloir aussi surcharge "==" et "="

Je ne sais pas trop ou trouver une référence sur le sujet
[\EDIT]

[EDIT 2]
Pour le parcours de l'arbre j'opterais pour un méthode brute. L'idée n'est pas de faire quelque chose de performant, mais de comprendre le concept.

Un vecteur qui à chaque profondeur associe le dernier élément de cette profondeur traité ou en cours de traitement me semble être une première approche suffisante.
[\EDIT 2]

[3DArchi]

Boost.Itérateur te fourni un cadre pour construire les itérateurs plus facilement. Mais leur construction from scratch n'est pas si complexe même si <iterator> propose le minimum vital.