Memory Limit Exceeded when allocating a dynamic 2D array of booleans in c++

Question

I have tried to allocate a dynamic 2D array of booleans for implementing graph in C++. Even though I have declared the graph globally and have done dynamic allocation using new operator yet I am getting memory limit exceeded error on codeforces. I have gone through segmentation fault answers already but all answers ask for dynamic allocation to avoid this error which I have already done.

#include<bits/stdc++.h>
using namespace std;
bool ** g;
bool dfs_h(int n,int k,int src,int *vis){
vis[src]=1;
if(src==k) return true;
for(int i=1;i<=n;i++){
    if(g[src][i]&&!vis[i]){
        if(dfs_h(n,k,i,vis)) return true;
    }
}
return false;
}
bool dfs(int n,int k,int src){
int *vis=new int[n+1]{0};
bool ans=dfs_h(n,k,src,vis);
return ans;
}

main(){
int n,k;
cin>>n>>k;
g=new bool *[n+1];
for(int i=0;i<=n;i++) g[i]=new bool [n+1];
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++) g[i][j]=false;
}
int buf;
for(int i=1;i<n;i++){
    cin>>buf;
    g[i][i+buf]=true;
}
bool ans=dfs(n,k,1);
for(int i=0;i<=n;i++) delete g[i];
delete [] g;
if(ans) cout<<"YES\n";
else cout<<"NO\n";
}

You don't seem to be deleting any memory till the end of the program. Why don't you just use `std::vector`, and avoid manual memory management? — cigien, May 23 '20 at 06:52
The maximum value of `n` is crucial here. Maybe you just don't have enough memory? Maybe you are expected to be able to solve this problem without allocating `n*n` bytes of memory. — john, May 23 '20 at 06:54
A *pointer-to-pointer-to* `bool` will require the allocation of a `pointer` for every block of `bool` you allocate. That can be horribly inefficient due to the pointer size conceivably being 8X the size of each `bool`. — David C. Rankin, May 23 '20 at 06:58
@cigien, I forgot to delete the dynamic array, I will do it now. I didn't use vector of vectors as I am comfortable with 2D array while implementing Graphs. — Ankur Vishwakarma, May 23 '20 at 07:00
@DavidC.Rankin , so what should I do according to you if I wish to allocate a 2D array of bools of size 10000 * 10000 — Ankur Vishwakarma, May 23 '20 at 07:03
Clearly not comfortable enough, since you forgot to delete the memory. For me personally, I find it very hard to remember these things, so I prefer using `vector`. I highly recommend it. it's easy to get used to. — cigien, May 23 '20 at 07:04
@AnkurVishwakarma 100 mega bytes is probably too much. Usually what you are supposed to do with these problems is devise something **smarter** than just the obvious brute force approach. That's probably what you need to do. — john, May 23 '20 at 07:10
@AnkurVishwakarma, also take a look at [why is using namespace std considered bad practice](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice)? — kesarling He-Him, May 23 '20 at 07:12
`std::vector` is a special case that uses bits instead of bytes to store booleans, which reduces memory requirements of the inner arrays eightfold -- maybe this is enough for your use-case. Also, as others have mentioned, vectors are much simpler to use and manage their own memory so you don't have to. All of your initialization (allocating subarrays and initializing the bools to `false`) can be done with a single vector declaration: `std::vector> g{n + 1, std::vector{n + 1, false}};` — cdhowie, May 23 '20 at 07:13
Alternatively, you can use a single vector (`std::vector g{(n + 1) * (n + 1), false};`) which will be more compact, and treat it as two-dimensional (`g[y * g.size() + x]`). — cdhowie, May 23 '20 at 07:15
Adding to @cdhowie, take a look at the [vector docs](https://en.cppreference.com/w/cpp/container/vector) — kesarling He-Him, May 23 '20 at 07:15
Adding to @d4rk4ng31 ;) take a look at the docs for the [`std::vector` specialization](https://en.cppreference.com/w/cpp/container/vector_bool), which differs from a standard vector in a few important ways. — cdhowie, May 23 '20 at 07:17

John Zwinck · Answer 1 · 2020-05-24T03:07:25.990

Let's think about this for the case of n=10000:

g=new bool *[n+1];

That will allocate 640064 bits on a 64-bit system. Then:

for(int i=0;i<=n;i++)
    g[i]=new bool [n+1];

That will allocate 800160008 bits (10001*10001*8).

In total this is more than 95 GB of allocation to store 10001*10001 bits which is fundamentally only 12 GB.

So the first thing you should do is change your storage strategy to use every bit, instead of just one bit per byte, and perhaps a single allocation instead of 10002 allocations. Using a single std::vector<bool> bits(10001*10001) will accomplish this easily, you just need to write an indexing function like bool get(int x, int y) { return bits[x + y * 10001]; }.

Memory Limit Exceeded when allocating a dynamic 2D array of booleans in c++

1 Answers1