Распределение памяти в рекурсивных вызовах C ++

Question

У меня проблемы с выделением и освобождением памяти в рекурсивной программе на C ++. Поэтому, не используя решение для автоматического управления памятью, мне интересно, сможет ли кто-нибудь помочь мне устранить утечку памяти, которую я испытываю.

Следующий код по существу объясняет проблему (хотя это надуманный пример, пожалуйста, исправьте все ошибки или упрощения, которые я сделал).

Числовой класс для хранения значения числа:

class Number {
    public:
        Number() { value = 1; };
        Number& operator + (const Number& n1) const {
            Number result = value + n1.value;
            return result;
        };
        int value;
};

Две функции для выполнения рекурсии:

Number& recurse(const Number& v1) {
    Number* result = new Number();
    Number one = Number();
    *result = *result + recurse(one);
    return *result;
}

int main(...) {
    Number answer = Number();
    answer = recurse(result);
}

Как вы можете видеть, память, выделенная в функции рекурсии, просочилась, но я не уверен, где можно освободить эту память в зависимости от характера рекурсии?

Answer 1

Проблема здесь:

Number& operator + (const Number& n1) const {
    Number result = value + n1.value;
    return result;
};

Вы возвращаете локальную переменную (result) по ссылке, и это большая НЕТ-НЕТ. Локальные переменные размещаются в стеке, и когда функция завершается, переменные исчезают. Возвращение ссылки на локальную переменную возвращает указатель в стек, который теперь используется для чего-то другого, и это вызовет много неприятностей.

Вместо этого вы должны возвращать значение (просто измените тип возврата с Number& на Number). Убедитесь, что у вас есть соответствующий конструктор копирования или что автоматически сгенерированный конструктор копирования компилятора соответствует вашим потребностям. Это означает, что когда возвращается operator+, он делает копию (что часто может быть оптимизировано), а поскольку нет указателей или ссылок, вы не можете получить поврежденное возвращаемое значение.

Чтобы исправить утечку памяти, вы можете использовать умные указатели, такие как boost::shared_ptr. Кроме того, можно использовать указатели рва и динамическую память и просто возвращать результаты по значению из recurse().

Answer 2

Я не понимаю, почему вы выделяете память в куче для начала:

Number& recurse(const Number& v1) {
    Number result;
    Number one;

    // I assume there is a step here to determine if the recursion should stop

    result += recurse(one);
    return result;
}

Располагая только в стеке, вы гарантируете, что переменные будут очищены при возврате функции.

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

Answer 3

Итак, я вижу три другие проблемы в коде, кроме возврата адреса локальной переменной, на которую указал Адам Розенфилд.

Во-первых, ваша функция восстановления никогда не закончится. В какой-то момент в recurse () вы должны проверить значение, которое не вызывает повторного вызова recurse () и просто возвращает. Это фундаментальная часть рекурсии. Переданный аргумент, v1, также не используется.

Во-вторых, оператор + () на самом деле не работает. Невозможно назначить int для объекта Number ().

В-третьих, в main вы передаете то, что называется result, который никогда не объявляется.

Забывая об этих ошибках, я предполагаю, что вы хотите разместить все объекты в куче, чтобы избежать переполнения стека, когда эта функция будет повторяться много раз или фактический используемый объект будет намного больше, чем Number. В этом случае, размещая возвращаемую переменную в куче внутри recurse (), вы заставляете вызывающую сторону удалить возвращаемый объект. Поэтому после вызовов recurse () в recurse () и main () вам придется удалить возвращаемое значение. Соглашение о том, чтобы указать это вызывающей стороне, должно возвращать указатель вместо ссылки. Поэтому recurse () и main () будут выглядеть примерно так:

Number* recurse(const Number& v1) {
    Number* result = new Number();
    Number one;
    if(v1.value >= 2) {
        Number temp;
        temp.value = v1.value - 1;
        Number* partialResult = recurse( temp ); //capture the object to delete
        *result = *partialResult + one;
        delete partialResult;                    //delete the object
    }
    return result;
}

int main() {    
    Number result;
    result.value = 15;
    Number *answer;
    answer = recurse(result);
    delete answer;
}

Примечание: все, что вычисляет рекурсор, бессмысленно. Я не знаю, каковы намерения, но это просто то, что работает.

Answer 4

Есть ли какая-то причина, по которой вы динамически распределяете память?

Number recurse(const Number& v1) {
    Number result;
    Number one;
    retun result + recurse(one);
}

Также я заметил, что вы не используете значение v1

Но большая ошибка в том, что у рекурсии есть NO escape-предложение.
По сути, это бесконечная рекурсия, которая в основном исчерпает память.

Answer 5

Умные указатели - ваш друг. Сделайте быстрое чтение auto_ptr как минимум.

Кроме того, прочтите комментарий Адама Розенфилда о вашей другой проблеме (возвращая ссылку на значение, которого больше не существует).