C++使用嵌套vector存储pair时出现段错误、大N场景程序被Killed如何解决

问题根因 #

1. N=12就段错误的原因 #

你定义的三维嵌套vector vector<vector<vector<pair<int, int>>>> sol 没有做初始化，构造函数里只给data数组申请了空间，sol是完全空的，直接访问sol[i][j]属于越界访问，必然触发段错误。

2. N=10000被系统kill的原因 #

你的存储方案内存开销过大：
O(N²)的二维结构里每个元素都是一个vector<pair<int,int>>，就算是空vector每个也要占至少24字节（STL vector的三个内置指针），N=10000时仅空结构就占100001000024B = 2.4GB，再加上每个vector存储的pair数据，总内存会远超WSL默认分配的内存上限，被系统OOM killer直接终止。

修复方案 #

第一步：修复段错误 #

在Chord类的构造函数里给sol初始化对应大小，修改构造函数代码如下：

Chord::Chord(int tmp){
    size = tmp;
    data = new int [size];
    // 新增：初始化三维vector的大小为size*size
    sol.resize(size, vector<vector<pair<int, int>>>(size));
};

改完之后N=12的场景即可正常运行。

第二步：优化内存适配大N场景 #

你现在的DP状态直接存储完整的结果路径，属于冗余设计，建议拆分逻辑降低内存占用：

• 新增一个纯int类型的二维dp数组，只存区间[i,j]的最大弦数，内存占用极低，N=10000时仅需要400MB左右
• 新增一个二维回溯表，记录每个[i,j]状态的转移类型（匹配到弦、直接继承左区间、拆分到两个子区间）
• DP计算完成后，仅需要从[0, size-1]状态回溯一次，就能构造出完整的结果pair列表，不需要每个状态都存全量结果

改完之后内存开销会降低一个数量级，N=10000的场景也可以正常运行。

其他可优化点 #

你当前代码里的reserve用法无效：reserve只能扩容不能缩容，你是先给sol[i][j]赋值之后再调用reserve，如果预留的空间小于现有元素数量，reserve不会产生任何作用，建议调整为先算好总需要的空间再做预留，或者直接省略多余的reserve调用即可。

内容的提问来源于stack exchange，提问作者jerry