Fuite mémoire sur une classe template.

**robinsondesbois** · 04/07/2013, 12h49

Bonjour,

Je n'arrive pas à désallouer mes pointeurs.
Voici ma classe :

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
#ifndef GRAPHNODE_H
#define GRAPHNODE_H
 
#include <iostream>
#include <vector>
 
template<typename T>
class GraphNode
{
private:
	T _value;
	int _nbChild;
	std::vector<GraphNode *> _children;
 
public:
	GraphNode(void);
	GraphNode(T value);
	GraphNode(const GraphNode &graphNode);
 
	void AddChild(GraphNode *graphNode);
	void DrawGraphNode();
 
	GraphNode &operator=(const GraphNode& graphNode);
 
	~GraphNode(void);
 
 
	//getter
	const T								GetValue()			const {return _value;}
	const int							GetNbChild()		const {return _nbChild;}
	const GraphNode<T> *				GetChild(int i)		const {return _children[i];}
	const std::vector<GraphNode<T> *>	GetChildren()		const {return _children;}
 
	//setter
	void SetValue(T value){_value = value;}
	void SetChild(GraphNode *graphNode, int i){_children[i] = graphNode;}
};
 
 
 
 
 
 
//================================DEFINITION DES FONCTIONS MEMBRES=====================
 
template<typename T>
GraphNode<T>::GraphNode(void)
{
	this->_value = (T)0;
	this->_nbChild = 0;
	this->_children = std::vector<GraphNode *>();
}
 
template<typename T>
GraphNode<T>::GraphNode(T value)
{
	this->_value = value;
	this->_nbChild = 0;
	this->_children = std::vector<GraphNode *>();
}
 
template<typename T>
GraphNode<T>::GraphNode(const GraphNode<T>& graphNode)
{
	this->_value = graphNode->GetValue();
	this->_nbChild = graphNode->GetNbChild();
	if (graphNode->GetChildren() != NULL)
	{
		this->_children = new vector<GraphNode *>[this->_nbChild];
		for (int i=0; i<this->_nbChild; ++i)
			this->_children.push_back(graphNode->GetChild(i));
	}
}
 
template<typename T>
void GraphNode<T>::AddChild(GraphNode<T> *graphNode)
{
	++this->_nbChild;
	this->_children.push_back(graphNode);
}
 
template<typename T>
void GraphNode<T>::DrawGraphNode()
{
	for (int i=0; i<this->_nbChild; ++i)
	{
		std::cout << "______";
		if (i == this->_nbChild/2)
			std::cout << _value;
	}
	std::cout << std::endl;
	for (int i=0; i<this->_nbChild; ++i)
		std::cout << "|      ";
	for (int i=0; i<this->_nbChild; ++i)
		std::cout << _children[i]->GetValue();
}
 
template<typename T>
GraphNode<T> &GraphNode<T>::operator=(const GraphNode<T> &graphNode)
{
	this->_value = graphNode->GetValue();
	this->_nbChild = graphNode->GetNbChild();
	if (graphNode->GetChildren() != NULL)
	{
		if (this->_children != NULL)
			delete[] this->_children;
		this->_children = new GraphNode*[this->_nbChild];
		for (int i=0; i<this->_nbChild; ++i)
			this->_children[i] = graphNode->GetChild(i);
	}
}
 
template<typename T>
GraphNode<T>::~GraphNode(void)
{
	for (int i=0; i<this->_nbChild; i++)
		delete this->_children[i];
}
 
 
#endif

Si je ne met rien dans le destructeur Avast ne me recommande pas ce programme. Si je met ma boucle j'ai un joli : "Debug Assertion Failed"

Merci d'avance,
Robin

**iNaKoll** · 04/07/2013, 13h34

Bonjour,

Quelle assertion n'est pas vérifiée ?
Où sont alloués les GraphNode passés à AddChild ?
Les GraphNode peuvent-ils se référencer eux-même dans AddChild ?
Pourquoi maintenir _nbChild plutôt que de faire confiance à _children.size() ?

**Médinoc** · 04/07/2013, 13h36

Les cycles sont-ils permis dans ton graphe?
Pourquoi Avast irait s'inquiéter d'un programme fait localement?

**therwald** · 04/07/2013, 14h01

hmm...utiliser new ou delete sur un membre std::vector me semble assez propice aux fuites, dangling pointers et autres double frees...mode jardinage mémoire on...

**robinsondesbois** · 04/07/2013, 14h11

@iNaKoll : heu oui, je n'utilise plus _nbChild; et les GraphNode sont déclaré dans le main pour le moment.

