Утечка памяти в рекурсии

Question

Я пытаюсь реализовать алгоритм, используя рекурсию. В рекурсии я выделяю память, используя новую, а затем удаляю ее, но все же получаю утечки памяти. Я попытался понять, что я делаю неправильно, но не мог понять. Может ли кто-нибудь посмотреть, пожалуйста?

• Я знаю, что могу использовать векторы, но хотел бы понять, что я сделал не так, и как исправить это.

это код:

#include <iostream> 
#include <fstream> 
#include <math.h> 
#define _CRTDBG_MAP_ALLOC 
#include <stdlib.h> 
#include <crtdbg.h> 
using namespace std; 



int sortInv(int*,int); 
int Sort_And_count_split_Inv(int*,int,int,int); 
int Sort_And_count(int *,int,int); 

int main() 
{ 
    _CrtSetDbgFlag (_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF); 
    int Siz = 9; 
    int Arr[9] = {66,3,11,76,93,9,22,56,89};  
    int b = Sort_And_count(Arr,0,Siz-1); 
    for (int i=0; i<Siz; i++) 
     Arr[i] = Arr[i]; 
    return 0; 
} 

int Sort_And_count(int *a,int low,int high) 
{ 
    int mid; 
    int n = 0; 
    if (low >= high) 
     return 0; 
    else 
     mid = (high+low)/2; 
     n+= Sort_And_count(a,low, mid); 
     n+= Sort_And_count(a, mid+1, high); 
     n+= Sort_And_count_split_Inv(a,low,mid,high); 
     return n; 
} 

int Sort_And_count_split_Inv(int* a, int low, int mid, int high) 
{ 
    int i,j,k; 
    i=low; 
    j=mid+1; 
    k=low; 
    int count = 0; 
    int* tmp = new int[high-low+1]; 
    while (i<=mid && j<=high) 
    { 
     if (a[i]<a[j]) 
     { 
      tmp[k] = a[i]; 
      i++; 
     } 
     else 
     { 
      tmp[k] = a[j]; 
      j++; 
      count += mid-i == 0? 1: mid+1-i; 
     } 
     k++; 
    } 
    while (i<=mid) 
     tmp[k++] = a[i++]; 
    while (j<=high) 
     tmp[k++] = a[j++]; 
    for (i=low; i<=high; i++) 
     a[i] = tmp[i]; 
    delete[] tmp; 
    _CrtDumpMemoryLeaks; 
    return count; 
} 

Answer 1

Компиляция кода и запустить его в valgrind производит это как первое появление вашей утечки памяти:

==20797== Invalid write of size 4 
==20797== at 0x400BA0: Sort_And_count_split_Inv(int*, int, int, int) (in /home/test/TestCPP) 
==20797== by 0x4009D4: Sort_And_count(int*, int, int) (in /home/test/TestCPP) 
==20797== by 0x4009BC: Sort_And_count(int*, int, int) (in /home/test/TestCPP) 
==20797== by 0x4009A2: Sort_And_count(int*, int, int) (in /home/test/TestCPP) 
==20797== by 0x400921: main (in /home/test/TestCPP) 
==20797== Address 0x5a1d0ec is 4 bytes after a block of size 8 alloc'd 
==20797== at 0x4C2B800: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==20797== by 0x400AE8: Sort_And_count_split_Inv(int*, int, int, int) (in /home/test/TestCPP) 
==20797== by 0x4009D4: Sort_And_count(int*, int, int) (in /home/test/TestCPP) 
==20797== by 0x4009BC: Sort_And_count(int*, int, int) (in /home/test/TestCPP) 
==20797== by 0x4009A2: Sort_And_count(int*, int, int) (in /home/test/TestCPP) 
==20797== by 0x400921: main (in /home/test/TestCPP) 

Я прибил его вниз к этому line:

tmp[k] = a[i]; 

Эта мера ns, что k достигает числа, большего, чем длина выделенного массива int[]. Поскольку вы выделяете длину high - low + 1 и k = low, вы превзошли границу 2*low = high + 1.

я не вдаваться в подробности о вашем фактическом алгоритме сортировки и почему вы питаетесь в неправильном low (или high), но это, где ваша утечка памяти приходит.