Why is there a segmentation fault when I use vector storing vector?-CodePudding

I'm dealing with an algorithm homework which need to be executable on linux(I'm using wsl), and this homework need to store the solution and export to the output file.

To store the solution, I need to open an 2D array of "vectors storing pairs", and at the end, I need to sort the pairs by its first component in the ascending order.

I know that for the first requirement, the running time would be O(N^2)(This is also the standard answer for this dynamic programming problem), and for the second one, I've google C STL, and it says that the algorithm used by c only needs O(NlogN).

(1)It return 'killed' if I use the new to declare 2D array of vector, for the cases that N=10000, but it works fine if N=1000.

[Edited] (2) I check the comment, and they suggest that I should write the code using vector to store vector instead of new. However, when I change to using vectors storing vectors, now the program cannot run, keep throwing segmentation fault.

I don't know where is happening. Can anybody help?

problem description: https://drive.google.com/file/d/1m8ISIGlVGXH3oeyechLbBA1QQVSmsw-q/view?usp=sharing

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

Note:

The .o files are alredy make, finish editing, you need to 'make', and run ./bin/mps [inputfile] [outputfile]
I've modified some code, but it can only run with case N=12, 1000; not for larger N. chord.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;
}

CodePudding user response：

By default, std::vector is constructed with 0 size, and I see that you don't ever resize the vector, but you access its elements by index [i][j]. You have to resize first two (or maybe three) dimensions of 3-dimensional vector sol to fit necessary size, do following resize inside constructor:

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

After this resize change in constructor your program doesn't crash on 10000 input, at least on my Windows laptop.

Also maybe you need to resize two dimensions to bigger than size, you should know better. Also 3rd dimension might be needed to resize too, if you need this by algorithm, up to you. If you need to resize 3rd dimension, then do following (but if I understand your algorithm correctly you don't need this change, resizing 3rd dimension, you need it to be of size 0):

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

(here size1/size2/size3 are three sizes of three dimensions, so that your vector gets 3-dimensional shape (size1, size2, size3), decide what these 3 sizes should be at your algorithm start, I think they should be (size, size, 0))