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
| // Type abstrait pour toute donnée contenue dans le quad tree.
struct content {
virtual ~content();
protected :
// Obligé d'avoir un pointeur nu ici :
// 1) un objet peut changer de noeud (pas de référence)
// 2) un objet n'est pas propriétaire du noeud qui le
// contient (pas de std::unique_ptr)
cell* parent_cell;
};
// Type abstrait pour toute noeud *terminal* du quad tree,
// c'est à dire le plus petit noeud qui peut exister dans l'arbre,
// et les seuls qui sont autorisés à contenir quelque chose.
// L'utilité est de cacher à l'objet contenu le type exact de
// son contenant (il n'a pas à connaitre la taille de l'arbre).
struct cell {
virtual ~cell() {}
private :
// Le noeud est propriétaire de l'objet contenu.
// Il peut ne rien contenir, et son contenu peut
// être déplacé : on utilise un std::unique_ptr.
std::unique_ptr<content> obj;
};
// Type d'un noeud de l'arbre.
template<std::size_t N, std::size_t D>
struct any_cell;
// Cas non terminal (N != D)
template<std::size_t N, std::size_t D>
struct any_cell {
any_cell(any_cell<N-1,D>& parent) : parent(parent) {}
// Un noeud doit avoir un parent, et il ne changera
// jamais : on utilise une référence.
any_cell<N-1,D>& parent;
// Structure contenant 4 enfants.
struct split_cell {
split_cell(any_cell<N,D>& self) {
for (std::size_t i = 0; i < 4; ++i)
childs.emplace(i, self);
}
// Le point qui fait mal...
// Cette structure *doit* contenir 4 enfants.
// Ils ne peuvent pas être déplacés : on n'a
// a priori aucune raison d'utiliser un pointeur
// nu ou intelligent.
table<any_cell<N+1,D>, 4> childs;
};
// Un noeud non terminal peut être subdivisé ou
// non (i.e. il contient 0 ou 4 enfants).
std::unique_ptr<split_cell<N,D>> split;
};
// Cas terminal (N == D)
template<std::size_t D>
struct any_cell<D,D> : public cell {
any_cell(any_cell<D-1,D>& parent) : parent(parent) {}
// Un noeud doit avoir un parent, et il ne changera
// jamais : on utilise une référence.
any_cell<D-1,D>& parent;
// NB : On hérite ici de 'cell' pour masquer à
// l'objet contenu le type exact du noeud qui le
// contient (il n'a pas à connaître la taille de
// l'arbre).
};
// Cas initial (N == 1), racine de l'arbre.
template<std::size_t D>
struct any_cell<1,D> {
any_cell() {}
// Pas de parent
// Un noeud non terminal peut contenir 0 ou 4
// enfants : cf. split_cell.
std::unique_ptr<split_cell<N,D>> split;
};
// Cas particulier un peu inutile, mais pour être complet...
template<>
struct any_cell<1,1> : public cell {
any_cell() {}
}; |
Initialisation d'un tableau avec constructeurs
Envoyé par g++
Répondre avec citation
)
)
A méditer: La solution la plus simple est toujours la moins compliquée
).
Pour éviter que le premier node ait un pointeur parent, tu créés un template récursif.
Partager