Nested struct in C++

Question

I tried to write a program with the following struct declaration:

struct N
{
    int value;
    N Left;
    N Right;
};

If that was possible, there would be an infinite number of structs in my program. I still want my Left and Right to have the exact same structure as N. Is there a way to do that?

Answer 1

To build tree-like structures you may use pointers:

struct N {
    int value;
    N *left;
    N *right;
};

You may also use references:

struct N {
    int value;
    N &left;
    N &right;
};

but this way you'll need to carefully bind references in elements that don't have either of branches (or both.)

Or other indirecting types: unique_ptr, shared_ptr, reference_wrapper, etc.

Additionally, you can have a whole bunch of child referencnes:

struct N {
    int value;
    std::vector<std::reference_wrapper<N>> branches;
};

Answer 2

I think im getting what your goal is. You want a struct that is aware of its neighbours. In that case use pointer instead.

struct N
{
    int value;
    N* Left;
    N* Right;
};

Answer 3

What is happening in your case is that the compiler is trying to generate your struct, but cannot because of infinite recursion: sizeof(N) = sizeof(int) + sizeof(N)

A way to solve this is to use pointers to N. Now : sizeof(N) = sizeof(int) + 2*sizeof(N*) is defined.

struct N { int value; N *left, *right; };

If you are using C++17, you can also use std::optional and std::reference_wrapper:

struct N { int value; std::optional<std::reference_wrapper<N>> left, right; };

Do Not Use References. References must bind during initialization and must bind to a valid object. Therefore, some of your references are bound to be invalid (since the tree is not infinite).