@Médinoc : Oui c'est un graphe général. J'utilise Avast pour détecter mes fuite mémoire ^^

@therwald : Je veux bien remplacer mon vector mais par quoi ?

**therwald** · 04/07/2013, 14h16

En fait il ne s'agit pas de remplacer vector mais de s'en servir comme d'un vector.
Pas besoin de le remplacer dans un opérateur=: on vide, on remet...
delete[] sur le vector c'est au mieux un double free...
Si la durée de vie des children est indépendante de celle du vector, ne fais pas de delete à ce niveau, c'est une autre classe qui le fera (le graphe?). Si les children n'existent que dans ce vector, alors il faut laisser tomber les pointeurs et utiliser un vector d'objets. Ceci dit je pense que les noeuds du grpahe sont plutôt des entités que des valeurs, c'est à dire que les copier n'a pas de sens, et que leur durée de vie ne dépend pas de leur existence en tant que "child"?

**therwald** · 04/07/2013, 14h20

Par ailleurs ce que je disais n'est pas spécifique à vector: si tu utilises un membre objet, ne pas faire de delete dessus. Faire une affectation à partir d'un objet alloué par new provoque des fuites de mémoire (ton new n'est jamais libéré).
C'est du C++ qui sent un peu la java par les bords...je n'ai rien contre java (que je pratique d'ailleurs) mais penser en java quand on fait du C++ c'est highway to hell...

**robinsondesbois** · 04/07/2013, 14h25

Ok donc mon operator= devient donc :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
template<typename T>
GraphNode<T> &GraphNode<T>::operator=(const GraphNode<T> &graphNode)
{
	this->_value = graphNode->GetValue();
	if (graphNode->GetChildren() != NULL)
	{
		this->_children.clear();
		for (int i=0; i<this->_children.size(); ++i)
			this->_children.push_back(graphNode->GetChild(i));
	}
}

Par contre j'aimerais bien raisonner de la façon suivante : une class est indépendante des autres. Elle désalloue donc elle même ses pointeurs. En gros je voudrais pouvoir créer aussi bien une class graphe que une class GraphNode.
Ou alors si on suit ta méthode, il faudrait pouvoir interdire la création d'un objet de type GraphNode sauf pour la class Graphe (comme ça il n'y a que elle qui détruit les GraphNode). Mais ça je ne sais pas si c'est possible.

**robinsondesbois** · 04/07/2013, 14h36

En faite ça marche

Mes erreur venais de mon "jardinage mémoire"
Lors de la destruction de mes objets, le destructeur détruisait _children déjà détruit.

Cependant je suis curieux et je voudrais bien savoir si on peut interdire la création d'un objet sauf pour une autre class.

**therwald** · 04/07/2013, 14h36

Envoyé par robinsondesbois

Ou alors si on suit ta méthode, il faudrait pouvoir interdire la création d'un objet de type GraphNode sauf pour la class Graphe (comme ça il n'y a que elle qui détruit les GraphNode). Mais ça je ne sais pas si c'est possible.

