进入main之前C++中的分段错误

Question

这是一个很常见的问题，我尝试阅读解决方案，但似乎没有一个能解决我的问题。这是我写的代码，我知道它很乱，因为我是C++的新手。

#include<iostream>
#include<string>
#include<iomanip>
#include<set>
#include<queue>
#include<cmath>
#include<algorithm>
#include<vector>
#include<limits.h>
#include<math.h>
#include<map>
#include<cstring>
using ll = long long;
const int N = 2e6+6;
int main(){
std::ios_base::sync_with_stdio(0);
std::cin.tie(0);
int n,m;
std::cin >> n >> m;
std::vector<std::array<int,3>> edges;
int exist[n][n];
memset(exist,0,sizeof(exist));
for(int i = 0; i < m;++i){
int a,b;
char c;
std::cin >> a >> b >> c;
--a,--b;
edges.push_back({a,b,c-'a'});
exist[a][b] = exist[b][a] = 1;
}
std::vector<int> adj[N];
std::map<std::pair<int,int>,int> nodes;
int node = 0;
for(int i = 0; i < m;++i){
for(int j = 0; j < m;++j){
if(i == j)
continue;
if(edges[i][2] != edges[j][2])
continue;
int a = edges[i][0];
int b = edges[i][1];
int c = edges[j][0];
int d = edges[j][1];
if(nodes[{a,c}] == 0)
nodes[{a,c}] = ++node;
if(nodes[{b,d}] == 0)
nodes[{b,d}] = ++node;
if(nodes[{a,d}] == 0)
nodes[{a,d}] = ++node;
if(nodes[{b,c}] == 0)
nodes[{b,c}] = ++node;
adj[nodes[{a,c}]].push_back(nodes[{b,d}]);
adj[nodes[{b,d}]].push_back(nodes[{a,c}]);
adj[nodes[{a,d}]].push_back(nodes[{b,c}]);
adj[nodes[{b,c}]].push_back(nodes[{a,d}]);
}
}
int start = nodes[{0,n-1}];
int ans = 1e9+7;
std::queue<int> q;
q.push(start);
std::vector<int> dist(node+1,-1);
dist[start] = 0;
std::vector<bool> visited(node+1,false);
visited[start] = true;
auto it = nodes.begin();
while(!q.empty()){
int cur_node = q.front();
q.pop();
for(int i = 0; i < (int)adj[cur_node].size();++i){
int next_node = adj[cur_node][i];
if(!visited[next_node]){
q.push(next_node);
visited[next_node] = true;
dist[next_node] = dist[cur_node] + 1;
}
}
}
for(int i = 0; i < n;++i){
for(int j = 0; j < n;++j){
int node = nodes[{i,j}];
if(node == 0)
continue;
if(dist[node] == -1)
continue;
if(i == j || (exist[i][j] == 1)){
ans = std::min(ans,dist[node]);
}
}
}
if(ans == 1e9+7)
ans = -1;
std::cout << ans << "n";
}

这个程序甚至在进入main之前就出现了分段错误，我尝试使用gdb，它也说错误在int main()线上。我根本不明白发生了什么，我也试着在C++14和C++17上运行这个程序，它运行得很好，但我使用的是C++11，它编译成功，但没有运行。请帮帮我。

Answer 1

您在堆栈中的代码中分配了超过200万个std::vector。通常堆栈不是很大，所以肯定会超出保留空间并导致问题。本地对象的分配发生在函数中的任何代码运行之前，因此它看起来像是在函数中崩溃，但在任何代码运行前。

std::vector<int> adj[N];

如果你需要那么多向量，你需要动态地分配它。

Answer 2

首先，这不是有效的C++：

int n;
cin >> n;
int exist[n][n];  // <-- not valid C++

C++中的数组的大小必须由编译时表达式表示，而不是由运行时值表示。C++不支持可变长度数组。

编译的代码，因为有些编译器默认情况下支持此功能。但是它仍然没有得到C++语言规范的支持。例如，Visual C++编译器不支持此语法。如果您试图使用Visual C++编译代码，则会收到相应的错误消息。

即使支持这一点，n的大值也可能会破坏堆栈内存，因为堆栈内存是有限的。

第二个问题是你有这个：

std::vector<int> adj[N];

如果N较大，则为Nstd::vector<int>的阵列。同样，这很可能会耗尽堆栈内存。

---

一种解决方案是使用std::vector<std::vector<int>>:

std::vector<std::vector<int>> exist(n, std::vector<int>(n));
//...
std::vector<std::vector<int>> adj(N):

由于向量从堆中获取内存，因此堆栈内存耗尽问题就消失了。