Discussion :

[darkman19320]

Bonjour tout le monde,

Je suis en train de construire un petit arbre basé sur les pointeurs intelligents.

J'ai mon objet (Node) contenant un std::weak_ptr pour son parent et une liste de std::weak_ptr pour ses enfants.

Ces différents objets sont stocker dans un conteneur me permettant d'accéder plus facilement aux différents noeuds.

Je souhaite :

1. lorsque je supprime le parent de supprimer tous les enfants
2. lorsque je supprime un enfant, il soit supprimer de son parent

Pour résoudre le 1), j'envoie un évènement pour dire à mon conteneur de supprimer le noeud.
Pour résoudre le 2), je demande au parent de parcourir toute la liste des enfants et de supprimer les enfants déjà supprimés.

Je voulais savoir si quelqu'un à une autre approche à me proposer (dont éviter de parcourir toute la liste des enfants pour supprimer ceux déjà supprimés).

Merci.

Voici un exemple d'implémentation de mon idée (sans la partie conteneur d'objet ni envoie d'évènement pour supprimer les enfants lors de la suppression du parent):

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <memory>
#include <list>
#include <iostream>
 
using namespace std;
 
class Node;
 
typedef std::shared_ptr<Node> NodePtr;
typedef std::weak_ptr<Node> NodeWPtr;
 
class Node : public std::enable_shared_from_this<Node>
{
    friend class NodeFactory;
    Node() = default;
public:
    virtual ~Node()
    {
        if (NodePtr p = p_parent.lock()) {
            p->removeDeletedChild();
        }
        for (NodeWPtr c : p_children) {
			if (NodePtr child = c.lock()) {
			    // TODO: ajouter l'évènement pour demander au conteneur de supprimer child
				child->p_parent.reset();
			}
		}
    }
 
    void addChild(NodePtr child) 
    {
        if (child) {
            child->p_parent = getPtr();
            // child est converti automatiquement en weak_ptr;
            p_children.push_back(child);
        }
    }
 
    const std::list<NodeWPtr> & getChildren() const
    {
        return p_children;
    }
 
    void removeDeletedChild()
    {
        std::list<NodeWPtr>::iterator it;
		for (it = p_children.begin(); it != p_children.end();) {
			NodePtr child = it->lock();
			if (!child) {
				it = p_children.erase(it);
			} else {
				++it;
			}
		}
    }
 
    NodePtr getPtr()
    {
        return shared_from_this();
    }
 
protected:
    NodeWPtr p_parent;
    std::list<NodeWPtr> p_children;
};
 
class NodeFactory
{
public:
    NodePtr create()
    {
        return std::shared_ptr<Node>(new Node());
    }
};
 
int main()
{
    NodeFactory factory;
    NodePtr parent = factory.create();
    NodePtr child1 = factory.create();
    NodePtr child2 = factory.create();
 
    parent->addChild(child1);
    parent->addChild(child2);
 
    if (parent->getChildren().size() != 2) {
        std::cerr << "Problem to add children" << std::endl;
        return 1;
    } else {
        NodeWPtr tmpWChild1 = parent->getChildren().front();
        NodeWPtr tmpWChild2 = parent->getChildren().back();
        if (NodePtr tmpChild1 = tmpWChild1.lock()) {
            if (tmpChild1 != child1) {
                std::cerr << "tmpChild1 is different from child1" << std::endl;
                return 1;
            }
        } else {
            std::cerr << "The child1 is not added correctly" << std::endl;
            return 1;
        }
        if (NodePtr tmpChild2 = tmpWChild2.lock()) {
            if (tmpChild2 != child2) {
                std::cerr << "tmpChild2 is different from child1" << std::endl;
                return 1;
            }
        } else {
            std::cerr << "The child2 is not added correctly" << std::endl;
            return 1;
        }
 
        child2.reset();
 
        if (parent->getChildren().size() != 1) {
            std::cerr << "Problem to remove children" << std::endl;
            return 1;
        } else {
            tmpWChild1 = parent->getChildren().front();
            if (NodePtr tmpChild1 = tmpWChild1.lock()) {
                if (tmpChild1 != child1) {
                    std::cerr << "tmpChild1 is different from child1" << std::endl;
                    return 1;
                }
            } else {
                std::cerr << "The child1 is not added correctly" << std::endl;
                return 1;
            }
        }
    }
 
   std::cout << "All work correctly" << std::endl;
 
   return 0;
}

[Bousk]

Salut,

avant d'aller plus loin : où sont les shared_ptr ? Qui les conserve et possède ?
Pourquoi l'arbre ne contient pas lui-même les noeuds mais juste un weak_ptr ?

Si le noeud possédait les données, il faudrait utiliser unique_ptr et raw ptr.
Pour le parcours de la collection, c'est à mon avis inéluctable : tu dois parcourir le tout et supprimer le nécessaire pendant ce parcours.
Après si tu restes avec des weak_ptr, tu t'en moques dans une moindre mesure : si le shared_ptr est mort, tu ne pourras pas lock le weak_ptr pour l'utiliser.

