Gestion de la mémoire pour une classe Noeud

Version imprimable

Bonjour,

mon code pour libérer la mémoire dans le destructeur de la classe Node ne fonctionne pas et génère une erreur à l'exécution lors de la supression du Node ayant une valeur 66. Ce Node n'ayant pas de Children, je m'attend à ce que le test if(*it!=nullptr) m'évitera de supprimer le contenu de Children pour le Node 66. Mais le programme essaie quand meme de supprimer Children du Node 66. Merci de votre aide :

Code:

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
 
 
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <iterator>
 
using namespace std;
 
/* ******************************************************* Node ********************************************************* */
 
template<class T>
class Node
{
private:
	T _value;
	vector<Node<T>*> children;
 
public:
	Node(T value);
	Node(const Node<T>& node);
	void AddChild(Node<T>* node);
	T getValue() const;
	vector<Node<T>*> returnChildren() const;
	void replaceChildrenByNewOnes(vector<Node<T>*> newChildren);
	~Node();
};
 
template<class T>
void Node<T>::replaceChildrenByNewOnes(vector<Node<T>*> newChildren)
{
	children = newChildren;
}
 
template <class T>
Node<T>::Node(T value) :_value(value)
{
	children.push_back(NULL);
}
 
template <class T>
Node<T>::Node(const Node& node) :_value(node.getValue()),
children(node.returnChildren())
{
}
 
template <class T>
void Node<T>::AddChild(Node* node)
{
	if (children[0] == NULL) { children.pop_back(); };
	children.push_back(node);
}
 
template <class T>
T Node<T>::getValue() const
{
	return _value;
}
 
template <class T>
vector<Node<T>*> Node<T>::returnChildren() const
{
	return children;
}
 
template <class T>
Node<T>::~Node()
{
	for (typename vector<Node<T>*>::iterator it = children.begin(); it != children.end(); it++)
	{
		if (*it != nullptr) {
			delete *it;
			cout << "Children with value " << (*it)->getValue() << " is deleted" << endl;
		}
	}
}
 
int main()
{
	Node<int> node(5);
	Node<int> node2(4);
	Node<int> node3(66);
 
	node.AddChild(&node2);
	node2.AddChild(&node3);
 
	Node<int>* ptr = &node;
	cout << ptr->getValue() << endl;
 
	system("PAUSE");
	return 0;
}

10/11/2015, 11h08
white_tentacle
Code:

1 2 3 4 5 if (*it != nullptr) { delete *it; cout << "Children with value " << (*it)->getValue() << " is deleted" << endl; }
Après delete *it, tu ne peux plus utiliser it !

Sinon, pourquoi ne pas utiliser std::unique_ptr dans ton vector ?
10/11/2015, 11h09
ternel

Peux-tu nous donner aussi le résultat d'une exécution?
Et nous dire comment tu l'analyse?

Je ne comprends pas pourquoi tu as un vecteur de pointeur dans ton cas.
En effet, si tu veux être polymorphique, à priori, c'est sur le contenu.
Tu devrais avoir un Node_base, non template, et Node<T> hériterait de Node_base.

Une exécution d'un delete doit correspondre à exactement une exécution de new. (et vice versa)
Ici, tu delete des pointeurs qui sont dse adresses de variables locales.

Salut,

Quelques remarques en vrac, en n'ayant lu le code qu'en diagonale :

JAMAIS de directive using namespace std; dans un fichier d'en-tête
Pourquoi te "casser la tête" à gérer la mémoire à la main, alors que tu pourrais utiliser std::unique_ptr :question:
le code if (*it != nullptr) dans le destructeur ne sert à rien : delete sur nullptr est garanti n'avoir aucun effet par la norme ;)

Ce qui te faciliterait énormément la vie, serait de travailler sous une forme proche de

