C++

Forum

 
Tree data structure/ Memory leak

Minionmin (8)
Hi guys, I'm currently taking an online C++ course and I'm a little bit curious about the buildTree() function. In the function there is a "new" keyword to allocate memory for the node, isn't it? I just realized that there is no "delete" keyword in the function. My questions are
1. If I continue to run the code repeatedly, will my computer's RAM get full?
2. Instead of using "new" keyword in the function, what would you guys use?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
//Class//
class node
{
    public:
        int data;
        node* left;
        node* right;

        node(int d)
        {
            data = d;
            left = NULL;
            right = NULL;
        }
};
//Class//

//Func//
node* buildTree()
{
    int d;
    cin >> d;

    if(d == -1)
        return NULL;
    
    node* root = new node(d);
    root->left = buildTree();
    root->right = buildTree();

    return root;
}
//Func//
MikeyBoy (5631)
Obviously, you wouldn't want to have a delete in the buildTree() function. The whole point of the function is to create the tree and hand it back to the calling code, and if you deleted the memory you've just allocated, then you'd be destroying the very thing you were supposed to be creating.

Somewhere else in the program, there should be some code responsible for calling delete to free up the memory used by the tree, after it's no longer required. Possibly, you should create a destructor for node, and do it there.

If I continue to run the code repeatedly, will my computer's RAM get full?

That part of the RAM set aside for processes to use would fill up, yes. On any sensible operating system, though, that won't be all the computer's RAM, just a part of it. At that point, new will start throwing an exception, and what happens then depends on what the calling code does with that exception.

And in any case, the node class is pretty small; you'd have to create an awful lot of them to fill up the available memory. It's unlikely to happen unless you're deliberately trying to do it.

Instead of using "new" keyword in the function, what would you guys use?

In modern C++, it's better to use the appropriate smart pointer, to reflect the ownership of the memory. I'm guessing here, that would be std::unique_ptr . Then, instead of new, you would use std::make_unique().
Last edited on
deleted account xyzzy (5768)
Use the stack -- don't use new to get heap memory -- and the program will (quickly) run out of stack space and segfault.

Use the heap -- AKA the freestore -- and you will have more memory possible to allocate. Though your OS isn't likely to allow your program to access all of your RAM, it should restrict the amount available for use for the process.

How your OS handles a program gobbling up all the heap initially allocated to the process depends on the OS.

Modern OSes are good at managing memory, programs when terminated free up the memory associated with the process.

With that said, not having delete with each new is very poor programming. It pays to be neat.

The C++ stdlib containers and smart pointers do the grunt work of managing memory for you so you don't have to worry about the details.

Personally I would use one of the C++ stdlib containers instead of creating a custom container.
https://en.cppreference.com/w/cpp/container

If none of the container matched exactly what my requirement were I'd adapt one of the available containers to my needs.

Instead of raw pointers using heap memory I'd use a smart pointer.
https://en.cppreference.com/w/cpp/memory

If I were to use a C++ stdlib container there is no need to have a data member be a pointer, the containers automatically use heap memory for allocating the elements.

But if I had a lot of -> access-a-data-member logic all over my code I'd go with a smart pointer.

Though I'd design the code basics on paper before actually writing it so using a C++ container or smart pointer would already be baked into the design.
seeplus (6591)
Using dynamic memory and a class for Tree, then maybe something like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
#include <iostream>

struct Node {
	int data {};
	Node* left {};
	Node* right {};

	Node(int d, Node* l = nullptr, Node* r = nullptr) : data(d), left(l), right(r) {}
};

class Tree {
	Node* root {};

	Node* build() {
		int d {};
		Node* rt {};

		std::cin >> d;

		if (d != -1) {
			rt = new Node(d);
			rt->left = build();
			rt->right = build();
		}

		return rt;
	}

	void show(Node* n) {
		if (n) {
			std::cout << n->data << ' ';
			show(n->left);
			show(n->right);
		}
	}

	void del(Node* n) {
		if (n) {
			del(n->left);
			del(n->right);
			delete n;
		}
	}

public:
	Tree(const Tree&) = delete;
	Tree& operator=(const Tree&) = delete;

	Tree() = default;

	~Tree() {
		del(root);
	}

	void buildTree() {
		root = build();
	}

	void showTree() {
		show(root);
		std::cout << '\n';
	}
};

int main() {
	Tree t;

	t.buildTree();
	t.showTree();
}



1 2 3 -1 -1 4 5 -1 -1 -1 6 -1 -1
1 2 3 4 5 6


Note that the input required would be easier to understand if build() displayed a useful prompt!
jonnin (11437)

Though your OS isn't likely to allow your program to access all of your RAM, it should restrict the amount available for use for the process.


you won't know the difference until you run out of virtual memory too. True, it won't give you 100% as the OS uses some of it, but it can give you more than your ram chips hold, by swapping to disk behind your back. I disagree that it should restrict you, but it may (or probably does) do that... modern OS are always meddling where they should not, putting up artificial walls.
Topic archived. No new replies allowed.