CODEWITHSUNDEEP
c++pointersdata-structuresrust
zakum
zakum

Reputation: 77

Recursive data-structures without the use of pointers

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.

Upvotes: 3

Views: 4620

Answers (2)

hauron
hauron

Reputation: 4668

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

Upvotes: 2

Cory Kramer
Cory Kramer

Reputation: 117926

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.

Upvotes: 3

Related Questions