Loi de Demeter

Version imprimable

03/01/2017, 17h57
Seabirds

Loi de Demeter
Salut à toutes et à tous, une belle et heureuse année 2017 ! :lahola:

Je me pose des questions sur ce bout de code :
Code:

1 2 3 4 auto forest = simulator.simulate(); assert(forest.at(x0).size() == 1); assert(forest.at(x0).at(0)->get_data() == 0);
Il faut finalement se rappeler que forest a pour type std::map<position_type, std::vector<std::unique_ptr<Tree<Data>>>>

Je n'aime pas trop le fait d'exposer tous ces détails (preuve en est que j'ai buggé sur les lignes en les relisant). Me confirmez-vous que c'est pas bien (même si c'est surtout des dépendances entre type de la STL) ? :aie:

J'hésite à faire une classe dédiée Forest, mais j'ai toute de même besoin d'effectuer des traitements sur les différentes "couches" d'implémentation (tous les arbres, toutes les données de tous les arbres, les arbres à une position donnée...), et j'ai du coup peur de me perdre en parcourant la Forest (fallait que je la case, désolé :mrgreen: ).

En fait j'ai peur de perdre du temps à dupliquer dans la classe Forest la sémantique qu'on peut attendre d'une map de vecteurs.

Puis-je avoir votre ressenti ?

Bien à vous,
03/01/2017, 19h39
bacelar

Citation:

J'hésite à faire une classe dédiée Forest

N'hésites pas, type "STL" bien trop complexe et donnant accès a plein de chose qui n'ont potentiellement aucun sens dans ton cas.
Tu auras aussi de mettre une API bien plus lisible, ajouter les pré et post condition, etc...

Tu ne dois pas encore utiliser énormément de primitive de map et de vector, donc change ~~temps~~ tant qu'il est temps.
Le type "STL", fait en un champ privée et l'implémentation initiale sera écrite en 1 ligne.

En plus, faire le test de la bascule, c'est 2 minutes.

Bonjour et bonne année.

A moins que Tree<Data> ait des classes dérivées, tu n'as pas besoin de std::unique_ptr.
A part ça, un type nu de la forme std::map<Key, std::vector<Value>> peut potentiellement contenir des vecteurs vides. Si on veut imposer comme invariant qu'aucun de ces vecteurs n'est vide, il vaut peut-être mieux encapsuler ce type dans une classe ou choisir un autre type.

Je propose deux solutions :

Solution rapide mais risquée si on a besoin de changer l'implémentation :

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
#ifndef INCLUDE__MY_PROJECT__FOREST__H
#define INCLUDE__MY_PROJECT__FOREST__H
 
// ...
#include <map>
 
namespace my_project {
 
typedef std::multimap<position_type, Tree<Data>> Forest;
 
/*!
 * \file Forest.h
 * \warning Plus tard, la définition du type Forest pourrait avoir une forme proche de :
\code
 
class Forest {
private:
        std::unordered_map<position_type, std::vector<Tree<Data>>> m_data;
public:
        typedef std::pair<const position_type&, Tree<Data>&> value_type;
        class iterator {
        public:
                value_type& operator*();
                // ...
        };
        class const_iterator {
                // ...
        };
        // ...
};
 
\endcode
 * Donc écrivez "Forest" au lieu de "std::multimap<position_type, Tree<Data>>"
 * et ne supposez pas que les éléments sont rangés par ordre croissant des clés.
 */
 
} // namespace my_project
 
#endif

Solution un peu plus lente à court terme mais sécurisée : créer une classe Forest. Exemple incomplet :

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
#ifndef INCLUDE__MY_PROJECT__FOREST__H
#define INCLUDE__MY_PROJECT__FOREST__H
 
// ...
#include <map>
#include <vector>
 
namespace my_project {
 
class Forest {
private:
	/*!
         * \warning "std::map" pourrait être changé plus tard en "std::unordered_map"
         *          ou en "std::unordered_multimap".
         */
	std::map<position_type, std::vector<Tree<Data>>> m_data;
public:
	class iterator {
	public:
		Tree<Data>& operator*();
		// ...
	};
	class const_iterator {
		// ...
	};
	iterator begin();
	iterator end();
	// ...
};
 
} // namespace my_project
 
#endif

04/01/2017, 15h09
Seabirds

Merci de vos réponses, direction la forêt ! :mrgreen:

Citation:

Envoyé par Pyramidev

A moins que Tree<Data> ait des classes dérivées, tu n'as pas besoin de std::unique_ptr.

Mhhh c'est là qu'on va avoir l'occasion de peut-être exploser un de mes choix d'implémentation :D . Les noeuds de l'arbre ont sémantique d'entité, et lors de la construction de l'arbre, pour éviter d'avoir des soucis (comme un noeud qui serait son propre enfant ou d'avoir des enfants dupliqués), j'ai choisi d'utiliser des std::unique_ptr pour n'avoir qu'une seule représentation du noeud. Du coup pas de souci ( pour l'instant en tout cas, mais vous allez passer par là... ;) ) : si il est déjà dans la topologie on va pas pouvoir le ré-utiliser puisque les insertions de parents ou d'enfants se font seulement par des std::unique_ptr.
Est-ce que ça se tient ? :calim2:

Pour le reste c'est la première fois que je vois des iterators définis à l'intérieur des classes (je me contentais de transférer les itérateurs des membres via une méthode begin() ou end() :pastaper: ), donc je suis en train de faire un peu de doc avant de revenir vers vous :)
04/01/2017, 15h35
ternel