Code:

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
#include <vector>
#include <memory>
template <typename T>
class Node{
public:
    /* quelques alias de type intéressants pour la facilité */
    using value_t  = T;
    using node_t = Node<T>;
private:
    /* ces alias ci sont à usage interne uniquement ... */
    using ptr_t = std::unique_ptr<node_t>;
    using children_t = std::vector<ptr_t>;
public:
    /* mais ceux ci seront utilisable depuis l'extérieur */
    using const_iterator_t = typename children_t::const_iterator;
    using iterator_t = typename children_t::iterator;
    Node(value_t v):value_(v){
    }
    /* ajouter une valeur, plutôt qu'un noeud, ca sera beaucoup plus facile ;)
    */
    void addChild(value_t /* const &*/ v){
        children_.emplace_back(std::make_unique<node_t>(v));
    }
    /* ce que l'on compare, c'est la valeur de chaque noeud */
    friend
    bool operator == (node_t const & lhs, node_t const & rhs){
        return lhs.value_ == rhs.value_;
    }
    const_iterator_t begin() const{
        return children_.begin();
    }
    const_iterator_t end() const{
        return children_.end();
    }
    size_t childCount() const{
        return children_.size();
    }
    value_t const & value() const{
        return value_;
    }
    /* un sucre syntaxique équivalent à la fonction value */
    value_t const & operator *() const{
        return value_;
    }
    /* à cause de std::unique_ptr, la classe ne peut pas être copiée...
    * mais on peut envisager de la cloner ;)
    */
    node_t clone() const{
        node_t * temp = new node_t(value_);
        for(auto const & it : children_){
            temp.add( *(it.get()));
        }
        return temp;
    }
    /* on peut vouloir interchanger deux noeuds */
    void swap(node_t & other){
        std::swap(value_, other.value_);
        std::swap(children_,other.children_);
    }
private:
    value_t value_;
    children_t children_;
};

et tu pourrais l'utiliser sous une forme proche de

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
using node = Node<int>;
int main(){
    node n(1);
    n.addChild(2);
    n.addChild(3);
    n.addChild(4);
    std::cout<<n.childCount();
    for (auto const & it :n){
        std::cout<< *(*(it.get()))<<"\n";
        /* revient au meme que */
        std::cout<<it.get()->value()<<"\n";
    }
    return 0;
}

L'avantage, c'est que comme tu as délégué la gestion de la mémoire à un std::unique_ptr, tu n'as même plus à t'inquiéter de créer un destructeur qui fasse le travail ;)

10/11/2015, 19h22
JasBeckC

J'utilise cette classe pour implementer une liste liées. J'utilise des delete car les noeuds sont alloués par des new dans la liste liées. Dans le vector de pointeurs je mets les adresses des noeuds auxquels pointe un noeud (cela permet d'avoir unz forme d'arbre/graphe)
Auriez vous une solution avec des pointeurs simples? Le but pour moi est de comprendre pourquoi ça ne marche pas.

Merci

Citation:

Envoyé par JasBeckC

J'utilise cette classe pour implementer une liste liées. J'utilise des delete car les noeuds sont alloués par des new dans la liste liées. Dans le vector de pointeurs je mets les adresses des noeuds auxquels pointe un noeud (cela permet d'avoir unz forme d'arbre/graphe)
Auriez vous une solution avec des pointeurs simples? Le but pour moi est de comprendre pourquoi ça ne marche pas.

Merci

Déjà, si tu n'envisages pas de créer des classes qui dérivent de ta classe Node, j'ai tendance à dire que tu n'as -- purement et simplement -- pas besoin de travailler avec des pointeurs (je viens de tilter sur ce point, à vrai dire :P)

Le code que j'ai produit dans mon intervention précédente pourrait en effet très bien être modifié pour prendre la forme de
Code:

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 #include <iostream> #include <vector> #include <memory> template <typename T> class Node{ public: /* quelques alias de type intéressants pour la facilité */ using value_t = T; using node_t = Node<T>; private: /* ces alias ci sont à usage interne uniquement ... */ using children_t = std::vector<node_t>; public: /* mais ceux ci seront utilisable depuis l'extérieur */ using const_iterator_t = typename children_t::const_iterator; using iterator_t = typename children_t::iterator; Node(value_t v):value_(v){ } /* ajouter une valeur, plutôt qu'un noeud, ca sera beaucoup plus facile ;) */ void addChild(value_t /* const &*/ v){ children_.emplace_back(node_t(v)); } /* ce que l'on compare, c'est la valeur de chaque noeud */ friend bool operator == (node_t const & lhs, node_t const & rhs){ return lhs.value_ == rhs.value_; } const_iterator_t begin() const{ return children_.begin(); } const_iterator_t end() const{ return children_.end(); } size_t childCount() const{ return children_.size(); } value_t const & value() const{ return value_; } /* un sucre syntaxique équivalent à la fonction value */ value_t const & operator *() const{ return value_; } /* on peut vouloir interchanger deux noeuds */ void swap(node_t & other){ std::swap(value_, other.value_); std::swap(children_,other.children_); } /* on n'a même plus besoin de la fonction clone, le constructeur de copie et * l'opérateur d'affectation implémentés automatiquement par le compilateur * font très bien leur boulot */ private: value_t value_; children_t children_; }; using node = Node<int>; int main(){ node n(1); n.addChild(2); n.addChild(3); n.addChild(4); std::cout<<n.childCount(); for (auto const & it :n){ std::cout<< *(it)<<"\n"; /* revient au meme que */ std::cout<<it.value()<<"\n"; } return 0; }
Et cela fonctionnerait tout aussi bien ;)

