C++ 分支递归结构?

问题描述

我有以下几点.该结构是原型，因此可以正常编译.

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.

我使用的是 C++98/03 (VC++2008) 并且不能使用 C++11

任何帮助都将不胜感激.

Any help at all would be much appreciated.

附加信息:

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

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.

更多附加信息:

这是另一个图表.它有点大，因此您可能需要右键单击它并选择在新标签中打开图像 以使其可读.

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.

这基本上就是我想要实现的目标，为简单起见，将其绘制为 2D:

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

推荐答案

无需任何(手动)堆分配:

Without any (manual) heap allocation:

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.

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

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.

示例程序(参见在 Coliru 上直播):

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";
}

打印:

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

(std::vector 之外的使用)

---

(outside the use of std::vector)

这篇关于C++ 分支递归结构?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！