Ce serait une grosse restriction, pourquoi ne pas simplement admettre que la classe GraphNode ne crée jamais de children, et réserver la création aux utilisateurs de cette classe (qui en fonction des cas d'utilisation pourraient devoir différer)?
Si toutefois tu veux réserver la création d'instance à une classe c'est peut-être possible en déclarant private le constructeur de GraphNode et en mettant ta classe créatrice friend de GraphNode. Si tu fais ça, je te conseille de limiter la responsabilité de cette classe friend à la création d'instances et à la gestion de leur durée de vie, les autres fonctionnalités du graphe étant confiées à une ou n autres classes (principe de la responsabilité unique).
Du coup cette classe serait plutôt une NodeFactory, qui devrait être créée avant d'utiliser le graphe, et détruite (et les nodes avec) quand elle devient inutile. Attention toutefois à ce que la destruction des GraphNode ne s'accompagne pas d'opérations sur les nodes sinon tu risque d'appeler des fonctions d'objets déjà morts (kaboum...)

**Médinoc** · 04/07/2013, 14h41

Je me demande s'il est normal que les noeuds de ton graphe soient copiables et assignable.
Après une copie telle que tu l'as posée, quel noeud a la responsabilité de détruire les "fils"?

De plus, mon histoire sur les cycles est liée au fait que si un nœud détruit toutes ses "destinations" (on ne peut pas les appeler des "fils" car il ne s'agit pas d'un arbre; un arbre est un graphe sans cycle), en cas de cycle ~A() va faire un delete B qui fera un delete C qui fera un delete A...

Franchement, je conseillerais plutôt de faire gérer la durée de vie de tes nœuds par une classe Graph, plutôt qu'avoir des nœuds qui gèrent la durée de vie les uns des autres.

shared_ptr<> n'est pas une solution ici, car leur seul effet sera que les cycles causeront des fuites de mémoire au lieu de causer des comportements indéfinis.

**robinsondesbois** · 04/07/2013, 14h43

@therwald : Ha je n'avais pas pensé au friend.
Dans ma conception ça me semblais logique qu'il n'y est que la class Graphe qui puisse utiliser GraphNode.
Mais sinon c'est pas bête le NodeFactory. Je vais modifier mon UML

@Médinoc : Voila c'est modifier. Maintenant chaque objet ce détruit tout seul (pas ses fils) et cette destruction est géré par la class Graph

Merci à tous pour vos réponse

**Médinoc** · 04/07/2013, 14h48

Envoyé par robinsondesbois

Cependant je suis curieux et je voudrais bien savoir si on peut interdire la création d'un objet sauf pour une autre class.

Tu peux utiliser friend, mais ça n'est pas vraiment nécessaire ici:

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
class GraphNode;
 
class Graph
{
public:
	Graph() {}
	Graph(Graph const &);
	Graph& operator=(Graph const &);
	void Swap(Graph &);
	~Graph();
 
	bool Register(GraphNode *);
	bool Unregister(GraphNode *);
private:
	std::vector<GraphNode*> nodes;
};
 
class GraphNode
{
private:
	GraphNode(/* ... */);
public:
	GraphNode* Create(Graph &parent/* ,... */);
};

**koala01** · 04/07/2013, 15h13

Salut,
Quelques remarques préliminaires:
void est implicite quand il n'y a pas d'argument à passer à une fonction.

Tu devrais utiliser les listes d'initialisation, plutôt que l'assignation dans tes constructeurs.

getChildren devrait renvoyer une référence constante sur le tableau

Un noeud de graphe a, typiquement, une sémantique d'entité parce que chaque noeud doit pouvoir être identifié de manière unique et non ambigüe. Cela implique que ta classe GraphNode devrait idéalement être non copiable et non assignable:

Ton constructeur par copie est, d'ailleurs, un nid à problème assez important. Je le recopie ici pour en parler

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
template<typename T>
GraphNode<T>::GraphNode(const GraphNode<T>& graphNode)
{
	this->_value = graphNode->GetValue();
	this->_nbChild = graphNode->GetNbChild();
	if (graphNode->GetChildren() != NULL)
	{
		this->_children = new vector<GraphNode *>[this->_nbChild];
		for (int i=0; i<this->_nbChild; ++i)
			this->_children.push_back(graphNode->GetChild(i));
	}
}

Les lignes 4 et 5 ne posent pas forcément problème, même si la liste d'initialisation serait préférable

La ligne 6 (et surtout le test sur null) ne rime à rien car, pour l'instant, tu renvoie _children par valeur, ce qui provoque une copie du tableau.

Tu devrais, surtout, t'intéresser à la valeur renvoyée par empty, par exemple:

Code :

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

1
2
3
if( !getChildren().empty()){
    /* copier les éléments du tableau */
}

La ligne 8 est une monstruosité!!!

Le membre _children est une valeur dont le type est un std::vector prévu pour contenir des pointeurs de type GraphNode, et toi, tu demandes d'y assigner le résultat de l'allocation dynamique d'un espace mémoire suffisant pour y stocker (_nbChild) vecteurs...

Ce n'est, décidément, pas ce que tu veux: ce qu'il te faut, c'est un (et un seul) std::vector (et non un pointeur sur std::vector!!!) qui contiendra, au final, le nombre correct de GraphNode

Tu obtiendra d'ailleurs ce résultat grâce aux push_back effectués à chaque fois (ligne 10)

Mais!!! ce push_back va lui-même poser un sérieux problème!

En effet, getChild(int) renvoie un pointeur sur le GraphNode enfant.

Mais un pointeur n'est jamais qu'une variable particulière en cela qu'elle représente l'adresse mémoire à laquelle on va trouver l'objet du type indiqué!

Le problème, c'est que c'est donc l'adresse qui sera copiée dans le tableau, avec comme résultat, le fait que l'adresse mémoire en question sera "partagée" entre l'original et la copie.

Du coup, lorsque le premier GraphNode (l'original ou la copie) sera détruit, son destructeur, qui invoque delete sur les pointeurs contenus, sera appelé, et le GraphNode "survivant" (celui qui n'est pas encore détruit!) contiendra un ensemble d'adresses... qui ne sont plus valides (parce que la mémoire allouée à ces données vient d'être libérée)

