C++分支递归结构？

Question

我有以下内容.结构是原型,所以它编译得很好.

struct vertexNodeInfo
{
    vector<vertexNodeInfo> node;
};

我正在尝试写一个八叉树的东西.我想要做的是使用递归函数继续向每个节点添加一个节点,直到我到达一个特定的点,此时函数,而不是添加另一个节点,添加一个叶子.如果可能的话,如果没有其他节点或叶子添加,我想不使用内存.

也许模板会在这种情况下有所帮助,但我不确定如何使用它们......

我不认为我已经很好地解释了自己.这是一个图表:

我不知道我所要求的是不可能或者太难以理解或者只是简单的愚蠢,但我无法自己解决这个问题.对不起,我无法解释它.

我正在使用C++ 98/03(VC++ 2008),不能使用C++ 11

任何帮助都将非常感激.

附加信息:

更好的解释:我想要一个数组数组的数组数组.内存使用非常重要(我存储了数百万个元素,因此单个字节会产生巨大差异).每个数组可以包含8个以上的数组,但在我需要使用它之前,我希望每个数组都不使用内存.这是一种八重奏.

更多附加信息:

这是另一张图.它有点大,所以您可能需要右键单击它并选择Open image in new tab使其可读.

我不想要的是"棕色"(红色+绿色)框,其中每个框都为更多节点和叶数据保留内存.这将为我的需求使用太多的内存.

这基本上就是我想要实现的,为简单起见为2D:

Answer 1

没有任何(手动)堆分配^[1]:

struct NodeInfo { 
    int id; 
};

using Tree = boost::make_recursive_variant<
        NodeInfo,
        std::vector<boost::recursive_variant_>
    >::type;

我知道变体带有自己的"复杂性",但保留了内存局部性并避免了手动内存管理.

现在,为了更接近您声明的优化目标,您可以使用std::array<T, 8>而不是使用std::vector或者只是vector使用自定义allocator来从内存池中分配.

示例程序(请参阅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";
}

打印:

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

^[1](使用std :: vector之外)