Pointers and reference information

Question

I am creating something similar to a list of structures. At the beginning of main, I declare a null pointer. Then I call the insert () function a couple of times, passing a reference to that pointer to add new elements.

However, something seems wrong. I cannot display a list item, std::cout just breaks the program, even if it is a compiler without warning.

 #include <iostream> struct node { node *p, *left, *right; int key; }; void insert(node *&root, const int key) { node newElement = {}; newElement.key = key; node *y = NULL; std::cout << root->key; // this line while(root) { if(key == root->key) exit(EXIT_FAILURE); y = root; root = (key < root->key) ? root->left : root->right; } newElement.p = y; if(!y) root = &newElement; else if(key < y->key) y->left = &newElement; else y->right = &newElement; } int main() { node *root = NULL; insert(root, 5); std::cout << root->key; // works perfectly if I delete cout in insert() insert(root, 2); std::cout << root->key; // program breaks before this line return 0; } 

---

As you can see, I create a new structure element in the insert function and save it inside the root pointer. In the first call, although the loop is not even initiated, it therefore works, and I can display the root element in the main function.

But in the second call, when the loop is already running, and I get the described problem.

Something is wrong with the root->key syntax because it does not work even if I put this in the first call.

What is wrong and what is the reason?

Also , I always saw the insertion of new list items using pointers like this:

 node newElement = new node(); newElement->key = 5; root->next = newElement; 

This code is equal to:

 node newElement = {}; newElement.key = 5; root->next = &newElement; 

? It will be a little cleaner and there is no need to delete memory.

Answer 1

The problem is that you are passing a pointer to a local variable from a function. The highlighting of such pointers is undefined. You must highlight newElement with new .

This code

 node newElement = {}; 

creates a local variable newElement . Once the function is finished, the scope of newElement ends, and its memory is destroyed. However, you pass a pointer to this corrupted memory outside the function. All references to this memory become invalid as soon as the function exits.

This code, on the other hand

 node *newElement = new node(); // Don't forget the asterisk 

Selects an object in free storage. Such objects remain available until you delete them explicitly. This is why you can use them after exiting the function that creates them. Of course, since newElement is a pointer, you need to use -> to access its members.

Answer 2

The key value you need to learn here is the difference between stacked objects and heaped objects. In your insert function, your node newElement = {} is allocated a stack, which means that its lifetime is determined by the enclosing area. In this case, this means that when the function exits your object, it will be destroyed. This is not what you want. You want the root of your tree to be stored in your node *root pointer. To do this, you need to allocate memory from the heap. In C ++, which usually runs with a new statement. This allows you to transfer the pointer from one function to another, without defining its life expectancy, determined by the scope. It also means that you need to be careful in managing the lifetime of objects allocated by a bunch.

Answer 3

You have one problem with the comment as well . The second may be cleaner, but it’s wrong. You must have a new memory and delete it. Otherwise, you will get pointers to objects that no longer exist. This is exactly the problem that the new solves.

Another problem

 void insert(node *&root, const int key) { node newElement = {}; newElement.key = key; node *y = NULL; std::cout << root->key; // this line 

The first root of the insert is still NULL, so this code will crash the program.

Answer 4

It has already been explained that you will have to allocate objects dynamically (using new ), however this is fraught with dangers (memory leaks).

There are two (simple) solutions:

• Have a ownership scheme.
• Use the arena to host your sites and keep links to them.

1 Ownership scheme

In C and C ++, there are two forms of obtaining memory for storing an object: automatic storage and dynamic storage. What you use is automatically used when you declare a variable in your function, for example, however, such objects only live for the duration of the function (and, therefore, you have problems using them after that, because the memory is probably overwritten by something else). Therefore, you often have to use dynamic memory allocation.

The problem with dynamic memory allocation is that you must explicitly return it to the system so that it does not leak. In C, this is quite complicated and requires rigor. In C ++, although this has been simplified through the use of smart pointers. So let's use them!

 struct Node { Node(Node* p, int k): parent(p), key(k) {} Node* parent; std::unique_ptr<Node> left, right; int key; }; // Note: I added a *constructor* to the type to initialize `parent` and `key` // without proper initialization they would have some garbage value. 

Notice the different parent and left declaration? The parent owns its children ( unique_ptr ), while the child simply refers to its parent.

 void insert(std::unique_ptr<Node>& root, const int key) { if (root.get() == nullptr) { root.reset(new Node{nullptr, key}); return; } Node* parent = root.get(); Node* y = nullptr; while(parent) { if(key == parent->key) exit(EXIT_FAILURE); y = parent; parent = (key < parent->key) ? parent->left.get() : parent->right.get(); } if (key < y->key) { y->left.reset(new Node{y, key}); } else { y->right.reset(new Node{y, key}); } } 

If you do not know that unique_ptr , get() it simply contains the object selected with new , and the get() method returns a pointer to this object. You can also reset its contents (in this case, it correctly disposes of the object contained in it, if any).

I would notice that I'm not too sure about your algorithm, but hey, this is yours :)

2 arena

If it deals with memory, you have your own head all soft, this is pretty normal at first, and why sometimes arenas can be easier to use. The idea of ​​using the arena is quite general; instead of worrying about owning the memory in parts, you use “something” to hold the memory and then manipulate the links (or pointers) to the parts. You just have to keep in mind that these links / pointers are only ever alive while the arena is.

 struct Node { Node(): parent(nullptr), left(nullptr), right(nullptr), key(0) {} Node* parent; Node* left; Node* right; int key; }; void insert(std::list<Node>& arena, Node *&root, const int key) { arena.push_back(Node{}); // add a new node Node& newElement = arena.back(); // get a reference to it. newElement.key = key; Node *y = NULL; while(root) { if(key == root->key) exit(EXIT_FAILURE); y = root; root = (key < root->key) ? root->left : root->right; } newElement.p = y; if(!y) root = &newElement; else if(key < y->key) y->left = &newElement; else y->right = &newElement; } 

Just remember two things:

• As soon as your arena dies, all of your links / pointers point to the ether, and bad things happen if you try to use them.
• If you ever just click things on arena , it will grow until it consumes all available memory and your program will fail; at some point you need cleaning!