C++ Branching recursive struct?

Question 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)

Question 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.

Question 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.

Question 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.