New and Delete

[unborn holly]

Let's say I create a tree in cpp. The tree is made of Node pointers that are initialized using new Node().

After I am done using the tree I have created, do I need to delete it from heap memory? If yes, would I have to loop through all the nodes pointer and delete each of them?

[paper tree]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For more information use !howto ask.

[dim wren]

everything thats allocated with new should be deleted with delete

suggest using smart pointers to do it for you

[autumn dagger]

I suggest not using smart pointers for linked data structures. It's often more convenient, but you lose performance due to hard to explain reasons

[unborn holly]

@autumn dagger what should I use instead

how would a smart pointer know when to delete a node?

[dim wren]

https://www.youtube.com/watch?v=JfmTagWcqoE
Heres a talk that uses trees as an example but it also explains the issue with using smartpointers for linked datastructures
If you dont understand that yet Id look at RAII

[frosty sail]

When it goes out of scope

The parent going out of scope would essentially trigger a chain reaction

But essentially every new must call a delte

( be that in a loop doesn't matter ofc)

So if you can new 10x you need 10x deletes

[unborn holly]

How does it work exactly?

when a function finishes executing, does it call the destructor to all pointers in the local memory?

So then when the destructor of the root is called, it calls the destructor of all pointers inside?

[frosty sail]

Essentially yeah

Well local variables are destructed

Newed memory needs to be freed manually though

[unborn holly]

smart pointer will free memory in the destructor?

[frosty sail]

Yeah they manage the owned resources themselves

Hence the smart

[sturdy lion]

the destructor is a function that gets called when your object dies, when a destructor's body finishes running the fields of the class get destroyed in reverse order of declaration, if the fields is a fundamental type like int or Node pointer, nothing happens, if the field is a class, then that field's destructor gets called

if you are asking how to write a destructor, you are not ready to use smart pointers, use raw pointers

[unborn holly]

when does an object die?

when function finishes?

[sturdy lion]

when it goes out of scope, for local variables,

or when it is heap allocated and you call delete

let me demonstrate

[unborn holly]

@dim wren what does unbounded stack depth mean and why is it an issue?

(from your video)

[dim wren]

one destructor calls the next one and so on until your stack explodes and your program crashes

[unborn holly]

why would it make the stack explode?

there are logn stack calls no? it's just like a dfs

[dim wren]

yup but n is unbounded

its a bigger issue with linked lists

youre right tho its gotta be pretty tricky to actually get a stack overflow from this

[sturdy lion]

void cleanupNodes(Node* root)
{
    if(root->left != nullptr)
    {
        cleanupNodes(root->left);    
    }
    if(root->right != nullptr)
    {
        cleanupNodes(root->right);    
    }
    delete root;
}

if the tree depth does not go to 40 000 or something, this will work

if not, then the iterative solution is needed

void cleanupNodesIteratively(Node* root)
{
    using namespace std;
    
    stack<Node*> s;
    s.push(root);
    
    while(!s.empty())
    {
        Node* current = s.top();
        s.pop();
        
        for(Node* child : {current->left, current->right}
        {
            if(child != nullptr)
            {
                s.push(child);    
            }
        }
        
        delete current;
    }
}

@dim wren

in the Tree destructor you need to call one of these to destroy the tree nodes

some users might chose to use queue to use BFS, well here with DFS and a stack, less memory will be used

(in the average use case)

[unborn holly]

@sturdy lion instead of having log n stack calls, you have local memory of size log n?

but this local memory will be on the stack, so wouldnt this cause overflow?

[sturdy lion]

which function

[unborn holly]

second

[sturdy lion]

it uses the stack, the data structure stack consumes memory from the heap, you have roughly the same ammount of free RAM from the OS available

[unborn holly]

oh yea

it will use heap

[sturdy lion]

the first one runs recursion, that uses the stack frame which is like 2MB

[unborn holly]

both of them are O(n) time ?

[sturdy lion]

yes, n is the node count in the tree

[unborn holly]

ok

so that iterative algorithm is the best way to deallocate heap memory of a tree?

[sturdy lion]

yes

people hate on it because it's longer to write than the recursive one

now, maybe the heap allocations of the iterative approach will be slower due to memory allocations on the heap, the recursion does not allocate anything ever

but in the extreme case, when the tree is a linked list with 40 000 nodes, it will not crash with a stack overflow

@unborn holly

try to make some gigantic binary tree

run the two destruction functions

and comapre run time

[unborn holly]

why is heap allocation slow?

[sturdy lion]

because whenever you allocate on the heap, your process goes "hey mr OS, find me a piece of memory with size sizeof(Node) and give it to me for personal use"

and the OS must find some gap in memory that is available

and return it

that is a system call

and it's not exactly fast

but the stack frame with 2MB preallocated size

is like

wooooosh

[unborn holly]

how does it work? it loops through memory until it finds a block of memory large enough?

[sturdy lion]

I'm fast as fuck boiiii

[sturdy lion]

well... these are the OS's internals, behind malloc

liek VirtualAlloc in microsoft windows

[unborn holly]

okok

also

why did languages like java decide to have garbage collection instead of smart pointers

[sturdy lion]

well referencces in Java are 98% equivalent to smart pointers in C++

but they are not the same

[unborn holly]

but isnt there garbage collection in java where it looks for memory allocated that doesnt have any pointer

[sturdy lion]

in Java, every time you make an object you call operator new, which calls malloc, which calls your OS

it's the same

the JVM decides when the object should be freed, when no one is using it any more

anyways, screw java lmao

[unborn holly]

yeah that

ok

[sturdy lion]

mark this post as !solved

[unborn holly]

ok ty for help

!solved