On en avait déjà causé. C'est la différence entre le fond et la forme.
std::map<Key, std::vector<Value>>, c'est la forme de la donnée. Cela concerne les aspects techniques de l'utilisation de la forêt.
Forest est le fond de ta donnée: sa signification réelle.

Le code qui se sert de ta forêt n'est normalement intéressé que par sa signification: c'est une forêt.
Le code concerné par le choix map ou multimap ou autre, c'est le code technique dont dépend le précédent. C'est en fait le code interne de la forêt.

D'une manière générale, plus que la loi de Demeter, c'est l'essence même de l'abstraction qui résonne là.
Séparer l'interface significative de l'implémentation technique, c'est, en C++, définir des classes (ou des fonctions).
04/01/2017, 15h46
Seabirds

Citation:

Envoyé par ternel

On en avait déjà causé.

Argh désolé, au temps pour moi, je ne me souvenais pas avoir parlé précisément de ce cas là, maintenant ça me revient. Nos discussions sont si denses en informations que je soupçonne le système d'archivage de mon cerveau d'être totalement dépassé (en voilà un qui gère pas bien ses pointeurs...), surtout si les infos sont orales x)
Merci pour ton rappel en tout cas ;)

Citation:

Le code qui se sert de ta forêt n'est normalement intéressé que par sa signification: c'est une forêt.
Le code concerné par le choix map ou multimap ou autre, c'est le code technique dont dépend le précédent.

Evidemment, dit comme ça... de réponse en réponse ma question devient de plus en plus sotte :whistle:
04/01/2017, 16h55
ternel

Citation:

Envoyé par Seabirds

Evidemment, dit comme ça... de réponse en réponse ma question devient de plus en plus sotte :whistle:

La plus sotte des questions est encore celle qu'on ne pose pas.
Mieux vaut un bon rappel qu'un doute teinté de honte :mrgreen:
04/01/2017, 20h23
Pyramidev

@Seabirds : Peux-tu donner plus de détails sur l'implémentation de ton modèle de classe Tree ?

