What causes `std::bad_alloc` to get thrown in this code?

Question

I'm trying to solve Leetcode Problem 22 (which is just a pretty simple application of recursion), and I was trying to memoize the results in order to speed up computation. However, when I try to store a list of pointers to vectors I run into a std::bad_alloc error, whereas when I simply store a list of pointers the program runs fine. I'm relatively new to C++ and pointers and memory allocation, so this might be a really stupid question, but I've been looking at the code for a while and I can't seem to figure it out.

So, this is the code:

#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;
}

I'm not quite sure where, or why, but this throws a std::bad_alloc error. However, changing memo to vector<vector<string>> (and changing other various small parts of the code so that it makes sense), it works fine.

What in particular is causing the error here? There's no infinite loop, the recursion has a well defined base case, and I don't think I'm allocating too much memory. I don't see how the program could be failing to allocate memory.

Answer 1

Problem is here:

memo[n] = &result;

Because you are referencing to local variable. You can change it to something like this:

memo[n] = new vector<string>(result);

But remember that you need to free these pointers manually.

Answer 2

As Some programmer dude said in the comments, the culprit is this line

memo[n] = &result;

because you assign a reference to a local variable (result) to memo, which goes out of scope at the end of the function.

(Edit): The solution below is wrong; don't use it.

This can be fixed by moving the declaration vector<string> result; outside of the function, like this:

vector<vector<string>*> memo;
vector<string> result;
vector<string> generateParenthesis_recursive(unsigned int n) {
//...

Consider using smart pointers - if you really need pointers, that is. See: What is a smart pointer and when should I use one?