Ensuite, de manière générale, il faut comprendre que si les développeurs de la bibliothèque standard se sont crevés le cul à fournir des pointeurs intelligents, ce n'est pas sans raison : la gestion de la mémoire allouée dynamiquement (à l'aide de new ou de new[]) a mano est un vrai casse-tête en C++, entre autres, parce que C++ est un langage à exception, et qu'il faut arriver à en tenir compte dans tout ce que l'on fait.

Il faut en effet comprendre qu'un code aussi "simple" que
Code:

1 2 3 4 5 6 7 8 9 int ** mat=nullptr; mat = new int*[10]; for(int i = 0;i<10;++i) mat[i] = new int[10]; /* ... */ for(int i = 0;i<10;++i) delete[] mat[i]; delete mat; mat = nullptr
a beau sembler correct, il n'en reste pas moins profondément buggé et susceptible de provoquer d'énormes fuites mémoires (enfin, pas énormes, dans ce cas, mais elle le deviendront si elle se répètent assez souvent ;) )

Aussi, tu peux me croire sur parole : tu ne tiens pas du tout à essayer de te confronter à l'exercice de la gestion de la mémoire dynamique à la main ;)

Pire, ce genre d'exercice est sans doute très formateur en C, car la gestion de la mémoire en C et la compréhension du concept de pointeurs sont des notions primordiales en C, mais tout exercice similaire en C++ n'est et ne sera jamais qu'un ramassis de conneries qui ne ferait que te donner des habitudes qui ne feront que dresser un mur dans lequel tu t’empresseras de foncer à chaque occasion qui se présentera ;)

Ceci dit, pour ne pas te laisser sans réponse si tu es "assez fou" pour vouloir tenter l'expérience, tu dois impérativement veiller à respecter la règle des trois grands : si, pour une raison ou une autre, tu dois définir toi-même le comportement de l'une des fonctions pour lesquelles le compilateur donne généralement une implémentation de manière automatique que sont le constructeur de copie, l'opérateur d'affectation et le destructeur, alors tu dois veiller à fournir l'implémentation de ces trois fonctions.

Tu as fourni (car tu y était obligé) une implémentation perso du destructeur :question: tu dois donc fournir également une implémentation du constructeur de copie et de l'opérateur d'affectation.

En voici la raison : Reprenons d'abord ton code de base que je rappelle ici :
Code:

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 template<class T> class Node { private: T _value; vector<Node<T>*> children; public: Node(T value); Node(const Node<T>& node); void AddChild(Node<T>* node); T getValue() const; vector<Node<T>*> returnChildren() const; void replaceChildrenByNewOnes(vector<Node<T>*> newChildren); ~Node(); }; template<class T> void Node<T>::replaceChildrenByNewOnes(vector<Node<T>*> newChildren) { children = newChildren; } template <class T> Node<T>::Node(T value) :_value(value) { children.push_back(NULL); } template <class T> Node<T>::Node(const Node& node) :_value(node.getValue()), children(node.returnChildren()) { } template <class T> void Node<T>::AddChild(Node* node) { if (children[0] == NULL) { children.pop_back(); }; children.push_back(node); } template <class T> T Node<T>::getValue() const { return _value; } template <class T> vector<Node<T>*> Node<T>::returnChildren() const { return children; } template <class T> Node<T>::~Node() { for (typename vector<Node<T>*>::iterator it = children.begin(); it != children.end(); it++) { if (*it != nullptr) { delete *it; cout << "Children with value " << (*it)->getValue() << " is deleted" << endl; } } }
Et imaginons une utilisation proche de
Code:

1 2 3 4 5 6 7 8 int main(){ Node<int> n(1); n.addChild(new Node(2)); // !!! risque d'avoir une std::bad_alloc, mais bon... { auto n2(n); // appel du constructeur de copie } // CRACK (1) return 0; //BOUM (2) }
Passons outre du fait que new est toujours susceptible de lancer une exception de type std::bad_alloc si l'allocation de mémoire échoue (on parle d'un monde de bisounours, mais bon) et observons ce qui va se passer...

Lorsque nous atteignons la ligne 5 (auto n2(n);) le constructeur de copie implémenté automatiquement par le compilateur est appelé. Ce constructeur de copie va effectuer une copie "membre à membre" de notre noeud.
C'est à dire qu'il va appeler le (pseudo)constructeur de copie pour Node<int>::_value, qui ne posera aucun problème, puis il va appeler le constructeur de copie pour Node<int>::children. Sauf qu'un pointeur n'est en réalité qu'une variable de type entier (généralement non signée) qui a la particularité de représenter l'adresse à laquelle on espère trouver un objet du type indiqué.