Bien sur Pyramidev. Dans le doute du degré de précision que tu attends, je vais mettre le code (il me semble qu'il existe déjà dans un autre fil de discussion :) )
L'idée d'utilisation de la classe Node était de partir d'une forêt initiale, constituées d'arbres renfermant des données (classe Node<Data>), arbres que l'on rebranche progressivement les uns aux autres au cours d'un processus. Les noeuds parents sont donc créés progressivement au cours du processus. Au bout d'un certain dans le processus s'arrête, et on utilise des algorithmes de parcours pour modifier les données des arbres restants selon les caractéristiques de leur topologie. La classe Node ci-dessous permet normalement de regrouper les services requis par ce contexte d'utilisation ( :question: ). Cela ne sera pas sans évoquer des souvenirs à pas mal de gens que j'ai déjà embêté pleeeein de fois à ce sujet :toutcasse:

Le header (les définitions de make_node en bas ne devraient pas être dans le header, c'est à changer :? )

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
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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
#ifndef __NODE_H_INCLUDED__
#define __NODE_H_INCLUDED__
 
#include <stdexcept> // logic_error
#include <vector>
#include <queue>
#include <memory>
 
template<typename T>
class Node;
 
template<typename T, typename ...Args>
std::unique_ptr<Node<T>> make_node(Args&& ...args);
 
template<typename T, typename ...Args>
std::unique_ptr<Node<T>> make_node(std::vector<std::unique_ptr<Node<T>>>&& children, Args&& ...args);
 
template <typename T>
class Node{
 
public:
	using data_type = T;
	~Node() = default;
 
 
	/*************************
        / Parent tracking
        *************************/
	bool has_parent() const;
 
	Node<T> const& get_parent() const;
	Node<T> & get_parent();
 
 
	/*************************
        / Children tracking
        *************************/
	bool has_children() const;
 
	/*************************
        / Data access
        *************************/
	T const& get_data() const;
	T& get_data();
 
 
	/*************************
        / Topology edition
        *************************/
 
	template <typename... Args>
    Node<T> & make_child(Args&&... args );
 
    Node<T> & add_child(std::unique_ptr<Node<T>>&& child);
 
	/*************************
        / Tree traversal
        *************************/
	template<typename Treatment>
	void pre_order_DFS(Treatment const& v) const ;
 
	template<typename Treatment>
	void leaves(Treatment const& v) const ;
 
	private:
 
	Node() = default;
    Node(const Node&) = delete;
    Node& operator=(const Node&) = delete;
 
    template <typename... Args>
    Node(Args&&... args );
 
    template <typename... Args>
    Node(std::vector<std::unique_ptr<Node<T>>>&& children, Args&&... args );
 
    template <typename T1, typename ...Args>
    friend std::unique_ptr<Node<T1>> make_node(Args&& ...args);
 
    template <typename T1, typename ...Args>
    friend std::unique_ptr<Node<T1>> make_node(std::vector<std::unique_ptr<Node<T1>>>&& children, Args&& ...args);
 
	Node<T>* m_parent = nullptr; // inexistence possible
	std::vector<std::unique_ptr<Node<T>>> m_children;
	T m_data;
 
};
 
 
template <typename T>
bool Node<T>::has_parent() const{
	return m_parent;
}
 
template <typename T>
Node<T> const& Node<T>::get_parent() const{
	if( ! has_parent() )
		throw std::logic_error("no existing parent");			
 
	return *m_parent;
}
 
template <typename T>
Node<T> & Node<T>::get_parent() {
	if( ! has_parent() )
		throw std::logic_error("no existing parent");			
 
	return *m_parent;
}
 
 
/*************************
/ Children tracking
*************************/
template <typename T>
bool Node<T>::has_children() const{
	return !m_children.empty();
}
 
/*************************
/ Data access
*************************/
template <typename T>
T const& Node<T>::get_data() const{
	return m_data;
}
 
template <typename T>
T& Node<T>::get_data() {
	return m_data;
}
 
 
/*************************
/ Topology edition
*************************/
template<typename T>
template <typename... Args>
Node<T> & Node<T>::make_child(Args&&... args ) {
	auto ptr = make_node<T>(std::forward<Args>(args)...);
	ptr->m_parent = this;
    m_children.push_back(std::move(ptr));
    return *(m_children.back());
}
 
template <typename T>
Node<T> & Node<T>::add_child(std::unique_ptr<Node<T>>&& child){
	if( child->has_parent()){
		throw std::logic_error("child already has a parent");
	}
	child->m_parent = this;
	m_children.push_back(std::move(child));
	return *(m_children.back());
}
 
/*************************
/ Tree traversal
*************************/
template <typename T>
template<typename Treatment>
void Node<T>::pre_order_DFS(Treatment const& v) const {
	v(this->get_data());
	for(auto const& it : this->m_children){
		it->pre_order_DFS(v);
	}
}
 
template <typename T>
template<typename Treatment>
void Node<T>::leaves(Treatment const& v) const {
	if(has_children()){
		for(auto const& it : this->m_children){
			it->leaves(v);
		}
	}else{
		v(this->get_data());
	}
}
 
template<typename T>
template <typename... Args>
Node<T>::Node(Args&&... args ) : m_data(T(std::forward<Args>(args)...)) {}
 
template<typename T>
template <typename... Args>
Node<T>::Node(std::vector<std::unique_ptr<Node<T>>>&& children, Args&&... args ) : m_children(std::move(children)), m_data(T(std::forward<Args>(args)...)) {
	for(auto & it : m_children){
		it->m_parent = this;
	}
}
 
template <typename T, typename ...Args>
std::unique_ptr<Node<T>> make_node(Args&& ...args){
	return std::unique_ptr<Node<T>>(new Node<T>(std::forward<Args>(args)...));
}
 
template <typename T, typename ...Args>
std::unique_ptr<Node<T>> make_node(std::vector<std::unique_ptr<Node<T>>>&& children, Args&& ...args){
	return std::unique_ptr<Node<T>>(new Node<T>(std::move(children), std::forward<Args>(args)...));
}
 
#endif

Et le fichier de test

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
// compiles with g++ -o test Node_test.cpp -std=c++14 -Wall
 
#include "Node.h"
#include "assert.h"
#include <vector>
#include <iostream>
 
struct Sum
{
	Sum(int a, int b, int c) : x(a+b+c) {}
	int x;
};
 
int main(){
 
	/***************************
        Constructors
        ***************************/
	auto a = make_node<int>(0);
	assert(a->get_data() == 0);
 
	auto z = make_node<Sum>(10,20,30);
	assert(z->get_data().x == 60);
 
	/**************************
        Adding topology
        **************************/
	/*           0
	            /\ \ 
	           1  3  4
	          /      \ \
	         2       5  6
	*/
 
	// Root -> Leaves construction
	a->make_child(1).make_child(2);
	Node<int>& d = a->make_child(3);
	assert(d.has_parent());
 
	// Leaves -> Roots construction
	auto f = make_node<int>(5);
	auto g = make_node<int>(6);
	std::vector<std::unique_ptr<Node<int>>> children;
	children.push_back(std::move(f));
	children.push_back(std::move(g));
 
	auto e = make_node<int>(std::move(children), 4);
 
	assert( (!f.get()) && !g.get()); // unique_ptr are now empty
 
	//Rebranching
	a->add_child(std::move(e));
	assert( !e.get());
 
	/***************************
        Using traversals
        ****************************/
 
	// Depth First Search
	std::vector<int> expected_data = {0,1,2,3,4,5,6} ;
	std::vector<int> v;
 
	auto treatment = [&v](int x){ v.push_back(x); };
 
	a->pre_order_DFS(treatment);
 
	assert(v == expected_data);
 
 
	// Leaves treatment
	std::vector<int> expected_children_data = {2,3,5,6};
	std::vector<int> children_data;
	auto accumulate = [& children_data](int x) { children_data.push_back(x); };
	a->leaves(accumulate);
	assert(children_data == expected_children_data);
 
	return 0;
}

Cela te permet il d'y voir plus clair ? As-tu besoin de plus d'infos ?

05/01/2017, 21h49
Pyramidev
Tree<Data> est-il :
1. un alias de Node<Data> ?
2. une classe qui encapsule un Node<Data> ?
3. une classe qui encapsule un std::unique_ptr<Node<Data>> ?
4. ou bien autre chose ?
Dans les deux premiers cas, Tree<Data> n'est pas déplaçable (pas de constructeur de mouvement ni d'affectation de mouvement), donc je comprends que tu le ranges dans un std::unique_ptr que tu peux déplacer.
06/01/2017, 00h18
Seabirds

C'est bien un alias de Node<Data>, je ne l'ai pas dit assez clairement, mes excuses. J'ai écrit Tree dans les premiers messages pour que le lien soit plus clair avec la classe Forest, mais dans le code la classe s'appelle Node.

Citation:

Envoyé par Pyramidev

Dans les deux premiers cas, Tree<Data> n'est pas déplaçable (pas de constructeur de mouvement ni d'affectation de mouvement), donc je comprends que tu le ranges dans un std::unique_ptr que tu peux déplacer.

