在 c++ 中分配布尔值的动态二维数组时超出内存限制

Question

我试图分配一个动态的布尔值 2D 数组，以便在C++中实现图形。即使我已经全局声明了图形并使用新运算符进行了动态分配，但我在代码强制上遇到了超出内存限制的错误。我已经经历了分段错误答案，但所有答案都要求动态分配以避免我已经完成的此错误。

#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<<"YESn";
else cout<<"NOn";
}

Answer 1

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

g=new bool *[n+1];

这将在 64 位系统上分配 640064 位。 然后：

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

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

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

因此，您应该做的第一件事是更改存储策略以使用每个位，而不是每个字节仅使用一位，并且可能是单个分配而不是 10002 个分配。 使用单个std::vector<bool> bits(10001*10001)可以轻松完成此操作，您只需要编写一个索引函数，例如bool get(int x, int y) { return bits[x + y * 10001]; }.