Что вызывает появление std :: bad_alloc в этом коде?
Я пытаюсь решить Leetcode Задача 22 (это довольно простое приложение рекурсии), и я пытался запомнить результаты, чтобы ускорить вычисления. Однако, когда я пытаюсь сохранить список указателей на векторы, я сталкиваюсь с ошибкой std::bad_alloc, тогда как когда я просто сохраняю список указателей, программа работает нормально. Я относительно новичок в C++, указателях и распределении памяти, поэтому это может быть действительно глупый вопрос, но я некоторое время смотрел на код и, похоже, не могу его понять.
Итак, это код:
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
vector<string> generateParenthesis(int n) {
if (n == 0) {
return {};
}
return generateParenthesis_recursive(n);
}
vector<vector<string>*> memo;
vector<string> generateParenthesis_recursive(unsigned int n) {
if (n < memo.size()) {
return *(memo[n]);
}
vector<string> result;
if (n == 0) {
result = {""};
}
else if (n == 1) {
result = {"()"};
}
else if (n > 1) {
vector<string> left, right;
for (unsigned int k = 0; k < n; k++) {
left = generateParenthesis_recursive(k);
right = generateParenthesis_recursive(n - k - 1);
for (auto left_parenths : left) {
for (auto right_parenths : right) {
result.push_back("(" + left_parenths + ")" + right_parenths);
}
}
}
}
while (memo.size() <= n) {
memo.push_back(nullptr);
}
memo[n] = &result;
return result;
}
};
int main(int argc, char const *argv[]) {
Solution s;
vector<string> output = s.generateParenthesis(4);
for (auto s : output) {
cout << s << " ";
}
cout << endl;
return 0;
}
Я не совсем уверен, где и почему, но это вызывает ошибку std::bad_alloc. Однако, изменив memo на vector<vector<string>> (и изменив другие различные мелкие части кода, чтобы он имел смысл), он работает нормально.
Что, в частности, вызывает здесь ошибку? Бесконечного цикла нет, рекурсия имеет четко определенный базовый случай, и я не думаю, что выделяю слишком много памяти. Я не понимаю, как программа могла не выделить память.
@Someprogrammerdude А, ладно, я подумал, что это может иметь какое-то отношение к этому. Идея сохранения адреса локальной переменной все еще остается для меня туманной. Это поправимо? Можно ли сохранить указатель на значение result в векторе memo?
@ user3002473 Да, просто переместите определение vector<string> result перед своим определением generateParenthesis_recursive().
Не использовать указатели? В первую очередь сконцентрируйтесь на написании хорошего кода, который работает. Затем, если производительность недостаточно высока (что часто является достаточно хорошо), профилируйте и измерьте, чтобы найти узкие места. Исправьте одно и снова измерьте, чтобы найти следующий. А поскольку оптимизации часто делают код трудным для чтения и понимания (и, следовательно, трудным для сопровождения), напишите комментарии о том, что делает оптимизированный код и почему он это делает именно так.
И возвращайте свои векторы с помощью const &, их копирование дорого!
@MatthieuBrucher ... и довольно дешевый в перемещении или даже бесплатный, если NRVO сработает. В этом случае они не могут быть возвращены с помощью &, потому что они вычисляются в локальной переменной.
Привет, @ user3002473, спасибо, что приняли мой ответ, но, как отметили некоторые другие комментаторы, он на самом деле совсем не работает. Я реализовал «правильную» версию - по крайней мере, мне так кажется. Тем не менее, у меня есть опасения по поводу его производительности и использования памяти - могу ли я опубликовать его в Code Review SE? Я дам ссылку на ваш вопрос и, конечно же, укажу вас как первоначального автора.
@ Marc.2377 Конечно, вперед! Никогда не мешайте поиску правильной информации!
Ответы 2
Проблема здесь:
memo[n] = &result;
Потому что вы ссылаетесь на локальную переменную. Вы можете изменить его примерно так:
memo[n] = new vector<string>(result);
Но помните, что вам нужно освободить эти указатели вручную.
Как сказал Какой-то чувак-программист в комментариях, виновата эта строка
memo[n] = &result;
потому что вы назначаете ссылку на локальную переменную (result) на memo, которая выходит за рамки в конце функции.
(Редактировать): Решение ниже неверно; не используйте это.
Это можно исправить, переместив объявление vector<string> result;за пределами функции, например:
vector<vector<string>*> memo;
vector<string> result;
vector<string> generateParenthesis_recursive(unsigned int n) {
//...
Рассмотрите возможность использования умных указателей - если уж нужны указатели, то есть. См .: Что такое умный указатель и когда мне его использовать?
Вся причина, по которой программистам на C++ настоятельно не рекомендуется использовать коллекции голых указателей, заключается в том, что никогда не ясно, кому принадлежат указанные объекты. Это именно та проблема - вы добавили указатели на объекты в вектор, который вы вернули, и не осознали, что указанные объекты принадлежат функции. В C++ есть простые способы сохранить ясность владения (например, использовать коллекции значений, использовать unique_ptr и т. д.). Пожалуйста, используйте их.
Ваше «исправление» нарушает кучу других вещей (рекурсивные вызовы будут действовать на вектор result, который не начинается с пустого, и вносимые ими изменения повлияют на внешний вектор result, и все записи в memo будут указывать на один и тот же экземпляр ). Короче говоря, это вообще не исправление.
memo[n] = &result;недействителен, посколькуresultявляется локальной переменной в этой функции, что означает, что время ее существования заканчивается с окончанием функции, и указатель становится недействительным.