Est-ce une bonne chose ou veux-tu dire que unique_ptr devient superflu si on rendait Tree<Data> (ie Node<Data>) déplaçable ? J'avais cru comprendre que les classes déplaçables étaient cool pour gérer les ressources internes à la classes. Lorsque j'ai implémenté la classe Node, j'avais plutôt en tête une phrase que j'avais lu dans un article dont une traduction pourrait être "l'identité du unique_ptr se confond avec celle de l'objet pointé".

Avec un arbre déplaçable et/ou copiable, il faut mettre à jour récursivement les pointeurs vers les parents :

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
/*!
 * \tparam CellT Cell type. The requirements that are imposed on CellT
 *               depend on the actual operations performed on Tree<CellT>.
 */
template<class CellT>
class Tree
{
private:
	typedef Tree<CellT> SelfType;
 
	SelfType*             m_parent;
	CellT                 m_cell;
	std::vector<SelfType> m_children;
 
public:
	//! \remark CellT must be copy constructible.
	Tree(const SelfType& other);
 
	//! \remark CellT must be move constructible.
	Tree(SelfType&& other) noexcept(std::is_nothrow_move_constructible<CellT>::value);
 
	//! \remark CellT must be copy constructible and move assignable.
	SelfType& operator=(const SelfType& other);
 
