为什么在使用矢量存储矢量时会出现分割错误

Question

我正在处理一个需要在linux上执行的算法作业(我使用的是wsl(，这个作业需要存储解决方案并导出到输出文件。

为了存储该解决方案，我需要打开一个"；向量存储对">，最后，我需要按升序的第一个分量对配对进行排序。

我知道，对于第一个需求，运行时间将是O(N^2)(这也是这个动态编程问题的标准答案(，对于第二个需求，我在谷歌上搜索了C++STL，它说C++使用的算法只需要O(NlogN)。

(1( 如果我使用new来声明向量的2D数组，对于N=10000的情况，它会返回"killed"，但如果N=1000，它会正常工作。

[已编辑](2( 我检查了注释，他们建议我应该使用vector来存储vector，而不是new来编写代码。然而，当我改为使用矢量存储矢量时，现在程序无法运行，不断抛出分段错误。

我不知道发生了什么事。有人能帮忙吗？

问题描述：https://drive.google.com/file/d/1m8ISIGlVGXH3oeyechLbBA1QQVSmsw-q/view?usp=sharing

文件：https://drive.google.com/file/d/1Ci8MXUsX65oVOxKCD1u3YcWiXsKNYToc/view?usp=sharing

注：

1. .o文件已经生成，完成编辑，您需要"生成"，然后运行./bin/mps [inputfile] [outputfile]
2. 我修改了一些代码，但它只能在N=121000的情况下运行；不适用于较大的N。和弦.h：

#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
class Chord {
public:
Chord(int);
~Chord();
void setEndPoint(int, int);
int getMaximumChords();
void print();
int size;
int* data;  //stores the endpoints of the chord
// vector<pair<int,int>>** sol; 
//I recently use this(1), works for N=1000, but killed if N larger
vector< vector< vector<pair<int, int>> >>sol;
//suggest to change to this(2), not working even for N=12, 
//return segmentation fault
int getEndPoint(int);
};

chord.cpp:

#include "chord.h"
#include <iostream>
Chord::Chord(int tmp){ //initialize all elements 0
size = tmp;
data = new int [size];
};
Chord::~Chord(){
delete[] data;
}
void Chord::setEndPoint(int a, int b){
data[a] = b;
data[b] = a;
return;
}
void Chord::print(){
for(int i=0;i<size; i++){
cout << data[i] << endl;
}
return;
}
int Chord::getEndPoint(int a){
return data[a];
}
int Chord::getMaximumChords(){
for(int j=1; j<size; j++){
for(int i=j-1; i>=0; i--){
int k = getEndPoint(j);
if(k==i){ //case 1: ij is the chord
sol[i][j] = sol[i+1][j-1]; //make a copy
sol[i][j].reserve(1);
sol[i][j].push_back(make_pair(i,j));
}else if(k<i || k>j){ //case 2: k outside interval[i,j]
sol[i][j] = sol[i][j-1];
}else{ //case 3: k inside interval[i,j]
if (sol[i][j-1].size() > sol[i][k-1].size() + sol[k+1][j-1].size() + 1){
sol[i][j] = sol[i][j-1];
}else{
sol[i][j] = sol[i][k-1];
sol[i][j].reserve(sol[k+1][j-1].size()+1);
sol[i][j].push_back(make_pair(k,j));
sol[i][j].insert(sol[i][j].end(),sol[k+1][j-1].begin(), sol[k+1][j-1].end()); 
}
}
}
}
sort(sol[0][size-1].begin(), sol[0][size-1].end());
return sol[0][size-1].size();
}

main.cpp

#include <iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include "chord.h"
using namespace std;
int main(int argc, char* argv[]){
if (argc < 3){
printf("Please enter output file name!");
return 0;
}
//import input
fstream fi(argv[1]);
fstream fo;
fo.open(argv[2], ios::out);
int N=0, a=0, b=0;
char buffer[200];
fi >> N;
Chord chord(N);
while(fi>> a >>b){
chord.setEndPoint(a,b);
}
//chord.print();
int ans= chord.getMaximumChords();
//export output
fo << ans <<endl;
for(int i=0; i<chord.sol[0][chord.size-1].size(); i++){
fo << chord.sol[0][chord.size-1][i].first << " " << chord.sol[0][chord.size-1][i].second << endl;
}
fi.close();
fo.close();
return 0;
}

Answer 1

默认情况下，std::vector是用0大小构造的，我看到您永远不会调整向量的大小，但您可以通过索引[i][j]访问其元素。您必须调整三维向量sol的前两个(或三个(维度的大小，以适应必要的size，在构造函数内执行以下调整大小操作：

Chord::Chord(int tmp){ //initialize all elements 0
size = tmp;
data = new int [size];
sol.resize(size, vector< vector<pair<int, int>> >(size));
};

在构造函数中调整大小之后，您的程序不会在10000输入上崩溃，至少在我的Windows笔记本电脑上是这样。

此外，也许您需要将两个维度的大小调整为大于size，您应该更清楚。此外，如果你需要通过算法调整尺寸，可能也需要三维尺寸，由你自己决定。如果您需要调整三维尺寸，请执行以下操作(但如果我正确理解您的算法，则不需要此更改，调整三维尺寸时，需要尺寸为0(：

sol.resize(size1, vector< vector<pair<int, int>> >(size2, vector<pair<int, int>>(size3)));

(这里size1/size2/size3是三维的三个尺寸，所以你的向量得到三维形状(size1, size2, size3)，在你的算法开始时决定这三个尺寸应该是什么，我认为它们应该是(size, size, 0)(