Heap memory vector initilization in C-CodePudding

I am confused between

vector<node>* children = new vector<node>;

vector<node> *children = new vector<node>;

vector<node*> children = new vector<node>;

I just want to implement a general tree data structure as

struct node{
    int index;
    vector<int> sol;
    vector<node *> children;
};

node *createNode(int indexVal)
{
    node* n = new Node();
    n->index = indexVal;

    vector<int>* soll = new vector<int>;
    n->sol = soll;

    vector<node>* childrenn = new vector<node *>;
    n->children = childrenn;

    return n;
}

void addChildren(node* curr, node* child)
{
//something like
    curr->push_back(child);
};

I want to be able to modify sol and children vector in which ever scope I want, given that I have a node pointer

I am confused which one of the three given will be the best results, how will they differ? Also how would this extend to 2-d vectors?

CodePudding user response：

You have this:

vector<node *> children;

That is fine, it's a vector of pointers to nodes. You do not use new to create it, it is created automatically whenever you have a node. So:

node *createNode(int indexVal)
{
    node* n = new node();
    n->index = indexVal;
    return n;
}

The node has sol and children vectors directly inside it.

CodePudding user response：

Regarding

vector<int>* children = new vector<int>;

and

vector<int> *children = new vector<int>;

They are the same. Both are declaring a pointer to a vector< int>. The only difference is the position of the *. Some people think it is more readable when the * is closer to the type name. Others prefer the * closer to the variable name.

Although I prefer the first one, which puts the * closer to type, the second one is more correct because in C the parser associates the * with the variable and not with the type. Thus one could declare the following:

vector<int> *ptr1, var2, *ptr2, *ptr3, var3

This would declare variables ptr1, ptr2 and ptr3 as being pointers to vector< int> while var2 and var3 would be normal variables. If you use the first writing style and write:

vector<int>* ptr1, var2, ptr2, ptr3, var3

Believing that all variables would be pointers, you would be wrong. Only ptr1 would be a pointer and all the others would be normal variables.

Now this

vector<node*> children = new vector<node>;

Is a completely different thing. While on the first two you're declaring a pointer to an array of ints, on the third one you are declaring an array of pointers to int. Also, note the typo you made on the new where you forget the *. To work, it would need to be (note the * at the end)

vector<node*> children = new vector<node*>;

Regarding your code, it seems that sol is the data stored in the node and children contains the pointers to the other nodes. So I believe in this case the following is correct

struct node{
    int index;
    vector<int> sol;
    vector<node *> children;
};

And here

node *createNode(int indexVal)
{
    node* n = new Node();
    n->index = indexVal;

    /* This is wrong and unecessary. As sol is not a pointer, when 
       you do a new above, the new already allocates the sol so that
       you don't need to allocate again here */
    vector<int>* soll = new vector<int>; // remove this
    n->sol = soll; // not needed

    /* Now here you have some typos. It should be vector<node *> and not 
       vector<node>* */
    vector<node>* childrenn = new vector<node *>;
    n->children = childrenn;

    return n;
}

I didn't make any comments on the tree itself as you posted just a skeleton code instead of the real one. I assume you know trees and just wanted to know the C stuff regarding pointers and vector. If you don't know trees yet, look closer to your code because there are some parts that are not quite right.

CodePudding user response：

vector<node>* children = new vector<node>; and vector<node> *children = new vector<node>; are both same and it is a pointer to vector of node but vector<node*> children = new vector<node>; is incorrect because your variable is not of the type of pointer. To assign memory from heap we use the keyword new and the variable should be of type pointer. vector<node*> children; is a vector of pointer to node but this will allocate memory from stack and not from heap