Basic pointer questions.

[Gaminic]

Hello,

I've got a decent grasp of basic C++, but pointers are still voodoo to me and I tend to avoid them. Considering they're a vital part of C programming, I decided to get some practice.

I've built a Binary Tree with basic functionality: A 'Node' class with a value (int), an lson and an rson(Node pointers), plus a 'Tree' class with a root (Node pointer). The 'Tree' class has an 'addNode(Node &n)'.

I've tested the Tree by manually making one as well as some Nodes, then manually adding them. That worked perfectly. Afterwards, I wanted to test it more thoroughly by means of adding a large amount of randomly generated values. The problem is I seemed to have messed up some of the 'pointering' and [probably not really] unexpected behaviour has occured.

The test function itself is simple:

	for (int i = 0; i < n; ++i) {
		Node temp = Node(rand()%5001);
		t.addNode(temp);
	}

Now, the problem is that the first node is assigned as the root ("root = &n;"), but that the address of 'n' is apparently reused every time a new node is generated. The result is that the value of the root Node is constantly overwritten.

I'm not certain how to fix this. Passing the Node to be added without the '&' would (to my understanding) lead to the root pointer pointing to a temporary copy of the Node, which is lost at the end of the function. Same thing if I make a new Node inside the Tree addNode() function.

How do I get around this, and what's the logic behind it?

P.S.: Secondary question: Imagine I were to dynamically create a variable (using new) and have it deleted later on. Then, I start the debugger, break somewhere between the new and delete, and then quit debugging. What happens to the memory allocation?

[Moschops]

P.S.: Secondary question: Imagine I were to dynamically create a variable (using new) and have it deleted later on. Then, I start the debugger, break somewhere between the new and delete, and then quit debugging. What happens to the memory allocation?

If you quit debugging and let the program keep running, it's just like normal. If you quit debugging and kill the process, all memory is tidied up and reclaimed by the OS as normal.

[moorecm]

If you're having trouble with your Node class internals and want help, post them...

[Gaminic]

I imagined the description would be sufficient, but here they are [stripped of unnecessary additions]:

class Node
{
public:
	int value;
	Node *lson;
	Node *rson;

	Node(int);
	~Node(void);	
};

class Tree
{
public:
	Node *root;

	Tree(void);
	~Tree(void);

	void addNode(Node);
};

void Tree::addNode(Node n) { // Tried both 'n' and '&n'
	if (root == NULL) {
		root = &n;
		return;
	}
	Node *parent = root;
	Node *next = NULL;
	bool go = true;
	int i = 1;
	while (go) {
		if (parent->value == n.value) { // Check if same value
			std::cout << "Value already present. Quitting.\n";
			return;
		}
		if (n.value > parent->value) { // Higher -> go right
			if (parent->rson == NULL) { // No right son -> become right son
				parent->rson = &n; // Have rson point to new Node
			}
			else { // Else, visit right son
				parent = parent->rson;
			}
		} 
		else { // Same for lower -> left
			if (parent->lson == NULL) {
				parent->lson = &n;
				go = false;
			}
			else { 
				parent = parent->lson;
			}
		}
	}
}

The function call is shown in my first post. A new Node is created inside a for loop, then added to the Tree.

My guess is that MVC++2010's compiler optimizes the process and makes reuses the temp Node variable, thus overwriting the previously initialized Node. This makes sense, because the Node goes out of scope at every iteration, thus I suppose my tree will be pointing to unallocated memory. I'm just not really sure how to fix this. I could add a vector of Node objects in the Tree class and make a copy of the added Node that persists, by adding it to the Tree object, but that seems redundant...

[Gaminic]

I've currently fixed it the way I described in my previous post:
The "Tree" class now carries a vector<Node>. When addNode(Node&) is called, a new Node is made (inside the function scope) and added to the vector. Rather than using the address of the temp Node, the address of the vector element is saved. Together with the .reserve() command, those pointers are fixed.

I do feel like this is a very dirty way, but I can't think of another way to make the Nodes/pointers persistent... Any ideas?

[moorecm]

At first glance, ownership is the problem. You can't store the address of a temporary, as it will become invalidated.

void Tree::addNode(Node n) { // Tried both 'n' and '&n'
	if (root == NULL) {
		root = &n; // <- this stores the address of the temp. variable n
		return;
	}

Now, IF you changed that parameter to be a pass by reference, you would still have the address of a temporary because of the way you are calling addNode:

	for (int i = 0; i < n; ++i) {
		Node temp = Node(rand()%5001); 
		t.addNode(temp); // <- temp is temporary but addNode would store its address
	}

You have to create a root node (probably dynamically) and either use assignment or copy construction to set its value. I don't really have time to go into the details but I'm sure there are plenty of examples of linked lists online. Or perhaps someone else will chime in.