Du coup n2::children et n::children sont deux tableau qui contiennent des pointeurs représentant exactement les mêmes adresses mémoire. Ce qui fait que quand on arrive en (1) (à la ligne 6), le destructeurs de Node<int> est appelé pour n2, vu que l'on quitte la portée dans laquelle n2 est déclaré et le destructeur va, en brave petit soldat, appeler delete pour toutes les adresses mémoire que n2::children contient.

Jusque là, il n'y a encore "rien de mal" qui a été fait... tant que l'on n'essaye pas d'accéder à un des noeuds contenus dans n::children car les adresses mémoire que n::children contient sont devenues invalides (la mémoire en question a été libérée)

Si bien que si tu pouvais faire un n.children[0]->value = XXX, l'adresse mémoire représentée par n.children irait modifier de la mémoire qui... n'appartient plus à l'application :P

De même, lorsque l'on arrive en (2) (à la ligne 7), le destructeur de n est lui aussi appelé, parce qu'on sort de la portée dans laquelle la variable n a été déclarée. Or, le destructeur de n, il a un job à faire : il doit invoquer delete sur chaque pointeurs que contient son membre children.

Pas de bol, l'adresse mémoire représentée par ces pointeurs a déjà été libérée lorsque n2 a été détruit :P on assiste donc à une tentative de double libération de la mémoire, et ca, c'est quelque chose qui ne sera jamais accepté.

Donc, si tu veux que la fonction main que je viens de te montrer fonctionne correctement, tu dois fournir une implémentation perso du constructeur de copie de ta classe Node. Et cette implémentation prendrait la forme de
Code:

1 2 3 4 5 6 template <typename T> Node<T>::Node(Node<T> const & other): _value(other.value){ for(auto const & it : other.children){ addChild(new Node<T>(it._value); } }
Cela permettrait à la fonction main que je viens de te présenter de fonctionner... Chouette!... Sauf que... un code proche de
Code:

1 2 3 4 5 6 7 8 9 10 int main(){ Node<int> n(1); n.addChild(new Node(3)); // !!! risque d'avoir une std::bad_alloc, mais bon... { Node<int> n2(1); n2.addChild(new Node(2)); // !!! risque d'avoir une std::bad_alloc, mais bon... n = n2; // fuite mémoire(1) } // CRACK (2) return 0; //BOUM (3) }
posera lui aussi un certain nombre de problème car c'est l'opérateur d'affectation qui est appelé à la ligne 6 et que l'implémentation que le compilateur a donné de cet opérateur d'affectation se contente d'appeler l'opérateur d'affectaion "membre à membre".

Ce ne sera pas un problème pour le membre n2._value, mais par contre, pour le membre n2.children... :
primo, on va perdre l'adresse mémoire de n2.children[0] sans l'avoir libéré, ce qui provoquera un fuite mémoire
secundo l'opérateur d'affectation de std::vector va se contenter de copier les adresses mémoire représentés par les pointeurs que n.children contient, ce qui nous remet dans une situation de tentative de double libération de la mémoire.

Si on veut corriger le tir, il faut donc fournir notre propre implémentation de l'opérateur d'affectation de Node<T>, et le plus facile pour y arriver est ce que l'on appelle l'idiome "copy and swap".

Cette idiome consiste à travailler en deux temps :
dans le premier temps, on crées simplement une copie de l'élément transmis en paramètre. C'est relativement simple, vu que l'on a fournit une implémentation correcte pour le constructeur de copie
dans le deuxième temps, on va intervertir toutes les donnée de l'objet courant avec les données de la copie que l'on vient d'effectuer.
De cette manière, lorsque le destructeur sera appelé sur la copie, c'est l'adresse représentés par les pointeurs qui se trouvaient à l'origine dans le membre children de l'objet courant qui sera utilisée avec delete, et l'objet courant récupérera les adresses (valides!!!) représentées par les pointeurs qui se trouvaient à l'origine dans le membre copy.children. Et tout le monde sera content ;)

Si bien que nous serions sans doute très bien inspirés de prévoir une fonction qui permette d'intervertir les membres de deux noeuds. Traditionnellement, on appelle cette fonction swap et elle prend la forme de
Code:

1 2 3 4 5 template <typename T> void Node<T>::swap(Node<T> & other){ std::swap(_value, other._value); std::swap(children, other.children); }
A l'aide de cette fonction, l'implémentation de l'opérateur d'affectation devient particulièrement triviale et pourrait ressembler à quelque chose comme
Code:

1 2 3 4 5 6 template <typename T> Node<T> & operator = (Node<T> const & other){ Node<T> copy(other); // on crée la copie swap(other); // on inverse les membres de la copie et de l'objet courant return *this; // on renvoie l'objet courant modifié }
Bien sur, il ne faut pas oublier de fournir les déclaration de ces deux fonctions dans la définition de ta classe ;)

NOTA : je me suis rendu compte, en relisant ton code avec un peu plus d'attention (il a bien fallu, pour pouvoir utiliser l'existant ;) ) que deux remarques très importantes devaient encore être faites :

