C ++ Branchement récursif struct?

J’ai le suivant. La structure est prototypée donc elle comstack bien.

struct vertexNodeInfo { vector node; };

J’essaye d’écrire un truc d’octree. Ce que je veux faire est d’utiliser une fonction récursive pour continuer à append un nœud à chaque nœud jusqu’à ce que je descende à un point spécifique, auquel moment la fonction, plutôt que d’append un autre nœud, ajoute une feuille. Je souhaite ne pas utiliser de mémoire lorsqu’il n’y a plus de nœud ni de feuille ajouté si cela est possible.

Les modèles pourraient peut-être aider dans cette situation, mais je ne sais pas comment les utiliser …

Je ne pense pas que je me suis bien expliqué. Voici un diagramme:

structure récursive de branchement

Je ne sais pas si ce que je demande est impossible ou trop confus pour être compris ou tout simplement stupide, mais je ne peux pas le comprendre par moi-même. Je suis désolé de ne pas pouvoir l’expliquer mieux.

J’utilise C ++ 98/03 (VC ++ 2008) et ne peux pas utiliser C ++ 11

Toute aide serait très appréciée.

INFORMATION ADDITIONNELLE:

Meilleure explication: je veux un tableau d’un tableau d’un tableau d’un tableau de données. L’utilisation de la mémoire est très importante à cet égard (je stocke plusieurs millions d’éléments, donc un seul octet fait une énorme différence). Chaque tableau peut contenir 8 tableaux supplémentaires, mais tant que je n’aurai pas besoin de l’utiliser, je souhaite que chacun des tableaux n’utilise pas de mémoire. C’est un octree en quelque sorte.

INFORMATIONS SUPPLÉMENTAIRES:

Voici un autre diagramme. C’est un peu gros, alors vous devrez peut-être cliquer dessus avec le bouton droit de la souris et sélectionner Open image in new tab pour le rendre lisible.

Ce que je ne veux pas, ce sont des boîtes “marron” (rouge + vert), où chaque boîte réserve de la mémoire pour plusieurs nœuds et pour les données de feuille. Cela utiliserait beaucoup trop de mémoire pour mes besoins.

C’est fondamentalement ce que j’essaie de réaliser, illustré en 2D par souci de simplicité:

Exemple 2D de mon idée d'un octree

Sans aucune allocation de tas (manuelle) ^[1] :

 struct NodeInfo { int id; }; using Tree = boost::make_recursive_variant< NodeInfo, std::vector >::type;

Je sais que les variantes ont leur propre “complexité”, mais la localisation mémoire est préservée et la gestion manuelle de la mémoire est évitée.

Pour vous rapprocher de vos objectives d’optimisation, vous pouvez utiliser std::array place de std::vector , ou simplement faire en sorte que le vector utilise un allocator personnalisé à allouer à partir d’un pool de mémoire.

Exemple de programme (à voir en direct sur Coliru ):

 #include  #include  #include  struct NodeInfo { int id; }; using Tree = boost::make_recursive_variant< NodeInfo, std::vector >::type; // for nicer code: using Branch = std::vector; using Leaf = NodeInfo; static std::ostream& operator<<(std::ostream& os, Leaf const& ni) { return os << ni.id; } static std::ostream& operator<<(std::ostream& os, Branch const& b) { os << "{ "; for (auto& child: b) os << child << " "; return os << "}"; } int main() { Branch branch1 { Leaf { 2 }, Leaf { 1 }, Branch { Leaf { 42 }, Leaf { -42 }, } }; Tree tree = Branch { branch1, Leaf { 0 }, branch1 }; std::cout << tree << "\n"; }

Impressions:

 { { 2 1 { 42 -42 } } 0 { 2 1 { 42 -42 } } }

^[1] (en dehors de l'utilisation de std :: vector)

La structure de base de l’octree est

 struct Node { std::vector items; std::array, 8> subnodes; Box BoundingBox; }; class Octree { Node n; //... stuff public: Octree(Box location) : n(location) {} };

Si vous souhaitez quelques octets supplémentaires sur les nœuds feuilles (et quelques octets perdus sur les nœuds non-feuilles), vous pouvez essayer d’utiliser un pointeur sur le tableau de sous-nœuds plutôt que de le conserver par valeur.

Maintenant, si T est un point, vous pouvez utiliser un boost :: variant pour stocker uniquement les items ou les subnodes – subnodes , car il est garanti que chaque point existe dans exactement un sous-noeud, et vous pouvez choisir un sharepoint coupure arbitraire entre avoir des items et avoir des subnodes .

Sinon, si T est une sorte de boîte englobante, vous ne pouvez pas vous en sortir, car les boîtes englobantes qui ne rentrent pas complètement dans l’un des sous-noeuds doivent aller dans la liste des items liste des items doit donc exister indépendamment du fait que il y a des sous-noeuds.

Ce que je vais aussi dire, c’est que si vous souhaitez absolument optimiser le temps ou l’espace, vous devez sérieusement vous pencher sur des routines d’allocation de mémoire personnalisées.

Edit: Oui, j’ai utilisé un tableau de pointeurs plutôt qu’un pointeur sur un tableau. En résumé, décrire la bonne initialisation de ce tableau sans une prise en charge forte de C ++ 11 est une tâche compliquée et, dans mon utilisation personnelle, cela ne justifiait pas les graves problèmes que j’avais rencontrés lors de la fabrication. Vous pouvez essayer std::unique_ptr, 8> si vous le souhaitez. En théorie, ce devrait être le choix supérieur.

Qu’en est-il du polimorphisme?

 struct TreeElem { virtual ~TreeElem() {} }; struct Node : public TreeElem { std::vector _children; }; struct Leaf : public TreeElem { int _value; };

Vous pouvez trouver le rest (membres virtuels de TreeElem).

PS: si c’est plus que sortingvial, utilisez des pointeurs intelligents.

Vérifiez le motif composite et vous pourrez l’adapter facilement pour réaliser un octree. Après cela, créez la fonction récursive qui prend en argument la profondeur d’octree réelle afin de pouvoir effectuer ce que vous voulez. Malheureusement, je ne comprends pas bien votre question et je ne peux donc pas être plus précis.