Initialisation d'un tableau avec constructeurs

Bonjour,

Je cherche a initialiser un simple tableau de données non copiables et sans constructeur par défaut. Exemple :

Code:

---

1 2 3 4 5 6 7 8 9

struct test { test(int i) {} test(const test&) = delete; };   int main() { test tbl[4] {1, 2, 3, 4}; return 0; }

---

Le compilateur (g++) me dit :

Citation:

---

Envoyé par g++

error: use of deleted function test::test(const test&)

---

Il semble donc créer une instance de test pour chaque élément de la liste d'initialisation, puis tente de les copier dans le tableau.

Connaissez-vous un moyen d'éviter cette copie inutile ? Mes recherches sur la toile ont été infructueuses...

NB :

• Je peux utiliser le C++11.
• Je pourrais bien sûr passer par un tableau de pointeurs (nus ou intelligents), mais je trouve ça dommage pour une raison aussi bête...

Je cite http://en.cppreference.com/w/cpp/lan...initialization :

Citation:

---

The effects of aggregate initialization are:
Each array element or non-static class member, in order of array subscript/appearance in the class definition, is copy-initialized from the corresponding clause of the initializer list.

---

éventuellement, avec std::array, mais sinon, tu ne peux pas faire un tableau si tu n'as ni copie ni valeur par défaut.

std::array est un aggregat donc aggregate-initialized.

Bonjour

vector + emplace (ou emplace_back) : http://en.cppreference.com/w/cpp/con...vector/emplace

Mais je sens l'anguille sous roche :)

Salut,

Déjà, si tu crées une structure non copiable, c'est sans doute parce que ta structure a sémantique d'entité, et donc, qu'elle risque de servir de base à une classe dérivée. (les classes / structures ayant sémantique de valeur sont classiquement copiables ;))

Dans cette hypothèse, il est donc cohérent de travailler avec des pointeurs, pour profiter entre autres du polymorphisme ;)

Ce n'est pas parce que tu n'envisages pas pour l'instant de faire dériver une classe de ta classe actuelle que tu n'en éprouveras pas le besoin par la suite, donc, autant prendre les devants, non :question:

A moins, bien sur, que ta classe actuelle ait sémantique d'entité, et, dans ce cas, il est utile de se rappeller la règle des trois grands :

Si tu fournit une implémentation personnelle de l'une des fonctions de base que sont le constructeur de copie, l'opérateur d'affectation ou le destructeur, tu dois fournir une implémentation personnelle pour les deux autres ;)

Dans cette hypothèse, je présume (peut etre à tord) que si tu as décidé de rendre ta classe non copiable, c'est parce qu'elle contient un pointeur pour lequel tu effectues une allocation dynamique de la mémoire, et que tu effectues donc un delete dans ton destructeur.

Cela pourrait justifier le fait que tu veuilles éviter la copie (mais il faudrait d'ailleurs aussi éviter l'affectation, vu que c'est le même combat ;)) sauf que, si ta classe a sémantique de valeur, il n'y a pas grand chose à faire : ta classe doit etre copiable et affectable ;)

L'idée pour arriver à ce résultat est

1. De faire une copie en profondeur du pointeur dans le constructeur de copie
2. De passer par un idiôme "copy and swap" dans l'opérateur d'affectation

(un tour du coté de la FAQ devrait te fournir les informations relatives à ces concepts ;))

Sinon, si ta classe a réellement sémantique d'entité et que tu es sur qu'elle ne sera jamais dérivée (mais peux tu vraiment avoir cette certitude :question:), tu peux toujours te tourner vers la sémantique de mouvement, vu que tu travailles en C++11 ;)

Mais un tableau statique d'élément ne fonctionnera pas, car, pour pouvoir créer un tableau statique, il faut pouvoir initialiser chacun des membres, à moins de recourir à un code proche de

Code:

---

1 2 3 4

Test tab[4]={std::move(Test(1)), std::move(Test(2)), std::move(Test(3)), std::move(Test(4)) };

---

(Et encore, je ne l'ai pas testé :aie:)

Citation:

---

Sinon, si ta classe a réellement sémantique d'entité et que tu es sur qu'elle ne sera jamais dérivée (mais peux tu vraiment avoir cette certitude ), tu peux toujours te tourner vers la sémantique de mouvement, vu que tu travailles en C++11

---

Attention, la sémantique de mouvement fait une copie quand c'est pas possible de déplacer. En l’occurrence, pour un tableau dont les données sont contiguës (et donc on n'a pas le chois de la localisation des données en mémoire après insertion), les données sont forcement copiées.

Concernant la copie avec les valeurs, dans l'absolue c'est vraie. Mais lorsque l'on a des gros tableaux de données à charger pour faire des calculs, s'amuser à copier les données fait toujours un peu mal :aie:
Dans ce cas, ça me parait pas incohérent de forcer l'interdiction de la copie, même si cela ne respecte pas la sémantique de valeur.
A mon avis, la seule chose importante est de respecter la sémantique de valeur au niveau du tableau complet et non de chaque élément

