Segmentation fault on vector class implementation

user_18260346 0
Viewed 58

As for many coding tests STL is not allowed so I am trying to implement vector class. To represent the graph I am using an adjacency list. It's giving me segmentation fault at new_allocation method. Also sometimes I get correct output when I run code but when I debug I get SegFault. Following is my code.

#include <iostream>
using namespace std;

template <typename T> class vector{
    T *arr;
    int s;
    int c;
    void new_allocation(){
        T *temp = new T[s + 10];       // SEGMENTATION FAULT HERE
        c = s + 10;
        for (int i = 0; i < s; i++)
            temp[i] = arr[i];
        arr = temp;
        delete[] temp;
    }
    public:
        vector() { s = c = 0; }
        vector(int userVectorSize){
            s = c = userVectorSize;
            arr = new T[userVectorSize];
        }
        void push_back(T data){
            if (s == c)
                new_allocation();
            arr[s] = data;
            s++;
        }
        T operator[](int index){ return arr[index]; }
        int size() { return s; }
};

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> graph[n + 1];

    for (int i = 0; i < m; i++){
        int v1, v2;
        cin >> v1 >> v2;
        graph[v1].push_back(v2);
        graph[v2].push_back(v1);
    }

    for (int i = 1; i <= n; i++){
        cout << i << " -> ";
        for (int k = 0; k < graph[i].size(); k++)
            cout << graph[i][k] << " ";
        cout << endl;
    }
}
adjacency-list vector graph segmentation-fault c++
3 Answers

this is never going to work

     arr = temp;
    delete[] temp;

you place 'temp' pointer in arr (your working buffer of data elements) and then delete it, so arr points at deleted memory

user_1733970
  1. please initialize the arr in the default ctor:
    vector() {
        s = c = 0;
        arr = nullptr; // (1)
    }
  1. As pm100 mentioned, please pick up the right array to delete[].
    void new_allocation() {
        T *temp = new T[s + 10]; // SEGMENTATION FAULT HERE
        c = s + 10;
        for (int i = 0; i < s; i++)
            temp[i] = arr[i];

        // (2)
        if (arr != nullptr) {
            delete[] arr;
        }
        arr = temp;
    }

The reason is that your arr is pointed to arbitrary memory by default, so it will still report a Segmentation fault when you try to delete[] arr.

#include <iostream>
using namespace std;

template <typename T> class vector {
    T *arr;
    int s;
    int c;
    void new_allocation() {
        T *temp = new T[s + 10]; // SEGMENTATION FAULT HERE
        c = s + 10;
        for (int i = 0; i < s; i++)
            temp[i] = arr[i];

        if (arr != nullptr) {
            delete[] arr;
        }
        arr = temp;
    }

  public:
    vector() {
        s = c = 0;
        arr = nullptr;
    }
    vector(int userVectorSize) {
        s = c = userVectorSize;
        arr = new T[userVectorSize];
    }
    void push_back(T data) {
        if (s == c)
            new_allocation();
        arr[s] = data;
        s++;
    }
    T operator[](int index) { return arr[index]; }
    int size() { return s; }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> graph[n + 1];

    for (int i = 0; i < m; i++) {
        int v1, v2;
        cin >> v1 >> v2;
        graph[v1].push_back(v2);
        graph[v2].push_back(v1);
    }

    for (int i = 1; i <= n; i++) {
        cout << i << " -> ";
        for (int k = 0; k < graph[i].size(); k++)
            cout << graph[i][k] << " ";
        cout << endl;
    }
}
user_152135430

you should delete arr instead of temp:

    void new_allocation(){
        T *temp = new T[s + 10];       // SEGMENTATION FAULT HERE
        c = s + 10;
        for (int i = 0; i < s; i++)
            temp[i] = arr[i];
        delete[] arr;
        arr = temp;
    }
user_153921460
Related