My code is leaking. How can I solve it?

Question

My code is leaking. I should delete somewhere the array, what I allocated in this line: T* out_array = new T[size1+size2]; But I don't know where and how. Can anyone help me please?

The code:

#include <iostream>
using namespace std;

template <class T>
T* merge(T arr1[], int size1, T arr2[], int size2);

template <class T>
T* merge_sort(T arr[], int n)
{
    if(n < 2){return arr;}
    int mid = n/2;
    T *arr1 = merge_sort<T>(arr,mid);
    T *arr2 = merge_sort<T>(arr+mid,n-mid);
    return merge(arr1, mid, arr2, n-mid);
}

template <class T>
T* merge(T arr1[], int size1, T arr2[], int size2)
{
    int i = 0,j = 0;

    T* out_array = new T[size1+size2];

    while((i < size1) && (j < size2))
    {
        if(arr1[i] >= arr2[j])
        {
            out_array[i+j] = arr2[j];
            ++j;
        }
        else
        {
            out_array[i+j] = arr1[i];
            ++i;
        }
    }
    while(i < size1)
    {
        //copy the reminder
        out_array[i+j] = arr1[i];
        i++;
    }
    while( j < size2)
    {
        out_array[i+j] = arr2[j];
        j++;
    }

    return out_array;
}

int main()
{
    int a[] = {2, 42, 3, 7, 1};
    int *a2 = merge_sort(a,5);
    for (int i = 0; i<= 4 ; ++i) cout << a2[i] << endl;
    delete[] a2;
    return (0);
}

Answer 1

I remember intervening "in urgence" on an application that was leaking badly:

• the improvements needed to be loaded quickly
• the application was already leaking, though less badly
• the non-regressions were known to be incomplete
• the application had never run under valgrind (it's not trivial to run multi-threaded code with tight timeout dependencies under valgrind...)

So, what did I do ? I used grep and removed all calls to new from the code (*).

• in C++03: delete is an error (**) and new is a code smell
• in C++11: both delete and new are an error (**)

And not so surprisingly, all memory leaks disappeared!

Instead of using new, you can use:

• std::vector for a dynamically allocated array
• std::unique_ptr for a dynamically allocated object

• std::shared_ptr in some rare and arcane situations where the actual lifetime of an object obeys complex rules

  (*) or I could have if it had been C++11, in C++03 and in the absence of perfect-forwarding and variadic templates having a make_auto_ptr was not really possible.

  (**) in C++03 it could be argued that an expert writing boost::scoped_ptr (or equivalent) might need it; in C++11 you can build about every abstraction on top of unique_ptr because it's 0-cost.

Answer 2

These are leaking:

T *arr1 = merge_sort<T>(arr,mid);
T *arr2 = merge_sort<T>(arr+mid,n-mid);

Fix with:

template <class T>
T* merge_sort(T arr[], int n)
{
    if(n < 2){return arr;}
    int mid = n/2;
    T *arr1 = merge_sort<T>(arr,mid);
    T *arr2 = merge_sort<T>(arr+mid,n-mid);
    T * res = merge(arr1, mid, arr2, n-mid);
    delete[] arr1;
    delete[] arr2;
    return res;
}

Answer 3

Before you try to solve the problem of memory leak in your implementation, consider this question: is it really necessary to allocate memory for out_array every time you call merge()?

I think the answer is no, instead, allocating memory for an auxiliary array (the same size as arr) once in merge_sort() is enough, and pass this array to merge(). This method could greatly reduce the times of memory allocation and it's easier to manage the memory allocation.

Answer 4

If you want to allocate memory like this, you should use std::unqiue_ptr. Change

T* out_array = new T[size1+size2];

to

std::unique_ptr<T[]> out_array(new T[size1 + size2]);

change the merge_sort signature to return unique_ptr<T[]>, fix arr1 and arr2 types and do not delete it manually at all. This aproach is better than using delete[], cause an exception can be generated in T's operator =. Than, delete[] operator will never be called, you will still leak memory, even if you add deletes as in Erik's answer.