on ne préfixe JAMAIS QUOI QUE CE SOIT d'un underscore '_'... ce préfixe est réservé à ceux qui implémentent la bibliothèque standard ;)
il faut impérativement veiller définir des règles de nommage strictes et à s'y tenir : les noms de tous les membres d'une classe, par exemple, doivent suivre les mêmes règles. C'est beaucoup plus facile pour s'y retrouver par la suite ;)

11/11/2015, 15h06
Invité
Citation:
Envoyé par koala01

on ne préfixe JAMAIS QUOI QUE CE SOIT d'un underscore '_'... ce préfixe est réservé à ceux qui implémentent la bibliothèque standard
D'où vient cette règle ?
Pour le double underscore, oui mais pour le simple underscore çà m'étonne car j'ai plutôt l'impression que c'est utilisé assez fréquemment pour préfixer les attributs de façon moins lourde qu'avec "m_". De plus, avec l'espace de nom de la classe, il y a peu de risques de conflit.
11/11/2015, 16h17
koala01

Citation:

Envoyé par nokomprendo

D'où vient cette règle ?

De la norme, si mes souvenirs sont bons

Citation:

Envoyé par nokomprendo

Pour le double underscore, oui mais pour le simple underscore çà m'étonne car j'ai plutôt l'impression que c'est utilisé assez fréquemment pour préfixer les attributs de façon moins lourde qu'avec "m_". De plus, avec l'espace de nom de la classe, il y a peu de risques de conflit.

Non, soit on préfix avec m_, soit on suffixe avec _

C'est d'ailleurs la solution que je choisi le plus souvent, pour que les premières lettres soient significatives et donc, pour aider l'intellisense à me donner le bon choix plus rapidement ;)... Enfin, quand je ne code pas tout simplement avec gedit :P
11/11/2015, 17h06
jo_link_noir

__ -> pour les compilos et des mot clef/macros
_ suivit d'une majuscule -> réservé pour les mots clefs et les types à venir (en partie un héritage du C).
_ -> interdit dans le namespace globale.

Dire que le préfixe _ est réservé est une simplification de la règle.

http://cpp.developpez.com/faq/cpp/?p...s-par-la-norme

Pour les mêmes raisons que koala01, je préfère _ en suffixe.
11/11/2015, 17h54
Iradrille

Citation:

Envoyé par jo_link_noir

_ suivit d'une majuscule -> réservé pour les mots clefs et les types à venir (en partie un héritage du C).

Tient, ya rien en C++ de cette forme ?
En C ya _Noreturn, _Generic et peut être d'autres.

Sinon perso je suis un grand fan de "m_" : sous VS avec Visual Assist, m + shift se transforme en "m_" et ça gêne pas l'intellisense. :)
Mais c'est comme tout, simple question d'habitude.
11/11/2015, 18h08
Invité

Ces remarques me font penser le underscore simple est justement un bon préfixe pour les attributs : d'une part on est sûr de ne pas masquer un nom global et d'autre part çà permet à la complétion de sélectionner rapidement les attributs sans polluer le 'm' comme avec le préfixe "m_".
Mais effectivement, c'est une question d'habitude.
11/11/2015, 21h16
jo_link_noir

Citation:

Envoyé par Iradrille

Tient, ya rien en C++ de cette forme ?
En C ya _Noreturn, _Generic et peut être d'autres.

À ma connaissance, il n'y en a pas en C++.
(pour la liste en C: http://en.cppreference.com/w/c/keyword. Il existe aussi des en-têtes pour avoir la forme aplatit (stdalign.h -> #define alignof _Alignof).)

Par contre, la stl l'utilise pour les noms des classes et des membres (_M_* et _S_*).

@nokomprendo: Je n'ai jamais vu d'identifiant préfixé avec underscore + minuscule, je suppose que le risque de conflit est plutôt faible, même dans le namespace global.
Cela dit le underscore simple est obligatoire pour la surcharge de littéraux. Mais du coup, si on suit la norme, il faut les mettre dans un namespace.