[darkman19320]

avant d'aller plus loin : où sont les shared_ptr ? Qui les conserve et possède ?

Le conteneur de tous les objets possèdera tous les shared_ptr (en gros ça sera un NodeManager).

Pourquoi l'arbre ne contient pas lui-même les noeuds mais juste un weak_ptr ?

Pour éviter d'avoir plusieurs shared_ptr qui se baladent et ne plus savoir qui à la possession des noeuds.

Après si tu restes avec des weak_ptr, tu t'en moques dans une moindre mesure : si le shared_ptr est mort, tu ne pourras pas lock le weak_ptr pour l'utiliser.

Le problème avec ça c'est que ma liste d'enfant risque de grandir de plus en plus pour ne rien faire enfin de compte.

[Bousk]

Si tu as un container pour les objets par-dessus pourquoi utiliser des pointeurs intelligents ? Tu as des perfs à sacrifier ?
Ton truc c'est comme si tu faisais une liste de weak_ptr et avais tes shared_ptr ailleurs. Ca a peu de sens imo.

Le problème avec ça c'est que ma liste d'enfant risque de grandir de plus en plus pour ne rien faire enfin de compte.

Ton programme n'est jamais réinitialisé ? Pourquoi il grandirait sans arrêt ?
Que se passe-t-il quand tu détruis un shared_ptr ? Tu gardes des weak_ptr qui pointent plus sur rien ?
Pourquoi pas une fonction de cleanup tous les X temps ?

[ParseCoder]

Je voulais savoir si quelqu'un à une autre approche à me proposer (dont éviter de parcourir toute la liste des enfants pour supprimer ceux déjà supprimés).

Personellement j'utiliserai un std::vector pour les enfants, plutôt qu'une std::list. L'accès est plus rapide et c'est plus compact en mémoire. C'est vrai qu'au lieu de supprimer un element de liste tu devras faire un décalage de 1 vers la gauche dans ton tableau à chaque fois que tu vas supprimer un enfant, mais je ne crois pas que tu y perdes, en complexité algorithmique c'est strictment pareil.
Après si ton soucis c'est les perfs pures tu peux optimiser un peu la chose, mais ça va pas être très beau (je trouve). Tu peux conserver au niveau d'un noeud, sa position dans le tableau du parent et ainsi tu n'auras besoin de parcourir que la partie du tableau qui est vraiment utile. Si tu as gardé la std::list tu peux conserver alors l'itérateur, ce qui est peut-être pas mal finalement. Tu peux aussi éventuellement avoir des "trous" (pointeurs nulls) dans le tableau des enfants si ça n'est pas trop gênant. Bref tu vois l'idée je pense ...

[darkman19320]

@Bousk Il est vrai que je peux utiliser seulement des raw pointers dans le cas où j'ai un conteneur ce qui impliquerai la gestion "manuelle" de la mémoire directement dans le conteneur. Je vais essayer avec les raws pointers et je vois si cela me convient.
Mon programme ne se réinitialise que très rarement: j'ai par exemple un objet A qui va rester tout le long de la session et à celui-ci on va lui appliquer diverses transformations (des filtres par exemple) que l'on risque de supprimer assez régulièrement et donc j'aurai une liste d'enfant pour cet objet A qui seront pour la plus part vide si je ne les supprime pas.
La fonction de cleanup est effectuée lors de la suppression d'un enfant (quand le destructeur de celui-ci est appelé). Je n'aime pas trop l'idée d'exécuter tous les X temps une fonction pour nettoyer des ressources (mauvais souvenir avec le garbage collector de Java...)

@ParseCoder: J'ai pris une liste au lieu d'un vecteur car je n'accèderais pas souvent aux enfants directement depuis le parent. J'y accèderai depuis le conteneur. La liste me permet plus facilement de supprimer un élément en fonction de sa valeur.

Edit: Je viens de remplacer les shared_ptr/weak_ptr par des raw_ptr et pour le moment aucun problème n'est remarqué. On verra avec le temps si tout fonctionne correctement.

[ParseCoder]

@ParseCoder: J'ai pris une liste au lieu d'un vecteur car je n'accèderais pas souvent aux enfants directement depuis le parent. J'y accèderai depuis le conteneur. La liste me permet plus facilement de supprimer un élément en fonction de sa valeur.

Si tu accèdes aux éléments le plus souvent par un accès direct, et non par un parcours de l'arbre, ça veut dire que tu n'as pas vraiment besoin de cette structure arborescente. A la place pour garder une notion de parentée tu peux utiliser quelque chose qui ressemblerai à ceci dans ton conteneur:

std::unordered_multimap<std::shared_ptr<Node>,std::shared_ptr<Node>> childhood; // relation parent->enfants
std::unordered_map<std::shared_ptr<Node>,std::shared_ptr<Node>> parentship; // relation enfant->parent

