C ++ Branching a recursive structure?

Question

I have the following. The structure is prototyped, so it compiles fine.

struct vertexNodeInfo { vector<vertexNodeInfo> node; }; 

I am trying to write an octree thingy. I want to use a recursive function to continue adding a node to each node until I go to a specific point, and at that time the function, and not adding another node, will add the sheet. I want to use memory without adding a node or leaf, if possible.

Templates may help in this situation, but I'm not sure how to use them ...

I don’t think I explained well. Here is the chart:

I have no idea that what I am asking is impossible or too difficult to understand, or just plain stupid, but I cannot figure it out on my own. I'm sorry that I can’t explain it better.

I am using C ++ 98/03 (VC ++ 2008) and cannot use C ++ 11

Any help at all would be greatly appreciated.

ADDITIONAL INFORMATION:

Best explanation: I want an array of an array of an array of data array. Using memory is very important in this (I store several million items, so one byte is of the utmost importance). Each array can contain another 8 arrays, but until I use it, I want each of the arrays to not use memory. This is a kind of octet.

ADDITIONAL INFORMATION:

Here is another diagram. It is a bit large, so you may need to right-click it and select Open image in new tab to make it readable.

What I don’t do is “brown” (red + green) boxes, where each field reserves memory for both more nodes and leaf data. It will require too much memory for my needs.

This is basically what I'm trying to achieve, depicted as 2D for simplicity:

Answer 1

Without any (manual) heap allocation ^[1] :

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

I know that options come with their “complexity”, but memory is saved and manual memory management is avoided.

Now, to get closer to your stated optimization goals, you can use std::array<T, 8> instead of std::vector or maybe just make vector using a custom allocator to allocate from the memory pool.

Example program (see Live on Coliru ):

 #include <iostream> #include <boost/variant.hpp> #include <vector> struct NodeInfo { int id; }; using Tree = boost::make_recursive_variant< NodeInfo, std::vector<boost::recursive_variant_> >::type; // for nicer code: using Branch = std::vector<Tree>; 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"; } 

Print

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

---

^[1] (outside of using std :: vector)

Answer 2

Basic octet structure

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

If you desperately need a few extra bytes on leaf nodes (and lose a few bytes on non-leaf nodes), you can try using a pointer to an array of subnodes rather than holding it by value.

Now, if T is a point, you can leave using boost :: variant to store only items or subnodes , because each point is guaranteed to exist in exactly one sub-sub, and you can choose an arbitrary cut-off point between the presence of items and the presence subnodes .

Otherwise, if T is a kind of bounding box, you cannot get away from this, because bounding fields that do not fully fit into any of the subnodes must be included in the items list, so the items list must exist regardless whether or not subnodes exist.

What I'm also going to say is that if you desperately need to optimize time or space, you should seriously study user memory allocation procedures.

Edit: Yes, I used an array of pointers, not a pointer to an array. Long and short - the description of the correct initialization of this array without any strong support for C ++ 11 is a complete bitch and in my personal use, this did not justify the serious problems that I actually did, damn it. You can try std::unique_ptr<std::array<Node>, 8> if you want. Theoretically, this should be the best choice.

Answer 3

What about polymorphism?

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

You can find the rest (virtual members of TreeElem).

PS: if it's more than trivial, use smart pointers.

Answer 4

Check out the che composite template and you can easily adapt it to perform octets. After that, create a recursive function that takes the actual depth of the octet as an argument, so you can do what you want. Unfortunately, I do not understand your question well, so I cannot be more precise.