	//! \remark CellT must be move assignable.
	SelfType& operator=(SelfType&& other)
		noexcept(std::is_nothrow_move_assignable<CellT>::value);
 
	// ...
};
 
template<class CellT>
Tree<CellT>::Tree(const SelfType& other) :
	m_parent(nullptr), m_cell(other.m_cell), m_children(other.m_children)
{
	for(Tree<CellT>& child : m_children)
		child.m_parent = this;
}
 
template<class CellT>
Tree<CellT>::Tree(SelfType&& other)
	noexcept(std::is_nothrow_move_constructible<CellT>::value) :
	m_parent(nullptr), m_cell(std::move(other.m_cell)), m_children(std::move(other.m_children))
{
	for(Tree<CellT>& child : m_children)
		child.m_parent = this;
}
 
template<class CellT>
Tree<CellT>& Tree<CellT>::operator=(const SelfType& other)
{
	Tree<CellT> otherCopy(other);
	*this = std::move(otherCopy);
	return *this;
}
 
template<class CellT>
Tree<CellT>& Tree<CellT>::operator=(SelfType&& other)
	noexcept(std::is_nothrow_move_assignable<CellT>::value)
{
	m_cell     = std::move(other.m_cell);
	m_children = std::move(other.m_children);
	for(Tree<CellT>& child : m_children)
		child.m_parent = this;
	return *this;
}

Dans ce cas, std::unique_ptr devient superflu et on gagne en performances.
Mais, d'un autre côté, le code de Tree devient plus difficile à analyser.

06/01/2017, 14h28
Seabirds

Wooooh 8O ("léger" pincement au coeur à l'idée de tout ce qui me reste à apprendre :mur: )

Citation:

Mais, d'un autre côté, le code de Tree devient plus difficile à analyser.

ça j'ai bien compris ... :mouarf:

Citation:

on gagne en performances.

pour ça par contre, j'ai du mal à comprendre pourquoi (connaissances limitées...). Où est ce que l'utilisation du unique_ptr est un peu coûteuse (et pourquoi pour la même opération ta solution l'est moins) ? :)

Merci en tout cas ! :)
06/01/2017, 17h21
Pyramidev
Par rapport à une donnée de type T, le principal coût ajouté par std::unique_ptr<T> vient du fait qu'il ne contient pas une donnée de type T sur place mais ailleurs, dans la mémoire dynamique.
Cela se traduit par une allocation supplémentaire.

Par exemple, quand tu écris :
Code:

1 2 3 4 template <typename T, typename ...Args> std::unique_ptr<Node<T>> make_node(Args&& ...args){ return std::unique_ptr<Node<T>>(new Node<T>(std::forward<Args>(args)...)); }
new Node<T>(std::forward<Args>(args)...) appelle operator new(sizeof(Node<T>)) pour réserver de la place dans la mémoire dynamique puis y construit l'objet en appelant le constructeur de Node<T> avec les paramètres std::forward<Args>(args)....
06/01/2017, 17h34
Seabirds

Je comprends ! Merci de ta réponse ! :D

Je vais garder mon implémentation pour l'instant parce qu'il faut que j'avance urgemment sur d'autres points, mais dès que j'ai l'occasion je remet un coup de polish :)