Du coup, lorsque le deuxième GraphNode sera détruit, et que son destructeur sera appelé, le fait d'essayer d'invoquer delete sur les différents éléments qu'il contient aura pour effet d'essayer de libérer une deuxième fois la mémoire qui leur est allouée (on parle de double libération de la mémoire), et cela ne pourra résulter qu'en une seule chose: un comportement indéfini (qui se traduira par une erreur de segmentation).

Ton opérateur d'affectation pose d'ailleurs à peu près le même problème (attention! tu as d'ailleurs oublié le return (*this) à la fin de la fonction)

Comme je te le disais un peu plus haut: ta classe a, a priori, une sémantique d'entité et il serait donc de bon ton d'en interdire la copie et l'assignation

Ceci dit, la question de savoir si les cycles sont autorisés prend toute son importance car je serais surement tenté de te proposer l'utilisation de pointeurs intelligents (std::unique_ptr ou std::shared_ptr), mais le choix entre les deux dépendra surtout de la possibilité ou non d'avoir des cycles

**robinsondesbois** · 11/07/2013, 08h25

Bonjour,

J'avais pour objectif de faire du code propre ^^
C'est pour cela que j'avais implémenté un constructeur par copie et l'opérateur = (formule de Coplien). Mais si c'est une classe d'entité, ces fonctions ne doivent pas être implémenté.

Je ne comprend pas pourquoi des cycles poserais problème.

Comme mon destructeur est vide chaque GraphNode se détruit. Il n'y a que Graph qui a accès à cette classe. Il suffit donc de ne pas lire le graphe pendant qu'il est détruit.

De plus j'ai rajouté deux autres fonctions pour pouvoir modifier mon graphe en toute sécurité

:

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
template<typename T>
void GraphNode<T>::AddChild(GraphNode<T> *graphNode)
{
	this->_children.push_back(graphNode);
	graphNode->AddFathers(this);
}
 
template<typename T>
void GraphNode<T>::SuppChild(GraphNode *graphNode)
{
	for (int i=0; i<this->_children.size(); ++i)
	{
		if (this->_children[i] == graphNode)
		{
			graphNode->SuppFathers(this);
			this->_children.erase(this->_children.begin() + i);
			break;
		}
	}
}
 
template<typename T>
void GraphNode<T>::AddFathers(GraphNode<T> *graphNode)
{
	this->_fathers.push_back(graphNode);
}
 
template<typename T>
void GraphNode<T>::SuppFathers(GraphNode *graphNode)
{
	for (int i=0; i<this->_fathers.size(); ++i)
	{
		if (this->_fathers[i] == graphNode)
		{
			this->_fathers.erase(this->_fathers.begin() + i);
			break;
		}
	}
}

**koala01** · 11/07/2013, 14h39

Envoyé par robinsondesbois

Bonjour,

J'avais pour objectif de faire du code propre ^^
C'est pour cela que j'avais implémenté un constructeur par copie et l'opérateur = (formule de Coplien). Mais si c'est une classe d'entité, ces fonctions ne doivent pas être implémenté.

Je ne comprend pas pourquoi des cycles poserais problème.

Comme mon destructeur est vide chaque GraphNode se détruit. Il n'y a que Graph qui a accès à cette classe. Il suffit donc de ne pas lire le graphe pendant qu'il est détruit.

Dans ton code d'origine, ce n'était justement pas le cas, je le remet ici pour mémoire

Code :

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

1
2
3
4
5
6
template<typename T>
GraphNode<T>::~GraphNode(void)
{
	for (int i=0; i<this->_nbChild; i++)
		delete this->_children[i];
}

(je te jure que je ne l'ai pas inventé celui-là

)

Imaginons que a soit relié à b qui est relié à c qui est relié à d qui est relié à a.

Lorsque tu va détruire a ([codinline]delete a[/codeinline]), le destructeur de a va être appelé.

Ce destructeur va faire appel à delete pour chaque pointeur se trouvant dans a->children_, dont b.

Cela va donc détruire b et en appeler le destructeur, qui va invoquer delete sur les pointeurs contenus dans b->children_, dont c.

Cela va détruire c et en appeler le destructeur, qui va invoquer delete sur les pointeurs contenus dans c->children, dont d.

Enfin, delete d va détruire d et appeler son destructeur, qui tentera d'invoquer delete d sur les pointeurs contenus dans d->children, ... dont a, parce que d n'a pas été tenu au courent que sont poineur sur a a été invalidé.

d contient donc un pointeur vers une adresse qui semble tout à fait valide, mais qui a déjà été libérée.

Le fait d'invoquer de nouveau delete sur cette adresse va provoquer ce que l'on appelle un comportement indéfini, parce que la norme n'a pas pu déterminer ce qui devrait se passer dans de telles conditions.

Sauf que, en fait, on sait parfaitement ce qui va se passer du coup: une erreur de segmentation va survenir, et le programme va planter lamentablement.

Si tu autorises les cycles dans ton graphe, il faut donc prendre des mesures pour faire en sorte que l'on ne tentera jamais de détruire deux fois un noeud à cause du cycle.

Si tu autorises les cycles dans ton graphe, tu dois donc impérativement veiller au minimum à briser tous le cycles dans lesquels un noeud particulier peut intervenir avant d'essayer de détruire ce noeud.

L'une des solutions pourrait consister dans le fait de rajouter une liste des "noeuds parents" à prévenir de la disparition de l'un de leurs enfants.

Evidemment, il faudra tenir cette liste à jour, et il faudra donc rajouter une fonction (addParent(TreeNode*)? pour pouvoir ce faire.

D'un autre coté, il faudra donner l'occasion au parent d'un noeud de le supprimer (sans essayer de le détruire!) de la liste de ses enfants.

Il faudra cependant éviter le cas "peau de banane" d'un cycle composé de seulement deux noeuds "a->b->a" sous peine de demander au parent qui vient d'être détruit de supprimer l'enfant qu'il a décidé de détruire de sa liste d'enfants

Il faudra donc faire en sorte de pouvoir demander à un noeud si un noeud particulier fait partie de la liste de ses parents(ce qui pourra sans doute être utile par ailleurs

)
On pourrait donc déjà modifier la classe GrapheNode sous une forme 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
39
40
41
42
43
44
45
46
47
48
49
template<typename T>
class GraphNode
{
private:
	T _value;
	int _nbChild;
	std::vector<GraphNode *> _children;
        std::vector<GraphNode *> _parents;
public:
	GraphNode(void);
	GraphNode(T value);
	GraphNode(const GraphNode &graphNode) = delete;
 
	void AddChild(GraphNode *graphNode);
	void DrawGraphNode();
 
	GraphNode &operator=(const GraphNode& graphNode) =delete;
 
	~GraphNode(void);
 
 
	//getter
	const T								GetValue()			const {return _value;}
	const int							GetNbChild()		const {return _nbChild;}
	const GraphNode<T> *				GetChild(int i)		const {return _children[i];}
	const std::vector<GraphNode<T> *>	GetChildren()		const {return _children;}
 
	//setter
	void SetValue(T value){_value = value;}
	void SetChild(GraphNode *graphNode, int i){_children[i] = graphNode;}
        bool hasParent(GrapheNode * toTest) const{
            /* C++11 inside */
            for(auto it : parents_)
            {
                if(it == toTest)
                    return true;
            }
            return false;
        }
        void removeChild(GrahpNode * toRem){
            /* C++11 inside */
            for(auto it : children_)
            {
                if(it == toTest)
                    it = nullptr;
            }
 
        }
};

NOTA: Je me suis contenté de faire en sorte de mettre tous les pointeurs correspondant à NULL, car delete NULL est garanti sans effet, et que la suppression réelle d'un élément d'un std::vector est consommatrice de temps si on veut qu'il soit correctement redimensionné. (et je n'ai pas modifié ton code d'origine, à par pour déclarer le constructeur par copie et l'opérateur d'affectation delete

)

Mais si cela te pose un problème (comme celui de devoir vérifier systématiquement la validité du pointeur chaque fois que tu tente d'accéder à un élément de children_), il est possible de supprimer effectivement l'élément du tableau

Enfin, nous devrions donc modifier le code du destructeur sous une forme 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
template<typename T>
GraphNode<T>::~GraphNode(void)
{
    /* on commence par briser tous les cycles */
    for(auto it : parents_){
           /* sauf les cycles de deux (a->b->a) */
           if(! it->hasParent(this)){
               it->removeChild(this);
           }
    }
    /* puid on peut détruire tous les enfants à notre aise */
    for (int i=0; i<this->_nbChild; i++)
        delete this->_children[i];
}

De plus j'ai rajouté deux autres fonctions pour pouvoir modifier mon graphe en toute sécurité

:

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
template<typename T>
void GraphNode<T>::AddChild(GraphNode<T> *graphNode)
{
	this->_children.push_back(graphNode);
	graphNode->AddFathers(this);
}
 
template<typename T>
void GraphNode<T>::SuppChild(GraphNode *graphNode)
{
	for (int i=0; i<this->_children.size(); ++i)
	{
		if (this->_children[i] == graphNode)
		{
			graphNode->SuppFathers(this);
			this->_children.erase(this->_children.begin() + i);
			break;
		}
	}
}
 
template<typename T>
void GraphNode<T>::AddFathers(GraphNode<T> *graphNode)
{
	this->_fathers.push_back(graphNode);
}
 
template<typename T>
void GraphNode<T>::SuppFathers(GraphNode *graphNode)
{
	for (int i=0; i<this->_fathers.size(); ++i)
	{
		if (this->_fathers[i] == graphNode)
		{
			this->_fathers.erase(this->_fathers.begin() + i);
			break;
		}
	}
}

Oui, c'est, en gros, ce que je viens de faire

Fais juste attention au fait que, encore une fois, tu ne vérifie pas la présence du parent dans AddFathers.

Il n'est donc pas impossible, pour une raison ou une autre, que tu en vienne à ajouter plusieurs fois le même parent à un noeud, tout comme tu risques, pour l'instant, de rajouter plusieurs fois le même enfant à un noeud.

Or, ta fonction SuppFathers ne supprimera que la première occurrence du parent trouvé, laissant les suivantes à leur place (s'il y en a).

Une utilisation maladroite sous une forme proche de

Code :

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

1
2
3
4
5
6
7
GraphNode<int> *a = new GraphNode<int>;
GraphNode<int> *b = new GraphNode<int>;
a->addChild(b);
/* plus loin */
a->addChild(b);
/* encore plus loin */
a->addChild(b);

risque d'avoir des conséquences... assez désastreuses.

En effet, si tu fais un

Code :

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

1
2
a->SuppChild(b);
b->SuppFathers(a);

tu vas croire,en toute bonne fois, que tu as correctement supprimé tout lien existant entre a et b.

Sauf que ce n'est pas le cas, parce que ce lien a été doublé, et meme triplé

Tu auras donc bien supprimé un des liens, mais il en restera encore un (en fait même deux) autre(s)

Ceci dit, tu as raison: la meilleure solution générale consiste à dégager le noeud de la responsabilité de la destruction de ses enfants, et donc de laisser le destructeur du noeud vide.

D'abord, parce que si tu décides de détruire le noeud "racine" (celui qui sert de base à tout ton graphe), c'est le graph entier qui serait détruit, et que ce n'est pas forcément ce que tu voudrais, ensuite parce que la suppression d'un noeud dans le graphe n'implique pas forcément la suppression de tous les noeud qui y sont rattachés sous la forme d'enfants, de manière directe ou indirecte.

Ce devrait donc être à l'élément qui décide de détruire un noeud (en fait, le graphe en lui-même

) de s'assurer d'en récupérer les enfants et de décider ce qu'il en fait

.

Ainsi, un graphe pourrait être le propriétaire légal de l'ensemble des noeuds (comprends: c'est le graphe qui décide de créer ou de détruire un noeud), le noeud ne servant plus en lui-même (outre la représentation des données du noeud) qu'à la représentation des relations qui peuvent exister entre eux.

De cette manière, tu n'as même pas forcément à t'inquiéter des parents d'un noeud (un parcours récursif te ramènera au noeud parent une fois que tu as fini de traiter les noeud enfant), et tu pourras décider que faire des noeuds enfants d'un noeud que tu as détruit "en connaissance de cause", une fois que le noeud détruit a bel et bien été supprimé de la liste des noeud existants.

Tu pourrais donc avoir une classe Graph qui est le propriétaire légal de l'ensemble des noeud, et qui ressemblerait à quelque chose comme

Code :

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

1
2
3
4
5
6
7
8
9
10
11
template <typename T>
class Graph{
    private:
       /* C++11 inside */
        std::vector<std::unique_ptr<GraphNode<T>>> allNodes_;
    public:
        void createNode(T value){
            GraphNode<T> * temp = new GraphNode<T>(value);
            allNodes_.emplace(std::unique_ptr<GraphNode>(value),allNodes_.end());
        }
};

J'utilise un std::unique_ptr parce que c'est une classe RAIIsante: c'est une classe non copiable (qui se manipule donc sous la forme de référence) qui prend en charge la durée de vie du pointeur dont on lui donne la propriété.

Le principal effet de cette classe est d'invoquer delete sur le pointeur possédé par chacune de ses instances.

Ainsi, lorsque je vais supprimer un élément de allNodes_, la mémoire allouée au pointeur possédé par cet élément sera correctement libérée sans que je n'aie à m'inquiéter de quoi que ce soit

Cette classe dispose, en outre, d'une fonction (get() ) qui permet de récupérer le pointeur nu (le unique_ptr garde la propriété du pointeur), d'une fonction release(T * other= nullptr) ) qui libère correctement la propriété du pointeur possédé avant de prendre possession du pointeur passé en paramètre et d'une fonction (release() ) qui renvoie le pointeur nu après en avoir abandonné la propriété.

