C++ Branching recursive struct?

Question

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

struct vertexNodeInfo
{
    vector<vertexNodeInfo> node;
};

I'm trying to write an octree thingy. What I want to do is use a recursive function to continue adding a node to each node until I get down to a specific point, at which time the function, rather than adding another node, adds a leaf. I want to use no memory when there's no further node or leaf added if that's possible.

Maybe templates would help in this situation, but I'm not sure how to use them...

I don't think I've explained myself well. Here's a diagram:

I have no idea if what I'm asking for is impossible or too confusing to understand or just plain dumb, but I can't figure it out on my own. I'm sorry that I can't explain it any better.

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

Any help at all would be much appreciated.

ADDITIONAL INFO:

Better explanation: I want an array of an array of an array of an array of data. Memory usage is very important in this (I'm storing several million elements, so a single byte makes a huge difference). Each array can contain 8 more arrays, but until I need to use it I want each one of the arrays to use no memory. It's an octree of sorts.

MORE ADDITIONAL INFO:

Here's another diagram. It's a little big, so you might need to right click it and select Open image in new tab to make it readable.

What I don't want are "brown" (red+green) boxes, where every box reserves memory for both more nodes and for the leaf data. That would use far too much memory for my needs.

This is basically what I'm trying to achieve, pictured 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 variants come with their own "complexity", but memory locality is preserved and manual memory management avoided.

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

Sample program (see it 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";
}

Prints:

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

---

^[1] (outside the use of std::vector)

Answer 2

The core structure of the octree is

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're desperate for a few extra bytes on the leaf nodes (and a few bytes lost on the non-leaf nodes), you can try using a pointer to the subnodes array rather than holding it by value.

Now, if T is a point, then you can get away with using a boost::variant to store only the items or the subnodes, because each point is guaranteed to exist in exactly one subnode, and you can pick an arbitrary cutoff point between having items and having subnodes.

Else if T is a kind of bounding-box, you cannot get away with this, because the bounding boxes that do not fit completely into any of the subnodes must go into the items list, so the items list must exist regardless of whether or not there are subnodes.

What I'm also going to say is that if you're desperate for either time or space optimizations, you should seriously look into custom memory allocation routines.

Edit: Yes, I used an array of pointers, rather than a pointer to an array. The long and short is that describing the correct initialization of that array without some strong C++11 support is a complete bitch and in my personal use, it didn't warrant the serious issues I had actually making the damn thing. You can try std::unique_ptr<std::array<Node>, 8> if you want. It should, in theory, be the superior choice.

Answer 3

What about polimorphism?

struct TreeElem {
    virtual ~TreeElem() {}
};

struct Node : public TreeElem {
    std::vector<TreeElem*> _children;
};

struct Leaf : public TreeElem {
    int _value;
};

You can figure out the rest (virtual members of TreeElem).

P.S: if it's more than something trivial, use smart pointers.

Answer 4

Check che composite pattern and you can adapt it easily to perform an octree. After this, create the recursive function that take as argument the actual octree depth, so you can easyli perform what you want. Unfortunately, I don't understand well your question so I can't be more precise.