D'ailleurs merci à vous tous de vos réponses, je vais mettre le sujet comme étant résolu !
09/01/2017, 20h47
Pyramidev

De rien.

Citation:

Envoyé par Pyramidev

Avec un arbre déplaçable et/ou copiable, il faut mettre à jour récursivement les pointeurs vers les parents

Plus précisément, seule la copie est récursive.
Avec mon implémentation, le constructeur de mouvement de Tree<CellT> n'est pas récursif, car le constructeur de mouvement de std::vector ne fait que s'approprier le contenu de l'autre std::vector sans changer de place ce contenu.
Donc le constructeur de mouvement de chaque enfant de type Tree<CellT> n'est pas appelé (et n'a pas besoin de l'être).
10/01/2017, 10h16
Seabirds

Citation:

Envoyé par Pyramidev

Donc le constructeur de mouvement de chaque enfant de type Tree<CellT> n'est pas appelé (et n'a pas besoin de l'être).

Cool c'est ce qu'il me semblait avoir compris, même si je n'en étais pas sûr et que ta précision est bienvenue ! :)
Peut-être que l'incorporation de la sémantique de mouvement va se faire un peu plus tôt que prévu, parce que je commence à avoir des unique-ptr qui glissent leur nez un peu partout ;)
Merci encore !
13/01/2017, 18h44
Seabirds

Je reviens après quelques apnées RTFM dans la sémantique de mouvement.

Admettons que je ne veuille pas que l'arbre soit copiable, je n'ai a priori aucun risque de le préciser dès maintenant ( :question: ) en déclarant delete le constructeur par copie et l'affectation par copie : au pire si j'en ai besoin plus tard, je les définirai à ce moment là ( :question: )

Je me retrouve du coup avec seulement le constructeur par mouvement et l'affectation par mouvement, avec charge au code client d'utiliser std::move pour convertir un arbre en référence rvalue, ce qui signale au reste du code client qu'il serait bien imprudent d'utiliser la variable après qu'on lui aie appliqué std::move :question:

Et à priori, si j'utilise les références universelles dans le code client (ce qui devrait arriver lorsque je voudrai faire un perfect forwarding avec des parameter packs), il faudra utiliser std::forward (typiquement dans le code de la forêt qui transmettra les arguments du contexte vers le constructeur de l'arbre) :question:

D'un autre côté, vu que je vais utiliser les arbres avec les containers de la STL, et que les arbres utilisent la sémantique de move, il n'y a pas garantie forte (qui dit que si une exception est lancée en plein milieu d'un algorithme de la STL, tous les arbres retrouvent leur états initiaux d'avant l'appel à l'algorithme). Du coup on attend que le constructeur de mouvement des arbres soit noexcept, ce qui appelle std::terminate à la moindre exception qui serait lancée pendant le mouvement, ce qui d'une certaine sorte est une trèèèès forte garantie qu'aucune instance ne sera jamais laissée dans un état incohérent, puisque tout ce joli monde vient de se tirer une balle dans la tête. :pan:

Est-ce correct ?

Bien à vous,

Citation:

Envoyé par Seabirds

Admettons que je ne veuille pas que l'arbre soit copiable, je n'ai a priori aucun risque de le préciser dès maintenant ( :question: ) en déclarant delete le constructeur par copie et l'affectation par copie : au pire si j'en ai besoin plus tard, je les définirai à ce moment là ( :question: )

Tout à fait.

Citation:

Envoyé par Seabirds

Je me retrouve du coup avec seulement le constructeur par mouvement et l'affectation par mouvement, avec charge au code client d'utiliser std::move pour convertir un arbre en référence rvalue, ce qui signale au reste du code client qu'il serait bien imprudent d'utiliser la variable après qu'on lui aie appliqué std::move :question:

Si tu préfères la sécurité, tu peux faire ça :
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 //! \tparam CellT Cell type. The requirements that are imposed on CellT //! depend on the actual operations performed on Tree<CellT>. //! \remark If a moved-from state is valid for CellT, this also applies to Tree<CellT>. //! template<class CellT> class Tree { private: Tree<CellT>* m_parent; CellT m_cell; std::vector<Tree<CellT>> m_children; bool invariant() const noexcept { return std::all_of(m_children.cbegin(), m_children.cend(), [this](const Tree<CellT>& child) -> bool {return child.m_parent == this;}); } public: //! \warning If other.getParent() != nullptr, the behaviour is undefined. //! \remark requires MoveConstructible<CellT> Tree(Tree<CellT>&& other) noexcept(std::is_nothrow_move_constructible<CellT>::value); //! \warning If other.getParent() != nullptr, the behaviour is undefined. //! \remark requires MoveAssignable<CellT> Tree<CellT>& operator=(Tree<CellT>&& other) noexcept(std::is_nothrow_move_assignable<CellT>::value); const Tree<CellT>* getParent() const noexcept {return m_parent;} Tree<CellT>* getParent() noexcept {return m_parent;} // ... }; template<class CellT> Tree<CellT>::Tree(Tree<CellT>&& other) noexcept(std::is_nothrow_move_constructible<CellT>::value) : m_parent(nullptr), m_cell(std::move(other.m_cell)), m_children(std::move(other.m_children)) { for(Tree<CellT>& child : m_children) child.m_parent = this; other.m_children.clear(); // So other.invariant() == true } template<class CellT> Tree<CellT>& Tree<CellT>::operator=(Tree<CellT>&& other) noexcept(std::is_nothrow_move_assignable<CellT>::value) { m_cell = std::move(other.m_cell); m_children = std::move(other.m_children); for(Tree<CellT>& child : m_children) child.m_parent = this; other.m_children.clear(); // So other.invariant() == true return *this; }
Cela dit, personnellement, je n'ai pas de scrupules à considérer le moved-from state comme un état où, par défaut, seul l'appel au destructeur est fiable. Sinon, dans certains cas, cela réduit les performances.
Il y a une discussion à ce sujet sur Stack Overflow : http://stackoverflow.com/questions/1...n-c11/12095473

Citation:

Envoyé par Seabirds

Et à priori, si j'utilise les références universelles dans le code client (ce qui devrait arriver lorsque je voudrai faire un perfect forwarding avec des parameter packs), il faudra utiliser std::forward (typiquement dans le code de la forêt qui transmettra les arguments du contexte vers le constructeur de l'arbre) :question:

Si les arguments de la fonction qui appelle le constructeur de l'arbre sont des références universelles, alors oui, il faudra les retransmettre au constructeur de l'arbre avec un std::forward.

Citation:

Envoyé par Seabirds

D'un autre côté, vu que je vais utiliser les arbres avec les containers de la STL, et que les arbres utilisent la sémantique de move, il n'y a pas garantie forte (qui dit que si une exception est lancée en plein milieu d'un algorithme de la STL, tous les arbres retrouvent leur états initiaux d'avant l'appel à l'algorithme). Du coup on attend que le constructeur de mouvement des arbres soit noexcept, ce qui appelle std::terminate à la moindre exception qui serait lancée pendant le mouvement, ce qui d'une certaine sorte est une trèèèès forte garantie qu'aucune instance ne sera jamais laissée dans un état incohérent, puisque tout ce joli monde vient de se tirer une balle dans la tête. :pan:

Est-ce correct ?

Oui.
Dans mon code, j'ai été moins strict en mettant noexcept(std::is_nothrow_move_constructible<CellT>::value) au lieu de noexcept tout seul. Mais ta solution semble plus adaptée à tes besoins.

24/02/2017, 00h59
Seabirds

Je me rends compte maintenant seulement que je n'avais pas répondu à ce dernier message :) Merci donc, à toi et aux autres, pour tous ces bons conseils qui m'ont permis d'écrire une classe qui tienne un peu la route. Bon, avouons le, le type horrible initial avait gangrené pas mal de trucs, du coup y'a eu du boulot pour rattraper tout ça (je me laisserai plus avoir par la non-abstraction. Enfin si, évidemment, mais plus aussi naïvement :mouarf: ). Mais maintenant j'ai une jolie classe Foret, peuplée de beaux petits arbres qui rendent tous mes autres algorithmes teeeellement plus naturels !!! :D
:merci: