Sign in to follow this  

Dynamic memory allocation in a constructor

This topic is 2538 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm trying to create an n-ary tree in C++. Here is my struct:


struct tree
{
int data;
tree * next;

tree(int numLeaves)
{
cout << "tree object created\n";
next = new tree[numLeaves];
}

tree()
{
}
};




When a tree object is created with an integer argument, am I correct in assuming this will create an array of pointers to 'tree' objects of a size equal to the argument.

The following code is giving compile-time errors:


int main()
{
tree test(2);
test.data = 1;
test.next[0] = new tree(3);

return 0;
}




It says there's an invalid conversion from tree* to int.

I'm confused since I used similar code to make a statically linked tree by omitting both constructors and initializing the pointer array as follows:

tree *next[2];

So what am I doing wrong in initializing this array of pointers dynamically? Or is my error in how I'm trying to access it?

edit: and my guess is that i'm looking at the constructor as creating an array of pointers to trees when in fact it's actually creating the trees themselves.

Share this post


Link to post
Share on other sites
If next is a tree * then next[0] is a tree, not a tree *. In this case, I'd recommend using a std::vector rather than a dynamic array, in which case if you want to hold pointers you would use std::vector<tree *>. However, I'd also give some serious thought about using smart pointers rather than raw pointers.

Share this post


Link to post
Share on other sites
Try thinking about this:
int* pint = new int [1];
pint[0] = new int; // doesn't compile
pint[0] = 123; // compiles

int** pintarr = new int* [1];
pintarr[0] = new int; // compiles fine
pintarr[0][0] = 123;

Share this post


Link to post
Share on other sites
You're creating an array of tree's, but it looks like you want an array of pointers to tree's, e.g.:

struct tree
{
int data;
tree ** next;

tree(int numLeaves)
{
cout << "tree object created\n";
next = new tree*[numLeaves];
}

tree()
{
}
};

(Of course the usually admonitions regarding dynamic memory management, RAII, use of standard containers, and so on apply here.)

Share this post


Link to post
Share on other sites

#include <iostream>

using namespace std;

struct tree
{
int data;
tree ** next;

tree(int numLeaves)
{
cout << "tree object created with " << numLeaves << " leaves\n";
next = new tree*[numLeaves];
}

tree()
{
}
};

int main()
{
tree test(2);
test.data = 1;
test.next[0] = new tree(3);
test.next[1] = new tree(4);
test.next[0]->data = 2;
test.next[1]->data = 3;
test.next[0]->next[0]->data = 4;
test.next[0]->next[1]->data = 5;
test.next[0]->next[2]->data = 6;
test.next[1]->next[0]->data = 7;
test.next[1]->next[1]->data = 8;
test.next[1]->next[2]->data = 9;
test.next[1]->next[3]->data = 10;

cout << test.data;

return 0;
}




I modified it so that it was an array of pointers instead of trees, but it still seems to have some subtle problem.

The above code, doesn't print out '1' as expected.

Nor does printing out any of the other data bits. (test.next[0]->next[1]->data, etc.)

Share this post


Link to post
Share on other sites
Quote:
The above code, doesn't print out '1' as expected.
What does it print out? (Or more generally, what happens when you run the program?)

It looks to me like you're dereferencing a number of tree pointers that haven't had a value assigned to them. At the very least, you should probably fill your next array with 0s in the constructor, as that will likely cause a run-time error to occur if no other assignment is made.

Also, you may already know this, but all of the memory you're allocating is being leaked. (This doesn't really have any practical significance in the given context, but it's important to be aware of.)

Share this post


Link to post
Share on other sites
Because you never initialize test.next[0]->next[0] with anything. It's a random garbage address that you're trying to access without allocating anything for it.

Share this post


Link to post
Share on other sites
Quote:
Original post by sooner123
Apparently the line:
test.next[0]->next[0]->data = 4;

Crashes the program at run time and I don't understand why.
I explained why in my previous post.

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Quote:
Original post by sooner123
Apparently the line:
test.next[0]->next[0]->data = 4;

Crashes the program at run time and I don't understand why.
I explained why in my previous post.


I didn't quite follow you at the time but now I understand. Thanks for your help.

Share this post


Link to post
Share on other sites
As you guys said, I was accessing memory locations that weren't ready to be accessed. I was looking at the line 'test.next[0] = new tree(3); as creating three tree objects and not as dynamically sizing the 'next' array to size 3, which then needed to be pointed to new tree objects.

Here is what I've got now and it's working for the time being.


#include <iostream>

using namespace std;

struct tree
{
int data;
tree ** next;

tree(int numLeaves)
{
cout << "tree object created with " << numLeaves << " leaves\n";
next = new tree*[numLeaves];
}

tree()
{
cout << "no argument constructor called\n";
}
};

int main()
{
tree test(2);
test.data = 1;
test.next[0] = new tree(3);
test.next[1] = new tree(4);
test.next[0]->data = 2;
test.next[1]->data = 3;
test.next[0]->next[0] = new tree();
test.next[0]->next[1] = new tree();
test.next[0]->next[2] = new tree();
test.next[1]->next[0] = new tree();
test.next[1]->next[1] = new tree();
test.next[1]->next[2] = new tree();
test.next[1]->next[3] = new tree();
test.next[0]->next[0]->data = 4;
test.next[0]->next[1]->data = 5;
test.next[0]->next[2]->data = 6;
test.next[1]->next[0]->data = 7;
test.next[1]->next[1]->data = 8;
test.next[1]->next[2]->data = 9;
test.next[1]->next[3]->data = 10;

cout << test.data;
cout << test.next[0]->data;
cout << test.next[1]->data;
cout << test.next[0]->next[0]->data;
cout << test.next[0]->next[1]->data;
cout << test.next[0]->next[2]->data;
cout << test.next[1]->next[0]->data;
cout << test.next[1]->next[1]->data;
cout << test.next[1]->next[2]->data;
cout << test.next[1]->next[3]->data;

return 0;
}



Any suggestions? Doesn't matter what for. This isn't for anything in particular. Just wanted to play with pointers, structs, and make a dynamic-ply tree.

Share this post


Link to post
Share on other sites
You've already been given quite a bit of advice that you've decided to ignore. Before you decide to finish with it you should at the very least deal with the fact that it leaks memory like a sieve.

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
You've already been given quite a bit of advice that you've decided to ignore. Before you decide to finish with it you should at the very least deal with the fact that it leaks memory like a sieve.


Hmm. Sorry if I gave that impression but it's not the case at all. I've spent some time since your post trying to figure out how and why it's leaking, but my experience is too limited.

My best guess is that the memory leak happens when the no argument constructor is called, since there's a dangling double pointer. Or is it also (or only) due to the fact that when the argument constructor is called, the double pointer is dynamically sized but still not pointing to specific objects?

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
You use new and you never use delete.


How do I clean up the whole tree without a destructor that recursively calls delete like this:


~tree()
{
for (int i=0; i<children; i++)
{
delete next[i];
}
cout << "the node containing " << data << " ceases to exist\n";
}




I thought this was working as intended because the top level node gets killed when main ends and it goes out of scope, which then recursively deleted all the children and grandchildren nodes. How am I supposed to do this without delete?



Also as for using new, should I be initializing test this way:

tree * test = new tree(2);



edit: or is it just that when you declare stuff with 'new' you don't need to 'delete' it anyways?

[Edited by - sooner123 on December 31, 2010 11:49:24 AM]

Share this post


Link to post
Share on other sites
Anything you allocate with new needs to be deleted. If a tree has an array of child objects dynamically allocated(which are also tree objects) which are correctly deleted in the destructor then deleting the root node will correctly clean up all children recursivly without you having to do anything extra.

You have to delete dynamically allocated arrays differently.

if you have

tree *a = new tree;
then doing
delete a;
is fine

but if you allocate an array of them:
tree *a = new tree[3];
then you have to do:
delete [] a;

doing "delete [] a" when you only allocate 1 object will also work fine so if you anticipate having more than one "next" then make sure to do "delete [] next" in your destructor.

Share this post


Link to post
Share on other sites
How are you planning on determining how many child nodes a node has at run-time? You don't have a childCount member. Perhaps you were going to null-terminate your array of pointers, in which case you have to allocate one extra?

A vector would certainly make it easier.

Share this post


Link to post
Share on other sites
Quote:
Original post by iMalc
How are you planning on determining how many child nodes a node has at run-time? You don't have a childCount member. Perhaps you were going to null-terminate your array of pointers, in which case you have to allocate one extra?

A vector would certainly make it easier.


In my last post I showed the destructor referencing a member called children.

Here's my full code:


#include <iostream>

using namespace std;

struct tree
{
int data;
int children;
tree ** next;

void printTree()
{
cout << data << endl;
for (int i=0; i<children; i++) next[i]->printTree();
}

tree(int numLeaves)
{
cout << "tree object created with " << numLeaves << " leaves\n";
next = new tree*[numLeaves];
children = numLeaves;
data = -1; //uninitialized
}

tree()
{
cout << "no argument constructor called\n";
children = 0;
}

~tree()
{
for (int i=0; i<children; i++)
{
delete next[i];
}
cout << "the node containing " << data << " ceases to exist\n";
}
};

int main()
{
//small example of doing things with pointers and 'new'
/* tree *x = new tree(2);
x->data = 30;
x->next[0] = new tree(2);
x->next[1] = new tree();
x->next[0]->data = 40;
x->next[1]->data = 50;
x->next[0]->next[0] = new tree();
x->next[0]->next[1] = new tree();
x->next[0]->next[0]->data = 60;
x->next[0]->next[1]->data = 70;
delete x;*/


//initializing an n-ary tree 3 levels deep that holds the integers [1,10]
tree test(2);
test.data = 1;
test.next[0] = new tree(3);
test.next[1] = new tree(4);
test.next[0]->data = 2;
test.next[1]->data = 3;
test.next[0]->next[0] = new tree();
test.next[0]->next[1] = new tree();
test.next[0]->next[2] = new tree();
test.next[1]->next[0] = new tree();
test.next[1]->next[1] = new tree();
test.next[1]->next[2] = new tree();
test.next[1]->next[3] = new tree();
test.next[0]->next[0]->data = 4;
test.next[0]->next[1]->data = 5;
test.next[0]->next[2]->data = 6;
test.next[1]->next[0]->data = 7;
test.next[1]->next[1]->data = 8;
test.next[1]->next[2]->data = 9;
test.next[1]->next[3]->data = 10;

//outputs the data in the tree
cout << test.data << ",";
cout << test.next[0]->data << ",";
cout << test.next[1]->data << ",";
cout << test.next[0]->next[0]->data << ",";
cout << test.next[0]->next[1]->data << ",";
cout << test.next[0]->next[2]->data << ",";
cout << test.next[1]->next[0]->data << ",";
cout << test.next[1]->next[1]->data << ",";
cout << test.next[1]->next[2]->data << ",";
cout << test.next[1]->next[3]->data << endl;

//taking a leaf with no children and giving it children
test.next[1]->next[3]->next = new tree*[8];
test.next[1]->next[3]->next[0] = new tree();
test.next[1]->next[3]->next[1] = new tree();
test.next[1]->next[3]->next[2] = new tree();
test.next[1]->next[3]->next[3] = new tree();
test.next[1]->next[3]->next[4] = new tree();
test.next[1]->next[3]->next[5] = new tree();
test.next[1]->next[3]->next[6] = new tree();
test.next[1]->next[3]->next[7] = new tree();

//giving one of those children data and printing it
test.next[1]->next[3]->next[7]->data = 32;
cout << test.next[1]->next[3]->next[7]->data << endl;

//calling printTree (recursive method of printing everything)
test.printTree();

return 0; //this calls the destructor for tree
//which in turn (recursively) calls
//the destructors for its children
}

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
You're still leaking memory. For every new there must be a delete and for every new [] there must be a delete [].


What about the very first new?

I played around with things and it seemed like the top level node got deleted (and destructor called) as soon as main ends (it goes out of scope). That's what prompted me to write the destructor the way I did.

Share this post


Link to post
Share on other sites
Quote:
Original post by sooner123
What about the very first new?

Every time you call new you must call delete. Every time you call new [] you must call delete []. It doesn't matter if it's the first time or the second time or the one millionth time. Conversely if an object isn't allocated by new you don't call delete.

Share this post


Link to post
Share on other sites

This topic is 2538 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this