Recursive data-structures without the use of pointers

Question

During my bachelor degree in CS I've come across the use of recursive data-structures a lot of times. In C++ I always ended up using pointers to make my data structures recursive, just like what I would do in C.

A simplified example could be the following:

struct Tree{
    int data;
    struct Tree *left, *right;
};

However, using pointers tends to be a risky job and involves a lot hours debugging and testing the code. For these resouns I would like to know if there is any other efficient way of defining recursive data-structures in C++.

In other programming languages, like Rust, I've seen things like that:

struct Node {
    children: Vec<Node>,
    node_type: NodeType,
}

Is there a safer and confortable way of defining such recursive structures in C++. One possibility would be to use std::Vector, but I am not aware of the performance of the method.

@Robinson and that would end the application immediately - due to infinite Tree object creation :) — hauron
– hauron, Commented Apr 29, 2016 at 11:24
In some cases it's actually an advantage in using pointers, for example in tree-like structures. How do you otherwise tell that a tree doesn't have any children? There's no "null" value that can be used for structures. — Some programmer dude
– Some programmer dude, Commented Apr 29, 2016 at 11:25
As for why it's allowed in Rust, that's because Rust is not C++. Two different languages, no matter how similar their syntax is, can't really be compared. As for why it works in Rust is probably because it uses references (sort of like pointers) instead of the actual structure. — Some programmer dude
– Some programmer dude, Commented Apr 29, 2016 at 11:28
Rust is absolutely no different to C++ in this respect: you can't write struct Tree { data: i32, left: Tree, right: Tree }. Rust's Vec contains direction internally, it is in fact essentially identical to C++'s std::vector. (Rust's structs and enums are values, like in C++, not pointers/references.) — huon
– huon, Commented Apr 29, 2016 at 11:30
@zakum, if you're happy using Box/Arc/Vec in Rust, then the equivalents in C++ (unique_ptr/shared_ptr/vector) should be just what you're looking for. (I realise I made a typo in my previous comment: "direction" should be "indirection".) — huon
– huon, Commented Apr 29, 2016 at 13:24

Cory Kramer · Accepted Answer · 2016-04-29 11:25:29Z

3

The reason pointers are used rather than values is because you would never be able to define your struct as its size would be infinitely recursive.

struct Tree{
    int data;
    struct Tree left, right;
};

Neglecting padding etc, you could approximate the size of Tree as

sizeof(Tree) == sizeof(int) + sizeof(Tree) + sizeof(Tree)
//                     ^data         ^left          ^right

but you can see that since Tree has two members of Tree, and those members themselves have two Tree members, and those have two Tree members.... you can see where this is going.

answered Apr 29, 2016 at 11:25

Cory Kramer

119k19 gold badges176 silver badges233 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

zakum Over a year ago

I am aware of that. However, using C++ style of doing things would make some things easier, like "garbage collection". That's why I'm trying to find a way of defining a recursive data-structure in C++. If I'm not clear enough, just think of how std::Vector handles memory on its own.

hauron · Accepted Answer · 2016-04-29 11:29:49Z

2

The Rust example uses a vector of children - this can be empty as well.

In C++, the member variable can be an object, a pointer or a reference (omitted for simplicity).

Since a node object cannot be used directly (this would loop infinitely) and you do not wish to use a pointer, your options are:

use a vector as well (though for a binary tree this is not the most convenient type - you could however limit it in code to always two elements),
use a map (key could be an enum CHILD_LEFT, CHILD_RIGHT),
reconsider using pointers, or better yet: smart pointers (this looks like a good use case for regular unique_ptrs).

answered Apr 29, 2016 at 11:29

hauron

4,6785 gold badges40 silver badges54 bronze badges

3 Comments

zakum Over a year ago

How would the code be if using references? @Joachim Pileborg says Rust just does that. However, the option of using unique_ptrs seems the most reasonable for me as well.

hauron Over a year ago

@zakum it'd require a series of ugly hacks (e.g. a global vector of Tree, three ctors for Tree: either empty, with a child or with both children (since you cannot change reference pointed to variable after it's initialization), and that's just creation... what about deletion!). I'd strongly recommend using unique_ptrs. Do note that in C++ if the raw pointers never leaves the object, it may be safe to use just that (just write a proper destructor, and avoid allocating in Tree constructor).

zakum Over a year ago

Thank you for your interesnt and time. I'm accepting your answer as the best one. I'll definetely try to use uniqe_ptr next time.

Collectives™ on Stack Overflow

Recursive data-structures without the use of pointers

2 Answers 2

1 Comment

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related