(ou encore mieux: utilise 1 seul conteneur Boost.Bimap qui est une map bidirectionnelle)

... et enlever p_parent et p_children de la classe Node (qui comporte par ailleurs d'autres infos utiles que tu n'a pas mis je suppose). Ajouter et retirer une parentée devient simple. Lorsque qu'un Node est détruit il doit demander au conteneur de le désenregistrer. Un Node peut demander au conteneur quel est son parent ou ses enfants.

En espérant que ça te donne des idées

[koala01]

Salut,

@Bousk Il est vrai que je peux utiliser seulement des raw pointers dans le cas où j'ai un conteneur ce qui impliquerai la gestion "manuelle" de la mémoire directement dans le conteneur. Je vais essayer avec les raws pointers et je vois si cela me convient.

Attention, la remarque de Bousk ne portait pas sur la différence shared_ptr Vs raw pointers, mais bien sur la différence shared_ptr Vs unique_ptr.

Les shared_ptr ne doivent être utilisés que si l'on a de bonnes raisons de croire que plusieurs "propriétaires" se partagent la tache de décider de la destruction (ou non) du pointeur possédé. Ils permettent de faire en sorte que le dernier propriétaire vivant se charge de la destruction. Autrement dit "le dernier éteint tout et ferme la porte"

Seulement, pour arriver à ce résultat, shared_ptr doit compter les référence (comprend: compter le nombre d'éléments qui ont revendiqué la propriété du pointeur), et ca, ca ne se fait malheureusement pas sans perdre de performances

De plus, on se rend compte que cette solution est régulièrement choisie uniquement pour la mauvaise raison que l'on est "trop fade" que pour réfléchir "au propriétaire légitime" du pointeur; pour réfléchir à la question "mais qui a le droit de détruire ce pointeur?".


Mais, même s'il faut de bonnes raisons pour décider d'utiliser un shared_ptr et que l'on préférera donc l'éviter, ce n'est pas une raison pour tomber dans l'exces inverse en décidant d'avoir recours aux raw pointers, pour la simple et bonne raison qu'il est particulièrement difficile de s'assurer que tous les éléments pour lesquels nous aurons eu recours à l'allocation dynamique de la mémoire seront effectivement détruits dans tous les cas "en temps et en heure".

Entre les deux, on trouve la "bonne" manière de faire : on détermine le seul propriétaire légitime du pointeur, et on s'assure que la mémoire allouée au pointeur sera libérée en temps et en heure en encapsulant le pointeur dans un unique_ptr.

Une fois que ca c'est fait, on peut commencer à avancer, en gardant en tête le fait que soit on devra décider de "transmettre" la propriété du pointeur de proche en proche (celui qui fournit le pointeur abandonne la propriété tu pointeur au profit de celui auquel il le donne), soit on devra décider que tous ceux qui obtiendront le pointeur (voir une référence sur l'objet pointé, choix à privilégier autant que possible) ne seront que des utilisateurs de l'élément pointé et qu'il n'auront donc aucun droit de décider de libérer la mémoire allouée au pointeur.

Si l'on choisit la deuxième solution (qui s'avère souvent être la meilleure afin de respecter le LSP), on peut décider que les utilisateur utilisent des raw pointers à la condition expresse d'imposer le fait de ne jamais appeler delete sur le raw pointer.

Mais cela sous-entend une politique stricte qui tend à aller à l'encontre des habitudes de certains (du genre de "si j'ai un pointeur, je ne dois pas oublier d'appeler delete dessus avant de perdre l'adresse mémoire en question).

C'est la raison pour laquelle on préférera généralement utiliser des référence, car il ne viendrait normalement à personne l'idée d'écrire un code proche de delete &myref. Le truc, c'est qu'une référence doit être définie (elle doit savoir quel objet est référencé) au moment de sa création, et que l'on ne peut pas décider qu'elle référence un autre objet une fois créée.

Et surtout, il ne faut pas oublier que l'on ne peut pas créer de collection de références .

C'est la raison pour laquelle c++11 est arrivé avec la classe std::reference_wrapper qui encapsule une référence sur un objet donné.

Malheureusement, cette classe ne résout qu'une partie du problème, en permettant, de changer l'objet référencé (au travers de l'opérateur =) et en permettant de créer des collections de std::wrapper_reference, ce qui (il faut bien l'admettre) te sauvera la mise dans le cadre d'un arbre Naire.

Pour résoudre la dernière partie du problème (vu qu'une référence doit savoir quel objet elle référence à la création, un std::reference_wrapper doit forcément connaitre l'objet référencé à sa création), l'utilisation de ce que l'on appelle un "null object" peut s'avérer intéressante

PS: méfies-toi du concept de "manager"... C'est un terme beaucoup trop générique qui fait que tu auras rapidement tendance à lui donner un tas de responsabilités qu'il n'aurait jamais du avoir.
Préfères lui des termes comme "fabrique/factory" ou "propriétaire/holder" qui ont au moins le bon gout de représenter une responsabilité bien précise et non ambigue