Mais il faut voir exactement où se trouve le problème de perte de performance par copie. J'ai du mal à imaginer qu'un tableau statique sur la pile créé à l'initialisation puisse poser des problèmes de performances.

EDIT :

Code:

---

1 2 3 4

Test tab[4]={std::move(Test(1)), std::move(Test(2)), std::move(Test(3)), std::move(Test(4)) };

---

move sert à rien ici, ce sont déjà des temporaires, donc des rvalues. move sert à convertir une lvalue en rvalue, donc est utile que sur les variables (move ne fait rien sur un temporaire) :

Code:

---

1 2 3 4 5

Test t1 = Test(1); Test t2 = Test(2); Test t3 = Test(3); Test t4 = Test(4); Test tab[4]={ std::move(t1), std::move(t2), std::move(t3), std::move(t4) };

---

Merci pour vos réponses.

Concernant std::vector et emplace, ça revient à créer le tableau de pointeurs sur le tas, avec certes l'avantage que je n'ai pas à gérer la mémoire à la main. Mais c'est probablement le mieux qu'il soit possible de faire j'ai l'impression (quitte à coder une classe maison qui n'ai pas l'overhead de std::vector dû au fait qu'il a une taille variable, où à faire du placement new sur la mémoire pré-allouée).

Quant au fait de faire un std::move() dans la liste d'initialisation, j'avais déjà essayé : ça ne change rien. Pour une raison que j'ignore, le compilateur cherche toujours à faire une copie.

Pour Koala : à la base, ma structure est non copiable tout bêtement car elle contient une référence :) Elle a bien une sémantique d'entité, mais je n'ai aucun intérêt à introduire du polymorphisme (je cherche même à l'éviter !). Voici un exemple plus représentatif de mon code actuel (un quad tree) :

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

struct content_base { virtual ~content_base() {} };   template<typename N> struct node;   template<typename N> struct node_split { node_split(node<N>& self) { // Comment initialiser 'childs' ? } node childs[4]; };   template<typename N> struct node { node(node<N-1>& parent) : parent(parent), content(nullptr), split(nullptr) {} node<N-1>& parent; content_base* content; node_split<N>* split; };   template<> struct node<1> { node() : content(nullptr), split(nullptr) {} content_base* content; node_split<1>* split; };

---

Bien sûr, il y a mille façons d'écrire ce code autrement de façon à rendre le même service et en contournant le problème, mais j'essaye d'écrire le code le plus simple et auto-cohérent possible (i.e. utiliser des références plutôt que des pointeurs, limiter les allocations dynamiques inutiles, ...).
Par exemple, ça a un sens de déclarer content et split comme des pointeurs, puisqu'ils ont le droit de ne pas exister (ils ne peuvent exister en même temps, d'ailleurs). En revanche, tout nœud du quad tree doit avoir un parent valide, déterminé une fois et une seule à la création du nœud, d'où l'intérêt sémantique d'avoir une référence.

Citation:

---

Envoyé par Kalith

Concernant std::vector et emplace, ça revient à créer le tableau de pointeurs sur le tas

---

Euh, non. C'est un tableau sur le tas de ton type

Citation:

---

Envoyé par Kalith

quitte à coder une classe maison qui n'ai pas l'overhead de std::vector dû au fait qu'il a une taille variable

---

A moins de créer une vecteur de vecteur (ce qui n'est pas une bonne chose en général, à remplacer par un tableau 1D), l'overhead sera négligeable.

Citation:

---

Envoyé par Kalith

Quant au fait de faire un std::move() dans la liste d'initialisation, j'avais déjà essayé : ça ne change rien. Pour une raison que j'ignore, le compilateur cherche toujours à faire une copie.

---

J'ai déjà donné l'explication...

Citation:

---

Envoyé par Kalith

Pour Koala : à la base, ma structure est non copiable tout bêtement car elle contient une référence :) Elle a bien une sémantique d'entité, mais je n'ai aucun intérêt à introduire du polymorphisme (je cherche même à l'éviter !). Voici un exemple plus représentatif de mon code actuel (un quad tree) :

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

struct content_base { virtual ~content_base() {} };   template<typename N> struct node;   template<typename N> struct node_split { node_split(node<N>& self) { // Comment initialiser 'childs' ? } node childs[4]; };   template<typename N> struct node { node(node<N-1>& parent) : parent(parent), content(nullptr), split(nullptr) {} node<N-1>& parent; content_base* content; node_split<N>* split; };   template<> struct node<1> { node() : content(nullptr), split(nullptr) {} content_base* content; node_split<1>* split; };

---

---

Plusieurs remarques :
* avec ce code, je comprend mieux le contexte et pourquoi n'utilises pas un vector en interne
* c'est pas parce que ta structure contient une référence qu'elle ne peut pas être copiable (par contre, le fait d'être une entité, oui). Par contre, clairement, ta classe peut être déplacable
* comment veut tu initialiser un noeud en donnant en même temps le parent et les 4 enfants dans le constructeur pour éviter la copie ? (si les enfants sont déjà créé, avec quel parent ils ont été créé ?)
* tu dis ne pas vouloir de polymorphisme, mais tu mets un destructeur virtuel. C'est pas cohérent. Et utiliser la virtualité quand on recherche des perfs, c'est pas top (surtout que c'est très facilement évitable ici, en ajoutant un second type template à node)
* idem pour l'implémentation sous forme de "liste chaînée" de tes quad trees. Tu vas avoir plein d'allocation (pour chaque noeud), la copie semble anecdotique à côté de ça (j'espèce que tu as fait du profiling pour tester si les pertes de perfs provient de l'allocation ou de la copie, sinon, c'est de la premature optimization)
* comme tu te doutes, les gpu ne permettent pas la prog objet (et vu ce que j'ai dit dessus, on ne le fait de toute façon pas). Une meilleure approche est d'implémenter le quad tree dans 1 seul vecteur de taille (1 + 4 + 4*4 + etc. pour N niveaux) (ou 1 vector pour N' niveaux)

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

template<class T> struct node { iterator parent; iterator child[4]; T content; };   template<class T> struct tree { tree(unsigned N) { data.reserve(...); } vector<node<T>> data; }

---

Avec emplace, tu éviteras les copies, l'overheas sera minime, l'allocation idem

Citation:

---

Envoyé par gbdivers

Euh, non. C'est un tableau sur le tas de ton type

---

Mea culpa. Mais on peut quand même faire mieux a priori, avec un tableau sur la pile (cf. ci-dessous).

Citation:

---

Envoyé par gbdivers

A moins de créer une vecteur de vecteur (ce qui n'est pas une bonne chose en général, à remplacer par un tableau 1D), l'overhead sera négligeable.

---

Négligeable peut être, mais c'est une perte qu'on peut éviter sans rien payer en échange, par exemple (pas très beau je te l'accorde) :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

template<typename T, std::size_t N> struct table { table() {} ~table() { for (std::size_t i = 0; i < N; ++i) ((T*)data+i)->~T(); }   template<typename ... Args> T& emplace(std::size_t i, Args&& ... args) { return *(new ((T*)data+i) T(std::forward<Args>(args)...)); }   T& operator[] (std::size_t i) { return ((T*)data)[i]; } const T& operator[] (std::size_t i) const { return ((T*)data)[i]; }   private : typename std::aligned_storage<sizeof(T), std::alignment_of<T>::value>::type data[N]; };

---

(cf. en.cppreference.com)

Citation:

---

Envoyé par gbdivers

c'est pas parce que ta structure contient une référence qu'elle ne peut pas être copiable (par contre, le fait d'être une entité, oui). Par contre, clairement, ta classe peut être déplacable

---

J'ai été un peu rapide, effectivement. En revanche pour le déplacement, en l'état actuel, je suis sceptique. Étant donné qu'une référence ne peut être modifiée après coup, je ne pourrai pas déplacer simplement les enfants : il faudrait que je les re-créé tous, n'est-ce pas ?

Citation:

---

Envoyé par gbdivers

comment veut tu initialiser un noeud en donnant en même temps le parent et les 4 enfants dans le constructeur pour éviter la copie ? (si les enfants sont déjà créé, avec quel parent ils ont été créé ?)

---

Les enfants sont toujours créés après les parents, je ne vois pas le problème. Par exemple avec mon type de tableau ci-dessus, le constructeur devient :

Code:

---

1 2 3 4 5 6 7 8

template<typename N> struct node_split { node_split(node<N>& self) { for (std::size_t i = 0; i < 4; ++i) childs.emplace(i, self); } table<node,4> childs; };

---

... et ça marche parfaitement.

Citation:

---

Envoyé par gbdivers

tu dis ne pas vouloir de polymorphisme, mais tu mets un destructeur virtuel. C'est pas cohérent. Et utiliser la virtualité quand on recherche des perfs, c'est pas top (surtout que c'est très facilement évitable ici, en ajoutant un second type template à node)

---

Je veut éviter le polymorphisme dans la structure de mon quad tree. Ici le polymorphisme n'intervient qu'au niveau des objets contenus dans une feuille de mon arbre, qui sont de toute manière polymorphiques. Je ne peux pas faire mieux.

Citation:

---

Envoyé par gbdivers

idem pour l'implémentation sous forme de "liste chaînée" de tes quad trees. Tu vas avoir plein d'allocation (pour chaque noeud), la copie semble anecdotique à côté de ça (j'espèce que tu as fait du profiling pour tester si les pertes de perfs provient de l'allocation ou de la copie, sinon, c'est de la premature optimization)

---

J'aurai dû être plus explicite là dessus, désolé. Je ne recherche pas les performances absolues (sinon j'aurais utilisé un code existant), mais le code le plus simple et cohérent, ce qui n'est pas la même chose (NB : je ne fais pas ça pour mon boulot, mais pour un projet perso).

Citation:

---

Envoyé par gbdivers

comme tu te doutes, les gpu ne permettent pas la prog objet (et vu ce que j'ai dit dessus, on ne le fait de toute façon pas). Une meilleure approche est d'implémenter le quad tree dans 1 seul vecteur de taille (1 + 4 + 4*4 + etc. pour N niveaux) (ou 1 vector pour N' niveaux)

---

Que vient faire le GPU ici ? J'utilise le quad tree pour récupérer les objets visibles à l'écran, j'obtiens leurs positions, et c'est ça que j'envoie au GPU, rien de plus. Quand au vecteur de taille 1 + 4 + 4*4 + etc., ça tuerait tout l'intérêt du quad tree qui est d'allouer uniquement l'espace qui est effectivement occupé par les objets (ou alors j'ai mal compris ta suggestion, mais si tu veux étendre ton vector au fur et à mesure que le quad tree grandi / rapetisse ... :calim2:).

Pour en revenir au sujet initial, je pense que la solution est la classe que j'ai montré ci-dessus.

A vrai dire, j'allais justement orienter la réflexion dans le sens inverse de gbdivers :aie:


Pour moi, le fait que chaque noeud puisse être mis en relation avec le noeud parent d'une part et (jusqu'à) quatre noeuds enfants d'autres part plaide clairement en faveur d'une sémantique d'entité, même si le polymorphisme n'est pas d'actualité.

En effet, chaque noeud est identifié de manière unique et non ambigüe par ses propres valeurs, et le fait de changer les noeuds auxquels il est rattaché ne provoque pas la création d'un nouveau noeud pour la cause : c'est le même noeud, mais avec des relations différentes ;)

De plus, il n'y a aucun autre moyen de faire en sorte qu'une classe soit mise en relation avec d'autres éléments du même type sans passer par des pointeurs (fussent-ils intelligents) car le compilateur entre dans une récursivité dont il est incapable de sortir.

Ok, je savais qu'ils y avait des anguilles...

Je vais commencer par cette structure de quad tree avec 1 seul buffer.
Pourquoi je parle de GPU. Simplement parce qu'il y a des contraintes sur les GPU (pas d'allocation dynamique, POO faible, recherche de performance) qui fait que l'on a des structures et algo très performants dessus.
En fait, on peut aller plus loin avec le quad tree en virant complètement les nodes et en gardant qu'un vecteur de Content. Pour un arbre de niveau N, la position de chaque node est déterministe, on peut la calculer directement. On sait que le premier node est en data[0], ses enfants en data[1] à data[4], les enfants de data[3] par exemple seront en data[13] à data[14], etc. 1 seule allocation de vecteur, plus d'overhead (sauf les quelques octets du vector, mais on gagne 4 pointeurs par node, 5 si on compte node_split), la mémoire est contiguë (optimisation des caches), etc. L'inconvénient est qu'il peut y avoir des noeuds vide, donc mémoire perdue. Mais si l'arbre est dense et équilibré, la perte due aux noeuds vides sera largement compensé par le gain des 5 pointeurs par node.
Mais c'est un exemple d'implémentation de quad tree qui ne sera intéressante que si les données s'y adapte.

@koala01
Pas de problème, je suis d'accord avec ta réflexion, pour moi aussi, les nodes ont des sémantiques d'entités.

Citation:

---

Envoyé par Kalith

Mea culpa. Mais on peut quand même faire mieux a priori, avec un tableau sur la pile (cf. ci-dessous).

---

Attention. Dans le premier code, le tableau est bien dans la pile. Par contre, dans tes nodes, qui sont alloués dynamiquement, les tableaux ne sont pas de toute façon dans la pile.
Et je ne parlais pas d'utiliser un vector dans chaque node

Citation:

---

En revanche pour le déplacement, en l'état actuel, je suis sceptique. Étant donné qu'une référence ne peut être modifiée après coup, je ne pourrai pas déplacer simplement les enfants : il faudrait que je les re-créé tous, n'est-ce pas ?

---

Déplaçable et modifiable, c'est pas la même chose. Modifier une référence correspond à changer vers quoi elle pointe. Déplacer veut dire que l'on copie simplement l’adresse, la référence pointe toujours vers la même chose.
Ici, sauf erreur de ma part, la référence ne sera pas simplement un alias, mais sera bien équivalent à un pointeur en mémoire et c'est ce pointeur (géré comme une référence) qui sera copié.
Par contre, tu dis que tu utilises une référence pour la garantie apportée. Mais j'ai l'impression que ta référence correspond à this. Si tu déréferences un pointeur pour l'attribuer à une référence, tu perds cette garantie (l'objet pourra être détruit et la référence invalidée)
Pour terminer, le déplacement ici ne sera effectivement pas intéressant, tu auras quand même une copie (les pointeurs sont des build in type)

Citation:

---

Les enfants sont toujours créés après les parents, je ne vois pas le problème.

---

Ok, je n'avais pas compris.

Citation:

---

J'aurai dû être plus explicite là dessus, désolé. Je ne recherche pas les performances absolues (sinon j'aurais utilisé un code existant), mais le code le plus simple et cohérent, ce qui n'est pas la même chose (NB : je ne fais pas ça pour mon boulot, mais pour un projet perso).

---

Je reste sceptique. Pour éviter quelques copies (a priori négligeable devant les allocations), tu dois créer une structure Table qui prend emplace, avec un code, comment dire... :cry: Pour éviter que le premier node ait un pointeur parent, tu créés un template récursif.
Tu fais des demi-optimisations qui complique beaucoup le code, alors que tu recherches un code simple ?

Bref, je sais pas très bien quels sont tes contraintes, je crois que tu as suffisamment d'éléments pour trouver une solution qui correspond à tes besoins. J'espère que tu as fait du profiling avant de t'attaquer à toutes ces petites optimisations, sinon cela veut dire que tu as compliqué ton code pour rien.

Bon courage

Citation:

---

Envoyé par gbdivers

En fait, on peut aller plus loin avec le quad tree en virant complètement les nodes et en gardant qu'un vecteur de Content.

---

Dis moi si j'ai bien compris : dans cette implémentation on alloue un gros tableau de taille ~2^(2*N) ? Ce n'est effectivement intéressant que pour un arbre bien dense (et pas trop profond), et c'est l'exact inverse de ma situation. J'utilise actuellement N=12 (soit ~10 millions de cellules de la plus petite taille possible), et je prévois d'avoir peut être 10 000 voir 100 000 objets au maximum.

Citation:

---

Envoyé par gbdivers

Attention. Dans le premier code, le tableau est bien dans la pile. Par contre, dans tes nodes, qui sont alloués dynamiquement, les tableaux ne sont pas de toute façon dans la pile.

---

Encore une fois c'est moi qui m'exprime mal. À moins d'utiliser une approche comme celle que tu proposes ci-dessus, je n'ai pas d'autre choix que d'allouer mes nodes dynamiquement. Par contre je peux éviter de le faire pour ce tableau de childs. Une solution vraiment toute bête :

Code:

---

1 2 3 4 5

template<typename N> struct node_split { node_split(node<N>& self) : child1(self), child2(self), child3(self), child4(self) {} node child1, child2, child3, child4; };

---

... mais on est obligé de dérouler les boucles à la main (à moins d'utiliser une astuce du genre operator[] (std::size_t i) { return &child1 + i; }, mais est-ce que je ne vais pas me faire avoir avec des histoires d'alignement ?).

Citation:

---

Envoyé par gbdivers

Déplaçable et modifiable, c'est pas la même chose.

---

On est bien d'accord. Ce que je voulais dire, c'est que si tu déplaces une node, alors son adresse va changer. De fait, les références qui trainent sur cette node (dans ses 4 enfants) deviennent invalides. Comme on ne peut pas modifier l'adresse "pointée" par une référence après coup, les nodes enfants sont irrémédiablement invalides, et la seule solution pour s'en sortir est d'en re-créer de nouvelles (et on propage ça jusqu'au fond de l'arbre).

Citation:

---

Envoyé par gbdivers

Par contre, tu dis que tu utilises une référence pour la garantie apportée.

---

C'est plus psychologique qu'autre chose. Il est toujours possible d'avoir une référence invalide (cf. ci-dessus par exemple), ça sera juste un peu plus dur qu'avec un pointeur. En particulier, comme je sais que tout node doit avoir un parent, j'utilise une référence car le compilateur va me forcer à initialiser celle-ci. En utilisant un pointeur, j'aurais pu faire l'erreur d'oublier cette initialisation, ou encore de modifier le parent par la suite alors que ça n'a pas de sens (sauf dans le cas du déplacement, mais ce n'est pas une fonctionnalité que je cherche à avoir de toute façon).

Je vois ça un peu comme le fait d'utiliser const. Ça n'apporte rien question performances, mais ça ajoute des contraintes supplémentaires sur le code qui le rendent plus difficilement faux (de même, on peut toujours contourner const avec des const_cast, mais alors on sait qu'on fait potentiellement une bêtise).

Citation:

---

Envoyé par gbdivers

Je reste sceptique. Pour éviter quelques copies (a priori négligeable devant les allocations), tu dois créer une structure Table qui prend emplace, avec un code, comment dire... :cry:

---

Encore une fois, mon but n'est pas d'éviter une copie. C'est comme ça que j'ai tourné ma question initiale parce que ça simplifiait les choses. Si j'avais copié-collé directement les 400 lignes de code de mon quad tree, je crois que je me serai fait eng...uirlander, et à raison :aie:

Citation:

---

Envoyé par gbdivers

Pour éviter que le premier node ait un pointeur parent, tu créés un template récursif.

---

Mais j'adore les templates, encore plus quand ils sont récursifs :) Plus sérieusement (et même si c'est vrai), il y a bien d'autres raisons pour lesquelles j'utilise les templates, mais elles ne paraissent pas dans ce petit bout de code. En gros, je peux transférer pratiquement tout le conditionnel à la compilation. Le seul test que je me retrouve à faire à l'exécution est "est-ce que ce nœud est vide ?".

Voici un abrégé de ce qui se trouve vraiment dans mon code, où toutes les structures/interfaces sont explicitées. Peut être que les commentaires seront plus clairs que moi :

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

// 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() {} };

---

Par exemple pour atteindre une position donnée :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

template<std::size_t N, std::size_t D> static std::size_t get_id(vec_t& pos) { static const std::size_t half_size = 1 << (D-N-1); auto dx = pos.x/half_size; pos.x -= dx*half_size; auto dy = pos.y/half_size; pos.y -= dy*half_size; return dx + 2*dy; }   template<std::size_t N, std::size_t D> cell& reach(any_cell<N,D>& c, vec_t& pos) { if (!c.split) c.split = std::unique_ptr<split_cell<N,D>>(new split_cell<N,D>(c)); std::size_t id = get_id<N>(pos); return reach(c.split->childs[id], pos); }   template<std::size_t D> cell& reach(any_cell<D,D>& c, vec_t& pos) { return c; }

---

Citation:

---

Envoyé par gbdivers

Bon courage

---

Merci, et également merci pour ton aide !

Pour tout dire, je ne suis pas particulièrement fan de la solution que tu essayes d'implémenter, car cela signifie que le type de node<3> est différent du type de node<4> ou de node<2>, avec tout ce que cela implique dans le sens où tu devras savoir en permanence à quel niveau tu te trouve pour récupérer le noeud de niveau supérieur / inférieur (meme si auto devrait bien t'aider dans ce cas)

Cela implique aussi que c'est tout ton arbre qui devra etre généré à la compilation : si tu prévois un arbre basé sur node<9>, il sera hors de question de rajouter un noeud en niveau 10.

Or, un noeud de niveau 1 est strictement identique à un noeud de niveau 10 dans l'absolu.

Je ne suis pas fan non plus de l'idée de déclarer le noeud parent sous la forme d'une référence car il n'y a, éventuellement, une différence qu'entre un noeud de niveau 0 et tout noeud d'un niveau quelconque dans le sens où le noeud de niveau 0 n'a pas de noeud parent ;)

La meilleure solution pour représenter le fait qu'un membre peut ne pas exister reste pour moi l'utilisation d'un pointeur.

De toutes manières, une fois tes noeud créés, ils devraient avoir sémantique d'entité, ce qui justifierait d'ailleurs le fait qu'il ne soient ni copiable ni assignable : chaque noeud ne devrait exister qu'une et une seule fois en mémoire, identifiable sans doute (outre par son adresse mémoire, s'entend) au travers de la valeur qui identifie de manière unique son content_base.

Par la suite, soit tu considères que les relations parent<-->enfants sont stables (comprend : une fois que tu as définis un enfant / un parent, il n'est plus question d'en changer), soit tu considères que ce genre de relation est "flottante" (comprends : tu peux à tout instant décider de prendre un enfant différent).

Mais cette décision (qui t'appartient, au demeurant) ne intervenir que dans le choix des fonctions publiques exposées par tes noeuds ;):

Si tu envisages d'avoir des relations "coulées dans le béton", tu ne fourniras que des accesseurs ( getChild(int) const, getParent() const ), étant entendu que le seul moyen de définir le parent passe par le constructeur.

Par contre, si tu envisages d'avoir des relation "flottantes", tu devras exposer des comportements (changeChild(int, Node * ) :question: , swapChild(Node*, Node):question:, swapAllChildren :question: ) qui veilleront, si le noeud dispose déjà d'enfant représenté par l'entier indiqué, à modifier le noeud parent en conséquence (comprend : le placer à nullptr pour le premier cité, inverser les deux parent pour les deux autres) ;)

Pour gérer le cas du noeud de niveau 0 n'ayant pas de parent, rien ne t'empêche de fournir un constructeur privé ou protégé l'initialisant à nullptr qui ne serait accessible qu'au travers d'une amitié vis à vis de la classe (ou de la fonction) qui s'occupe de générer le premier noeud, les autres pouvant plus ou moins être générés "à la demande", pour autant que l'on dispose du parent à leur indiquer ;)

Citation:

---

Envoyé par koala01

Cela implique aussi que c'est tout ton arbre qui devra etre généré à la compilation

---

Non : les noeuds sont quand même alloués dynamiquement. Un arbre vierge (construit par défaut), quel que soit D, ne contiendra toujours qu'un seul noeud sans contenu ni enfants. L'arbre se construit alors selon ce qu'on choisi de mettre dedans, et ça se fait bien sûr à l'exécution.

Citation:

---

Envoyé par koala01

si tu prévois un arbre basé sur node<9>, il sera hors de question de rajouter un noeud en niveau 10.

---

Là oui. Et j'y compte bien : dans mon contexte, ça n'aurait pas de sens.

Citation:

---

Envoyé par koala01

Or, un noeud de niveau 1 est strictement identique à un noeud de niveau 10 dans l'absolu.

---

Je suis d'accord, si je voulais faire un code de quad tree générique et multi-purpose, je ne l'aurais certainement pas implémenté de la sorte. Ce sont les contraintes que j'impose de moi-même sur ses capacités qui le rendent atypique, mais aussi plus simple (à mon sens).

Citation:

---

Envoyé par koala01

Je ne suis pas fan non plus de l'idée de déclarer le noeud parent sous la forme d'une référence car il n'y a, éventuellement, une différence qu'entre un noeud de niveau 0 et tout noeud d'un niveau quelconque dans le sens où le noeud de niveau 0 n'a pas de noeud parent ;)

---

Sauf quand on a des classes templates : je peux (et je l'ai fait) spécialiser le noeud 0 de façon à ce qu'il n'ait pas de membre parent, puisque ça n'aurait de toute façon pas de sens.

Citation:

---

Envoyé par koala01

De toutes manières, une fois tes noeud créés, ils devraient avoir sémantique d'entité, ce qui justifierait d'ailleurs le fait qu'il ne soient ni copiable ni assignable : chaque noeud ne devrait exister qu'une et une seule fois en mémoire, identifiable sans doute (outre par son adresse mémoire, s'entend) au travers de la valeur qui identifie de manière unique son content_base.

---

C'est le cas.

Citation:

---

Envoyé par koala01

Par la suite, soit tu considères que les relations parent<-->enfants sont stables (comprend : une fois que tu as définis un enfant / un parent, il n'est plus question d'en changer), soit tu considères que ce genre de relation est "flottante" (comprends : tu peux à tout instant décider de prendre un enfant différent). Mais cette décision (qui t'appartient, au demeurant) ne intervenir que dans le choix des fonctions publiques exposées par tes noeuds ;):

---

Effectivement, dans mon contexte les relations doivent être stables. Un enfant aura toujours le même parent jusqu'à sa destruction. Un parent peut en revanche perdre ses enfants et en refaire d'autres (un peu comme dans la vie, en fait...), mais uniquement par lot de 4. Partant de là, je ne vois pas pourquoi je relâcherais des contraintes sur mon code qui le rendent plus robuste.

J'avais la mauvaise habitude il y a quelques année de toujours vouloir faire le plus générique possible dans toute situation. Ca part d'un bon sentiment (réutilisabilité, c'est joli, etc.), mais en général :

1. c'est plus long à écrire,
2. ça produit souvent du code qui est mille fois plus compliqué qu'il ne le devrait (plus dur de comprendre quand on revient dedans plus tard, on ne sait plus où se trouve l'essentiel qui est noyé dans la masse de features inutiles),
3. et souvent plus lent ou gourmand en mémoire, puisque jamais parfaitement adapté à la situation.

Comme effet secondaire, ça te laisse trop de latitude sur ce que tu peux faire, ça te permet de partir dans trop de directions différentes. En comparaison, un code contraint au maximum ne peut pas être tourné dans tous les sens : il rend un service précis et délimité. Ça aide à avoir les idées claires, je trouve.

Peut être que ça aiderait si je situais le contexte : je code un jeu, dans lequel ce quad-tree et une entité qui représente l'espace (une surface finie et déterminée au lancement de la partie, comme un plateau de jeu). Dans cet espace, j'impose (c'est une règle du jeu) que tous les objets sont de taille 1 (la plus petite cellule du quad-tree) et sont situés exclusivement sur une case du quad-tree.

Je comprend l'idée et les motivations sont bonnes, mais j'ai l'impression au final que tu arrives à quelque chose d'inutilement compliqué (problématique d'initialisation, utilisation de ta propre structure table, utilisation de template récursif...)
Mon bon, c'est ton code :aie:

Citation:

---

Envoyé par Kalith

Je suis d'accord, si je voulais faire un code de quad tree générique et multi-purpose, je ne l'aurais certainement pas implémenté de la sorte. Ce sont les contraintes que j'impose de moi-même sur ses capacités qui le rendent atypique, mais aussi plus simple (à mon sens).

---

Si c'est à but didactique, ma foi, pourquoi pas, mais, si c'est pour un dev qui doit passer en production, j'ai l'impression que tu te fais du mal et tu perds beaucoup de temps pour pas grand chose :aie:

Citation:

---

Sauf quand on a des classes templates : je peux (et je l'ai fait) spécialiser le noeud 0 de façon à ce qu'il n'ait pas de membre
parent, puisque ça n'aurait de toute façon pas de sens.

---

Tout à fait, mais cela résout un problème "mineur" en en amenant un bien plus lourd de conséquence : le fait que node<1> est d'un type strictement différent que node<2> :aie:

Et ca, pour moi, c'est vraiment un bien lourd tribu à payer pour le simple fait de s'éviter un test sur la validité d'un pointeur :aie:

Citation:

---

Effectivement, dans mon contexte les relations doivent être stables. Un enfant aura toujours le même parent jusqu'à sa destruction. Un parent peut en revanche perdre ses enfants et en refaire d'autres (un peu comme dans la vie, en fait...), mais uniquement par lot de 4. Partant de là, je ne vois pas pourquoi je relâcherais des contraintes sur mon code qui le rendent plus robuste.

---

Attention, je ne faisais qu'aborder les deux aspects d'une alternative : si tu veux des contrainte fortes quant aux relations, c'est "s'implement à toi" de veiller à ce qu'aucune fonction n'aille toucher indument à ton pointeur sur le noeud parent (pour le modifier, s'entend ;))

Citation:

---

J'avais la mauvaise habitude il y a quelques année de toujours vouloir faire le plus générique possible dans toute situation. Ca part d'un bon sentiment (réutilisabilité, c'est joli, etc.), mais en général :

1. c'est plus long à écrire,
2. ça produit souvent du code qui est mille fois plus compliqué qu'il ne le devrait (plus dur de comprendre quand on revient dedans plus tard, on ne sait plus où se trouve l'essentiel qui est noyé dans la masse de features inutiles),
3. et souvent plus lent ou gourmand en mémoire, puisque jamais parfaitement adapté à la situation.

---

Attention, je n'ai pas dit de faire du générique à tout prix non plus, j'ai dit que l'utilisation des template pour ton node et ton split_node implique un casse-tête dont tu aurais pu te passer assez facilement, sans perdre en ressources ou en efficactié, ou, en tout cas, sans perte significative ;)

Citation:

---

Comme effet secondaire, ça te laisse trop de latitude sur ce que tu peux faire, ça te permet de partir dans trop de directions différentes. En comparaison, un code contraint au maximum ne peut pas être tourné dans tous les sens : il rend un service précis et délimité. Ça aide à avoir les idées claires, je trouve.

---

Ah, parce que tu trouve que d'avoir une classe Node, une classe split_node et une spécialisation de chacune de ces classes, c'est un code minimum et délimité :question:

L'intention est louable, mais la technique utilisée ici me semble vraiment inadaptée, et je le répète, pour un bénéfice qui me semble bien maigre ;)

Citation:

---

Peut être que ça aiderait si je situais le contexte : je code un jeu, dans lequel ce quad-tree et une entité qui représente l'espace (une surface finie et déterminée au lancement de la partie, comme un plateau de jeu). Dans cet espace, j'impose (c'est une règle du jeu) que tous les objets sont de taille 1 (la plus petite cellule du quad-tree) et sont situés exclusivement sur une case du quad-tree.

---

mais donc, si tu dois faire varier quelque chose, ce n'est pas ton quad-tree, mais... ce que tu vas mettre dessus ;)

La première chose est de ne pas se tromper de cible lorsque l'on veut refactorer quelque chose ;)

Citation:

---

Envoyé par koala01

Si c'est à but didactique, ma foi, pourquoi pas, mais, si c'est pour un dev qui doit passer en production, j'ai l'impression que tu te fais du mal et tu perds beaucoup de temps pour pas grand chose :aie:

---

Ça m'a pris plus de temps d'en discuter avec vous que de l'écrire, ce code :mrgreen:

Citation:

---

Envoyé par koala01

Tout à fait, mais cela résout un problème "mineur" en en amenant un bien plus lourd de conséquence : le fait que node<1> est d'un type strictement différent que node<2> :aie: Et ca, pour moi, c'est vraiment un bien lourd tribu à payer pour le simple fait de s'éviter un test sur la validité d'un pointeur

---

En quoi est-ce un problème ? On ne peut plus faire n'importe quoi ? Mais c'est bien ce que je cherche ! (je taquine un peu, tu l'auras remarqué...)

Citation:

---

Envoyé par koala01

Attention, je ne faisais qu'aborder les deux aspects d'une alternative : si tu veux des contrainte fortes quant aux relations, c'est "s'implement à toi" de veiller à ce qu'aucune fonction n'aille toucher indument à ton pointeur sur le noeud parent (pour le modifier, s'entend ;))

---

Ayant le choix, je préfère qu'il en soit "simplement au compilateur", parce que j'ai tendance à faire plus d'erreur que lui.

Citation:

---

Envoyé par koala01

Ah, parce que tu trouve que d'avoir une classe Node, une classe split_node et une spécialisation de chacune de ces classes, c'est un code minimum et délimité :question:

---

Minimum non, mais je n'ai jamais dit ça (en plus je parlais du service, non du code). Pour te donner un exemple de ce que je veux dire par "délimité", prends les structures que j'ai explicité et essayes de faire une connerie avec (i.e. quelque chose qui n'est pas sensé pouvoir être fait). Ce n'est bien sûr pas impossible, mais à voir le code on sait qu'on fait une connerie (exemple : déréférencer nullptr pour construire une référence, appels explicites des destructeurs, ré-interpréter une référence en pointeur pour modifier l’adresse, etc.). Je pourrais même pousser le bouchon plus loin en rendant privés les constructeurs, et en mettant comme ami le type du noeud parent (seul autorisé à créer un noeud enfant). Je viens de le faire dans mon code tient, très bonne idée merci :mrgreen:

Citation:

---

Envoyé par koala01

mais donc, si tu dois faire varier quelque chose, ce n'est pas ton quad-tree, mais... ce que tu vas mettre dessus ;)

---

Que veux-tu dire par là ?