Query related to memory management in C++

Question

Hi i have a general query regarding memory management in C++. With the help of this program only i understood that new is used to allocate memory on heap and temporary variables are allocated memory on stack.And that if we are allocating memory on the heap we have to free it also manually else there will be memory leak.

But in the program i am updating an object of BST struct in a function named Insert by creating a new variable temp of type BST on heap.But then i am not sure how to free that memory.If i use the free command at the end of the function i.e free(temp) then the value stored at that memory will be lost and i will get an error if i try to access it again,and i certainly cannot use free(temp) in main as it is not a local variable to main. Can some one tell me what should be done.

Btw i must mention that without using free(temp) also my program is working correctly but then i guess memory leak is happening which is bad.

Also i am a little confused as why my program is running without errors if i comment the destructor ~BST() but giving linker errors when i uncomment it.

#include<iostream>
#include<string>
#include<conio.h>
#include<array>
#include<stack>
#include<sstream>
#include<algorithm>
#include<vector>
#include<ctype.h>//isdigit
#include<deque>
#include<queue>
#include<map>
using namespace::std;
struct BST
{
    int data;
    BST *left;
    BST *right;
    BST(int d,struct BST* l,BST *r):data(d) , left(l) ,right(r)
    {
    }

    BST()
    {
    }
    //~BST();
};

void levelOrder(struct BST *root)
{
    struct BST *temp=NULL;
    int count =0;
    deque<struct BST*> dq;
    if(!root)
    {
        return;
    }
    dq.push_back(root);
    count=dq.size();
    while(!dq.empty())
    {
        temp=dq.front();
        cout<<temp->data<<" ";
        if(temp->left)
        {
            dq.push_back(temp->left);
        }
        if(temp->right)
        {
            dq.push_back(temp->right);
        }
        dq.pop_front();
        if(--count==0)
        {
            cout<<endl;
            count=dq.size();
        }
    }
}
void Insert(struct BST*root,int data)
{
    //struct BST temp(data,NULL,NULL);
    BST *temp = new BST(data,NULL,NULL);
    temp->data =data;
    temp->left= NULL;
    temp->right=NULL;
    if(!root)
    {
        return;
    }
    while(root)
    {
        if((root)->data >data)
        {
            (root)=(root)->left;
            if(!(root)->left)
            {
                (root)->left=temp;
                break;
            }
        }
        else
        {
            (root)=(root)->right;
            if(!(root)->right)
            {
                (root)->right=temp;
                break;
            }
        }
    }
}
int main()
{
    deque<struct BST> dq1,dq2;
    BST e(4,NULL,NULL);
    BST f(3,NULL,NULL);
    BST d(1,&f,NULL);
    BST b(2,&d,&e);
    BST c(8,NULL,NULL);
    BST a(6,&b,&c);

    levelOrder(&a);
    Insert(&a,5);
    cout<<a.left->right->right->data;
    cout<<endl;
    levelOrder(&a);
    _getch();
    return 0;
}

Answer 1

First of all, you should use new and delete for memory management in C++, not malloc() and free().

With that said, note that you assign another pointer, either left or right to point to the memory which is originally allocated to the variable temp. Your tree will give you access to the allocated memory, albeit via other variables than the original temp variable. This means that you can delete the memory using these variables in your BST class. Typically this is done inside the destructor.

Note that you are managing memory here, not variables. Let's look at the difference with a simple example:

int main() {
    int* intPtr = new int;
    int* temp = intPtr;

    delete temp;
    temp = NULL;
}

As you can see, this code allocates a single block of memory to store an int. This memory has two pointers to it. You can delete the memory with either pointer, just as long as you don't delete with both. This is definitely a balancing act when you learn about memory management. You must be sure that all memory is deallocated while never attempting to deallocate the same block of memory twice.

Answer 2

Both constructors should assign default values to the left right members, at least NULL; They should not be assigned values outside the class. Add default parameters to the constructor. To avoid leakage you should not create the object until you need it. Alternatively have a flag, initially false, that you set to true if you've used it. And then delete on return if the flag is still false.

Answer 3

First, in C++ you should generally use new and delete (they call ctors/dtors, etc.) For arrays, use delete[]. new/delete is not compatible with malloc/free.

I guess BST is a binary search tree. So you have a tree of dynamically allocated memory.

You must free this whole tree, and which means you should do it in order too, lest you get dangling pointers.

One could significantly reduce the complexity by making sure that a BST-node always free's its children. Then when you delete the root node, it will recursively delete all the other nodes.

In my opinion, the easiest way to do this is to use a smart pointer, like shared_ptr<T>, unique_ptr<T> or auto_ptr (the last one has caveats, but I'm not gonna address them here.)

The structure would then look like:

struct BST
{
  /* ctor, dtor omitted for brevity. */

  std::unique_ptr<BST> left;
  std::unique_ptr<BST> right;
}

Your BST-node goes out of scope, that is, you delete it, or it is allocated on the stack and the code exits the block. The destructors for left and right is called and the unique_ptr implementation makes sure to call delete on the pointer it stores.

Answer 4

The BST *temp created in your Insert method is the new node/subtree that you insert, you don't want to delete it until either the entire tree is destroyed or the node is deleted in some kind of Delete function that you haven't written yet.

Regarding your last point:

Running this particular program without a destructor will leak memory, but not access any invalid memory segments, that's why it runs without any errors.

When you uncomment the destructor declaration in your code, you get linker errors because you haven't defined the destructor, you have just told the compiler/linker that there should be a destructor, but there is none. Even if you just want an empty one, it would have to be ~BST() {}.