c++ - 如何最好地将递归结构体的本地生成元素保留在内存中？

Question

我有一个递归的树状结构(下面示例代码中的TestStruct)，基本上是一个生成器函数，它接受其中一个并输出下一个。我的第一次尝试类似于下面的代码(不起作用)。我现在意识到 sub 变量仅存在于 gen_next 范围内，因此指针 (sub0,sub1 ) 父 TestStructs 中不再指向任何内容。

我对 C++(或具有这种内存控制级别的通用语言)没有太多经验，而且我真的不知道解决此问题的最佳方法。我想过将所有内容存储在全局变量中，但这看起来很困惑，而且我觉得我缺少一种更简单的方法来完成此任务。

#include <stdio.h>

struct TestStruct
{
    int type;
    struct TestStruct * sub0;
    struct TestStruct * sub1;

    TestStruct()
    {
        type = 0;
        sub0 = NULL;
        sub1 = NULL;
    }
    TestStruct(int type_init, TestStruct * sub0_init, TestStruct * sub1_init)
    {
        type = type_init;
        sub0 = sub0_init;
        sub1 = sub1_init;
    }
};

TestStruct gen_next(int size, TestStruct last)
{
    TestStruct empty;
    TestStruct sub;

    if (size==0)
    {
        if (last.type == 1)
            return TestStruct();
        if (last.type == 0)
            return TestStruct(1,NULL,NULL);
    }
    if (last.type == 0)
    {
        sub = gen_next(size-1,empty);
        return TestStruct(2,&sub,NULL); // bad code; sub will no longer exist!
    }

    if (last.type == 2)
    {
        sub = gen_next(size-1,*last.sub0);
        if (sub.type == 0)
            sub = gen_next(size-1,empty);
            return TestStruct(3,NULL,&sub);
        return TestStruct(2,&sub,NULL);
    }

    if (last.type == 3)
    {
        sub = gen_next(size-1,*last.sub1);
        if (sub.type == 0)
            return TestStruct();
        return TestStruct(3,NULL,&sub);
    }
    throw;
}

void print_struct(TestStruct test_struct)
{
    switch (test_struct.type)
    {
    case 0: printf("NONE");
        break;
    case 1: printf("END");
        break;
    case 2: printf("LEFT("); print_struct(*test_struct.sub0); printf(")");
        break;
    case 3: printf("RIGHT("); print_struct(*test_struct.sub1); printf(")");
        break;
    default: printf("INVALID:%d",test_struct.type);
    }
}

int main()
{
    TestStruct test;
    test = gen_next(3,test);
    print_struct(test);
    printf("\n");

    do {
        test = gen_next(3,test);
        print_struct(test);
    } while (test.type != 0);

    return 0;
}

Answer 1

如前所述，您无法解决这个问题。堆栈分配的内存不受您的控制。

您可以做的是动态分配内存，并使用适当的 smart pointer :

#include <memory>

struct TestStruct {
    int type;
    std::unique_ptr<TestStruct> sub0;
    std::unique_ptr<TestStruct> sub1;

    TestStruct() : TestStruct(0, nullptr, nullptr) {}

    TestStruct(int type_init,
               std::unique_ptr<TestStruct> sub0_init,
               std::unique_ptr<TestStruct> sub1_init)
    : type(type_init), sub0(std::move(sub0_init)), sub1(std::move(sub1_init)) {}
};

在您的 gen_next() 函数中，您将子节点创建为

std::unique_ptr<TestStruct> empty(new TestStruct);
std::unique_ptr<TestStruct> sub(new TestStruct);

并引用值，而不是地址，例如:

return TestStruct(2, std::move(sub), nullptr);