How to best keep locally generated elements of recursive struct in memory?

Question

I have a recursive, tree-like struct (TestStruct in the example code below) and basically a generator function which takes one of these and outputs the next one. My first attempt was similar to the code below (which does NOT work). I realize now that the sub variable only exists within the scope of gen_next, so the pointers (sub0,sub1) in the parent TestStructs no longer point to anything.

I do not have very much experience with C++ (or in general languages with this level of memory control), and I don't really know the best way to work around this. I thought of storing everything in global variables, but that seems pretty messy, and I feel like I'm missing a much simpler way to accomplish this.

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

Sorry wrong dupe marked, you need this one http://stackoverflow.com/questions/6441218/can-a-local-variables-memory-be-accessed-outside-its-scope — πάντα ῥεῖ, May 30 '15 at 10:40
@πάνταῥεῖ I understand that this is the problem, but my question is how do I work around it in my case. — KSab, May 30 '15 at 10:43
You cannot _workaround it_, unless you use dynamcally allocated memory. Stack memory is already managed under the hands of your program. — πάντα ῥεῖ, May 30 '15 at 10:44
@πάνταῥεῖ would storing every struct instance in a global array or something just to stop them from being dereferenced work? — KSab, May 30 '15 at 10:49

score 3 · Accepted Answer · edited May 30 '15 at 11:20

As mentioned, you cannot work around this. Stack allocated memory isn't under your control.

What you can do, is to allocate memory dynamically, and use an appropriate 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)) {}
};

In your gen_next() function you create the sub nodes as

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

and refer to the values, not the address like:

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

How to best keep locally generated elements of recursive struct in memory?

1 Answers1