Le principe à suivre avec la classe Graph que je présente ici est donc de se dire qu'un pointeur nu représente systématiquement un pointeur dont tu n'as que l'usage sans en avoir la possession, et qu'il ne faudra donc jamais invoquer delete dessus

La classe unique_ptr présente cependant un léger problème:
Elle permet de comparer deux unique_ptr afin de savoir si l'adresse correspondant au pointeur possédé est identique et avec nullptr.

Par contre, elle ne permet pas de comparer un unique_ptr avec un pointeur nu.

Or, nous devrons régulièrement comparer un unique_ptr avec un pointeur nu

Nous devons donc (ce sera le plus facile

) prévoir un foncteur qui s'occupe de cette comparaison (juste l'égalité devrait nous suffire

)
Notre class Graph pourrait donc être agrémentée d'un foncteur imbriqué sous la forme de

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
template <typename T>
class Graph{
    /* comme précédemment */
    private:
        struct equal{
            equal(GraphNode<T>* totest):totest(totest{}
            GraphNode<T>* totest;
            bool operator==(std::unque_ptr<GraphNode<T>> const & unique) const{
                return unique.get()==ptr;
            }
        };

Il faudra cependant une fonction utilitaire supplémentaire à la classe Graph : une fonction qui permette de savoir si un pointeur donné fait encore partie de la liste des pointeurs existants, sous une forme 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
 
template <typename T>
class Graph{
    /* comme précédemment */
    bool exists(GraphNode<T> * totest) const{
        equal test(totest);
        for(auto it : allNodes_){
            if(equal(it))
                return true;
        }
        return false;
    }
};

Nous pouvons maintenant créer une fonction qui supprime un noeud sans toucher à ses enfants, et une autre qui supprime un noeud et tous les enfants, de manière récursive:

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
template <typename T>
class Graph{
    /* supprime le noeud uniquement */
    void removeChild(GraphNode<T> * torem){
        equal test(torem);
        std::remove_if(allNodes_.begin(), allNodes_.end(),test);
        removeChildFromAllNodes(torem); // j'y viens ;)
    }
    void removeRecursiveNode(GraphNode * torem){
         /* déclarer la classe Graph comme amie de la class GraphNode
          * sera surement une bonne idée ;)
          */
          /* nous commençons par récupérer la liste des enfants ;) */
        std::queue<GraphNode<T>*> affectedQueue;
          for( auto it:torem->children_){
              affectedQueue.push(it);
          }
          /* je peux maintenant retirer le noeud en lui-même */
          removeChild(torem);
          /* s'il y avait des enfants, je dois récupérer les enfants des enfants
           * et ainsi de suite, jusqu'à ce que tous les descendants aient
           * été supprimés
           */
           while(! affectedQueue.empty()){
               /* je prend le premier enfant de la liste */
               GraphNode<T> * temp = affectedQueue.front();
               /* je récupère la liste de ses enfants */
               for( auto it:temp->children_){
                   affectedQueue.push(it);
               }
               /* je supprime l'enfant du graphe */
               removeChild(temp);
               /* et je le supprime de la liste */
               affectedQueue.pop();
           }
    }
};

Il ne me reste plus qu'à dire un mot, comme promis, au sujet de removeChildFromAllNodes(torem).

Cette fonction ne sera nécessaire que si les cycles dans ton graphe sont autorisé, pour s'assurer qu'aucun des noeuds restant ne contient une référence vers un noeud qui aurait détruit.

En effet, si tu essayes à un moment quelconque d'accéder à un noeud enfant qui n'existe plus, tu fonces tout droit vers l'erreur de segmentation, et il ne te restera plus qu'à pleurer

Cette fonction va donc parcourir tous les noeuds qui restent après la suppression et leur demander de supprimer la référence vers ce noeud s'il était connu comme étant un de leurs enfants

Elle sera implémentée sous une forme sans doute proche de

Code :

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

1
2
3
4
5
6
7
8
9
template <typename T>
class Graph{
    /* comme précédemment */
    void removeChildFromAllNodes(GrahNode<T> * torem){
        for(auto it: allNodes_){
            it->removeChild(torem);
        }
    }
};

Et là, nous avons à peu près fait le tour du problème

NOTA: ce code utilise intensivement les possibilités offertes par la nouvelle norme (C++11), bien qu'il pourrait encore les utiliser d'avantage.

Si tu n'as pas la possibilité d'utiliser cette opportunité et que tu éprouves des problèmes à le convertir dans le respect de l'ancienne norme, n'hésites pas à le dire

**koala01** · 11/07/2013, 15h11

En fait, je viens de réfléchir au fait que la fonction removeRecursiveNode risque de présenter un problème de performances assez important, surtout sur les très gros graphes.

En effet, bien qu'elle fasse strictement ce qu'on attend d'elle, elle va faire en sorte de parcourir l'intégralité du graphe pour demander aux noeuds restants de supprimer le noeud qu'on vient de détruire de la liste de leurs enfants. Y compris... aux noeuds qui seront détruits parce qu'ils sont l'enfant d'un enfant d'un enfant

Le nombre de parcours du graphe en entier peut donc assez rapidement devenir un problème et rendre la classe totalement inutilisable si les performances sont ne serait-ce qu'un tout petit peu critiques

On peut donc repenser un peu à la logique en faisant en sorte de ne demander à tous les noeuds restants de supprimer une liste de noeud de la liste de leurs enfants qu'une fois que tous les noeuds ont été supprimés.

Cela impliquera que chaque noeud devra parcourir la liste de ses enfants un nombre de fois égal au nombre d'enfants supprimé mais cela devrait malgré tout nous faire gagner un peu de temps

Je propose donc d'améliorer la fonction sous une forme 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
39
40
41
42
43
44
45
46
template <typename T>
class Graph{
    /* comme précédemment */
    void removeRecursiveNode(GraphNode * torem){
         std::list<GraphNode*> removedNodes;
         /* déclarer la classe Graph comme amie de la class GraphNode
          * sera surement une bonne idée ;)
          */
          /* nous commençons par récupérer la liste des enfants ;) */
        std::queue<GraphNode<T>*> affectedQueue;
          for( auto it:torem->children_){
              affectedQueue.push(it);
          }
          /* je peux maintenant retirer le noeud en lui-même */
          std::remove_if(allNodes_.begin(), allNodes_.end(),equal(torem));
          /* et je l'ajoute à la liste des noeuds supprimés */
          removedNodes.push_back(torem);
          /* s'il y avait des enfants, je dois récupérer les enfants des enfants
           * et ainsi de suite, jusqu'à ce que tous les descendants aient
           * été supprimés
           */
           while(! affectedQueue.empty()){
               /* je prend le premier enfant de la liste */
               GraphNode<T> * temp= affectedQueue.front();
               /* je récupère la liste de ses enfants */
               for( auto it:temp->children_){
                   affectedQueue.push(it);
               }
               /* je supprime l'enfant du graphe */
 
                std::remove_if(allNodes_.begin(), allNodes_.end(),equal(temp));
               /* et je le supprime de la liste des enfants*/
               affectedQueue.pop();
               /* mais je le rajoute à la liste des noeuds supprimés */
               removedNodes.push_back(temp);
           }
           removeChildFromAllNodes(removedNodes); // on va surcharger la fonction :D
    }
    void removeChildFromAllNodes(std::list<GraphNode<T>*> const & list){
        for(auto it: allNodes_){
            for(auto removed : list){
                it->removeChild(removed);
            }
        }
    }
};

PS: j'en ai profité pour repérer un copier foireux dans mon code précédant, je le corrige de suite

**therwald** · 11/07/2013, 16h38

Ca devient vite assez compliqué...d'où l'intérêt de confier la propriété des noeuds à une classe graphe, les liens entre enfants étant des pointeurs sur lesquels on ne fait pas de delete.
On crée alors tous les noeuds par un appel à une instance de graphe (qui enregistre au passage le ptr), et la libération des noeuds se fait en détruisant cette instance de graphe. On peut faire en sorte de ne renvoyer qu'une réf et de créer les liens à partir de réfs pour clarifier le fait que c'est graphe qui gère les noeuds.

Fuite mémoire sur une classe template.

Langage C++

Discussions similaires

Partager

Partager