메모리 누수는 어디에서 발생합니까?

Question

그래서 ArrayList (일명 C++의 벡터) 구현을 직접 작성했으며 여러 알고리즘을 포함 시켰습니다. 이제 내 병합 정렬 방법은 메모리 누수가 될 것 같지만 코드별로 한 줄 씩 지나쳐 삭제에 대한 추적을 추적합니다. 모두 잘될 것 같습니다!

나는 ArrayList의 모든 메소드에 대한 테스트 스크립트를 가지고 있으며 충돌이 발생했다는 것을 알아 두어야한다. 그런 다음 mergesort 테스트를 제거하고 더 이상 작동하지 않게된다. 그러나 흥미로운 점은 항상 충돌이 아니며 때로는 작동하고 다른 충돌은 발생한다는 것입니다.

두 방법의 코드는 아래와 같다 :

빠른 변수 열거 :

배열 = ArrayList를에게

크기 후위 배열 =의 크기를 추적하는 int 정렬.

정렬 = 목록이이 j < size1을인지 확인하기 전에 당신은 array1 [ j ] 액세스하는

/** 
* Runs merge sort on this ArrayList<T>. Interface function to the central, 
* recursive, merge sort function. 
* 
* Runs in O(nlogn) time. However it consumes extra memory. 
*/ 
template<class T> 
void ArrayList<T>::mergeSort() { 

    T* temp = mergeSort(array, size); 
    delete [] array; 
    array = temp; 
    sorted = true; 
} 

/** 
* Runs merge sort on the passed in array. Recursive. 
* 
* Runs in O(nlogn) time. However it consumes extra memory. 
* 
* @param array the array to sort. 
* @param arraySize the size of the array that is to be sorted. 
* @return the sorted array. 
*/ 
template<class T> 
T* ArrayList<T>::mergeSort(T* array, int arraySize) { 

    T* returnArray; 

    //If the array is more than one element. 
    if (arraySize > 1) { 

     int size1 = arraySize/2; 
     int size2 = arraySize - size1; 

     T* array1; 
     T* array2; 

     //Recurse. 
     array1 = mergeSort(array, size1); 
     array2 = mergeSort(array + size1, size2); 

     //Allocate memory for return array. 
     returnArray = new T[arraySize]; 

     //Loop through all elements in returnArray. 
     int i = 0, j = 0, k = 0; 
     while (i < arraySize) { 

      //Place the lesser of two elements in returnArray. 
      if ((array1[j] <= array2[k] && j < size1) 
        || k == size2) { 

       returnArray[i] = array1[j]; 
       j++; 
      } 
      else { 

       returnArray[i] = array2[k]; 
       k++; 
      } 

      i++; 
     } 

     //Free the memory allocated in the recursive calls. 

     delete [] array1; 
     delete [] array2; 
     array1 = 0; 
     array2 = 0; 
    } 
    //If one element is in the passed array. 
    else { 

     //Allocate memory for new array, and assign passed value to it. 
     //This is done so delete can be called in the calling function. 
     returnArray = new T[1]; 
     returnArray[0] = array[0]; 
    } 

    return returnArray; 
} 

Answer 1

를 정렬 여부를 나타내는 부울. j >= size1 인 경우 해당 인덱스에서 배열에 액세스하는 것은 불법입니다. 힙의 메모리 레이아웃에 따라 항상 충돌하는 것은 아니지만 충돌이 발생할 수 있습니다. 확인은 다음과 같아야합니다.

if (((j < size1) && (array1[j] <= array2[k])) || k == size2) { 
...