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?

You know that it's impossible, you even know *why* it's impossible, but you're still looking for a way to do it? — molbdnilo, Aug 17 '18 at 12:29
Recursion. *"Pete and Repeat were on a boat. Pete fell off. Who was left?"* How does the compiler know when to stop the recursive layout? — Thomas Matthews, Aug 17 '18 at 14:08

bipll · Accepted Answer · 2018-08-17T13:16:44.067

5

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

edited Aug 17 '18 at 13:16

answered Aug 17 '18 at 12:05

bipll

11,747
1
18
32

3

No, you cannot use references. References must bind to a valid object at their initialization (Construction). Therefore it this will cause invalid references. – Kostas Aug 17 '18 at 12:22
@GillBates they *could*, if they use a constructor. But it would probably not be very useful. – eerorika Aug 17 '18 at 12:32
2

@GillBates `N wat{42, wat, wat};`? Or declare an `external N null;` and default `left` and `right` to it? – bipll Aug 17 '18 at 12:40
@bipll [reference_wrappers, unlike pointers, don't have a null state.](https://stackoverflow.com/questions/26766939/difference-between-stdreference-wrapper-and-simple-pointer) – Kostas Aug 17 '18 at 12:44
1

Yes, but can be rebound. Btw it's not hard to define a refernce wrapper that _has_ null state. – bipll Aug 17 '18 at 12:48
Technicalities aside, it's just a bad idea to have nodes made out of references. Why offer it as advice? – Passer By Aug 17 '18 at 13:13
@PasserBy Sure, still possible. :) – bipll Aug 17 '18 at 13:14
Besides, there are so many class hierarchies in this world where objects contain pointers to other objects, and those pointers aren't expected to be null. – bipll Aug 17 '18 at 13:15
Thank you! May I also ask you I should initialise such an object? I need to tell the computer not to expect further delcarations from a particular struct at some point. – Artur Wiadrowski Aug 17 '18 at 18:15

score 2 · Answer 2 · answered Aug 17 '18 at 12:07

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

answered Aug 17 '18 at 12:07

Korni

464
2
10

Kostas · Answer 3 · 2018-08-17T14:45:24.333

2

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).

edited Aug 17 '18 at 14:45

answered Aug 17 '18 at 12:20

Kostas

4,061
1
14
32

1

The `optional` example is incorrect, it would have infinite size too (`optional` is like the type with a validity flag tacked on) – M.M Aug 17 '18 at 13:22
@M.M You are right. I assumed it was implemented as a pointer :). How about `std::optional>` thought? – Kostas Aug 17 '18 at 14:46
Legal but I don't really see the advantage over `N *`. (It probably uses more storage, and is more cumbersome to access, for no clear benefit) – M.M Aug 17 '18 at 23:30

Nested struct in C++

3 Answers3