c++vectorgraphsegmentation-faultadjacency-list

Segmentation fault on vector class implementation


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;
    }
}

Solution

    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;
        }
    }