在c++中分配一个动态二维booleans数组时，超过了内存限制。

Question

我曾试图分配一个动态的2Dbooleans数组，以便在C++中实现图形。尽管我已经声明了图形 全球性 并已 动态分配 使用新的操作符，但我在codeforces上收到内存限制超过的错误。我已经查看了分段故障的答案，但所有的答案都要求动态分配以避免这个错误，我已经做了。

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

Answer 1

让我们考虑一下n=10000的情况。

g=new bool *[n+1];

在64位系统中，将分配640064位。 那么，在64位系统中，将分配640064位。

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

将分配800160008位(10001*10001*8)。

总的来说，这就是超过95GB的分配来存储10001*10001位，而10001*10001位根本上只有12GB。

所以，你首先应该做的是改变你的存储策略，使用每一个比特，而不是每一个字节只用一个比特，或许用单次分配代替10002次分配。 使用单个 std::vector<bool> bits(10001*10001) 就能轻松实现，你只需要写一个类似于 bool get(int x, int y) { return bits[x + y * 10001]; }.