Не могу найти причину утечки памяти в C ++

Question

Я пытался написать код для умножения матриц, используя алгоритм Штрассена. Код работает, но когда я попытался сравнить результаты с наивным алгоритмом (n ^ 3), используя случайно сгенерированные квадратные матрицы. Во время компиляции предупреждений нет, но память, используемая программой, каким-то образом продолжает увеличиваться. Я новичок в C ++, и указатель - для меня совершенно новая концепция. Даже после устранения неполадок не могу найти утечку памяти. Извините за публикацию всего кода.

#include <iostream>
#include <time.h>
#include <string>

int** MakeMatrix(int size);

bool CheckMatrixEquality(int** a, int** b, int size)
{
    bool isEqual = true;
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            if (a[i][j] != b[i][j])
                isEqual = false;
        }
    }
    return isEqual;
}

int** MatrixMultiplicationNaive(int** a, int** b, int size)
{
    int** res = MakeMatrix(size);
    int temp = 0;
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            for (int k = 0; k < size; k++)
            {
                temp += a[i][k] * b[k][j];
            }
            res[i][j] = temp;
            temp = 0;
        }
    }
    return res;
}

void PrintMatrix(int** mat, int size)
{
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            std::cout << mat[i][j] << " ";
        }
        std::cout << "\n";
    }
    std::cout << "\n";

}

void DeleteMatrix(int** del, int size)
{
    for (int i = 0; i < size; i++)
    {
        delete[] del[i];
    }
    delete[] del;
}

int** MakeMatrix(int size)
{
    int** mat = new int* [size];
    for (int i = 0; i < size; i++)
    {
        mat[i] = new int[size] { 0 };
    }
    return mat;
}

int** AddMatrix(int** a, int** b, int size)
{
    int** add = MakeMatrix(size);
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            add[i][j] = a[i][j] + b[i][j];
        }
    }
    return add;
}

int** SubtractMatrix(int** a, int** b, int size)
{
    int** sub = MakeMatrix(size);
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            sub[i][j] = a[i][j] - b[i][j];
        }
    }
    return sub;
}

int** MatrixMultiply(int** a, int** b , int size)
{
    //base case return
    if (size == 1)
    {
        int** p = MakeMatrix(size);
        p[0][0] = a[0][0] * b[0][0];
        return p;
    }
    int l1 = size / 2;
    int l2 = size - l1;

    //defining new matrices for fragmentation of matrix1
    int** q1_1 = MakeMatrix(l2);

    int** q1_2 = MakeMatrix(l2);

    int** q1_3 = MakeMatrix(l2);

    int** q1_4 = MakeMatrix(l2);

    //defining new matrices for fragmentation of matrix2
    int** q2_1 = MakeMatrix(l2);

    int** q2_2 = MakeMatrix(l2);

    int** q2_3 = MakeMatrix(l2);

    int** q2_4 = MakeMatrix(l2);

    //adding values into smaller matrices from matrix 1 and 2
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            if (i < l1 and j < l1)
            {
                q1_1[i][j] = a[i][j];
                q2_1[i][j] = b[i][j];
            }
            else if (i < l1 and j >= l1)
            {
                q1_2[i][j - l1] = a[i][j];
                q2_2[i][j - l1] = b[i][j];
            }
            else if (i >= l1 and j < l1)
            {
                q1_3[i - l1][j] = a[i][j];
                q2_3[i - l1][j] = b[i][j];
            }
            else if(i >= l1 and j >= l1)
            {
                q1_4[i - l1][j - l1] = a[i][j];
                q2_4[i - l1][j - l1] = b[i][j];
            }
        }
    }

    //multiplications required for strassens algo
    int** p1 = MatrixMultiply(q1_1, SubtractMatrix(q2_2, q2_4, l2), l2);
    int** p2 = MatrixMultiply(AddMatrix(q1_1, q1_2, l2), q2_4, l2);
    int** p3 = MatrixMultiply(AddMatrix(q1_3, q1_4, l2), q2_1, l2);
    int** p4 = MatrixMultiply(q1_4, SubtractMatrix(q2_3, q2_1, l2), l2);
    int** p5 = MatrixMultiply(AddMatrix(q1_1, q1_4, l2), AddMatrix(q2_1, q2_4, l2), l2);
    int** p6 = MatrixMultiply(SubtractMatrix(q1_2, q1_4, l2), AddMatrix(q2_3, q2_4, l2), l2);
    int** p7 = MatrixMultiply(SubtractMatrix(q1_1, q1_3, l2), AddMatrix(q2_1, q2_2, l2), l2);

    //further calculations using p's
    int** q3_1 = SubtractMatrix(AddMatrix(p5, p4, l2), SubtractMatrix(p2, p6, l2), l2);
    int** q3_2 = AddMatrix(p1, p2, l2);
    int** q3_3 = AddMatrix(p3, p4, l2);
    int** q3_4 = SubtractMatrix(AddMatrix(p1, p5, l2), AddMatrix(p3, p7, l2), l2);

    //compiling results
    int** Narr = MakeMatrix(size);

    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            if (i < l1 and j < l1)
            {
                Narr[i][j] = q3_1[i][j];
            }
            else if (i < l1 and j >= l1)
            {
                Narr[i][j] = q3_2[i][j - l1];
            }
            else if (i >= l1 and j < l1)
            {
                Narr[i][j] = q3_3[i - l1][j];
            }
            else if (i >= l1 and j >= l1)
            {
                Narr[i][j] = q3_4[i - l1][j - l1];
            }
        }
    }

    //deleting heap allocated pointers, help!!!
    DeleteMatrix(q1_1, l2);
    DeleteMatrix(q1_2, l2);
    DeleteMatrix(q1_3, l2);
    DeleteMatrix(q1_4, l2);
    DeleteMatrix(q2_1, l2);
    DeleteMatrix(q2_2, l2);
    DeleteMatrix(q2_3, l2);
    DeleteMatrix(q2_4, l2);
    DeleteMatrix(q3_1, l2);
    DeleteMatrix(q3_2, l2);
    DeleteMatrix(q3_3, l2);
    DeleteMatrix(q3_4, l2);
    DeleteMatrix(p1, l2);
    DeleteMatrix(p2, l2);
    DeleteMatrix(p3, l2);
    DeleteMatrix(p4, l2);
    DeleteMatrix(p5, l2);
    DeleteMatrix(p6, l2);
    DeleteMatrix(p7, l2);

    return Narr;
}

