C++ 分支递归结构？

Question

我有以下内容。该结构已原型(prototype)化，因此可以正常编译。

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)