int main()
{
    while (true)
    {
        int size = 10;

        srand(time(NULL));

        int** a = MakeMatrix(size);
        int** b = MakeMatrix(size);
        for (int i = 0; i < size; i++)
        {
            for (int j = 0; j < size; j++)
            {
                a[i][j] = rand() % 100;
                b[i][j] = rand() % 100;
            }
        }

        int** resultFast = MatrixMultiply(a, b, size);
        int** resultNaive = MatrixMultiplicationNaive(a, b, size);

        if (CheckMatrixEquality(resultFast, resultNaive, size))
        {
            std::cout << "okie\n";
        }
        else
        {
            PrintMatrix(resultFast, size);
            PrintMatrix(resultNaive, size);
            break;
        }

        DeleteMatrix(a, size);
        DeleteMatrix(b, size);
        DeleteMatrix(resultFast, size);
        DeleteMatrix(resultNaive, size);
    }
}

Я попытался удалить повторяющиеся определения, которые перезаписываются без использования.

Answer 1

В вашем методе MatrixMultiply у вас есть несколько таких строк:

   int** p5 = MatrixMultiply(AddMatrix(q1_1, q1_4, l2), AddMatrix(q2_1, q2_4, l2), l2);
   int** p6 = MatrixMultiply(SubtractMatrix(q1_2, q1_4, l2), AddMatrix(q2_3, q2_4, l2), l2);
   int** p7 = MatrixMultiply(SubtractMatrix(q1_1, q1_3, l2), AddMatrix(q2_1, q2_2, l2), l2);

Проблема в том, что входной параметр этой функции (например, MatrixMultiply) является выходом некоторых вызовов функций, например SubtractMatrix(q1_1, q1_3, l2) или AddMatrix(q2_3, q2_4, l2), l2). Но эти временные входные матрицы никогда не удаляются. Их тоже следует удалить.

Answer 2

Прямая причина утечек памяти, с которыми вы сталкиваетесь, заключается в том, что вы не освобождаете выделенную память с помощью вспомогательных операций, например, в этой строке:

int** p1 = MatrixMultiply(q1_1, SubtractMatrix(q2_2, q2_4, l2), l2);

функция SubtractMatrix будет выделять память для результата, но вы не храните указатель на эту матрицу и не имеете возможности вызвать delete в этой памяти.
При этом, я думаю, вам будет очень полезно прочитать хорошую книгу по C ++ и познакомиться с RAII идиома. std::vector - это контейнер, который (среди прочего) реализует эту идиому для массивов с динамическим размером, и изменение всех ваших функций для возврата векторов векторов вместо этого решит ваши проблемы с утечкой памяти (и сделает DeleteMatrixFunction устаревшим) для Например, вы можете написать свою функцию SubtractMatrix следующим образом:

using MyMatrix = std::vector<std::vector<int>>;
// Creates a size x size matrix with 0 at each position.
MyMatrix MakeMatrix(std::size_t size) {
  MyMatrix result;
  result.reserve(size);
  for (auto i = 0u; i < size; ++i)
    // std::vector<int>(size, 0) creates a vector of length n with each element initalized to 0.
    result.push_back(std::vector<int>(size, 0));
  return result;
}

MyMatrix SubtractMatrix(const MyMatrix& a, const MyMatrix b)
{
    MyMatrix result = MakeMatrix(a.size());
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            result[i][j] = a[i][j] - b[i][j];
        }
    }
    return sub;
}