Access violation reading location in a destructor of a class

Question

I've built the Graph class, one constructor and one destructor. My problem is: when i compile this code, i get an error at this line delete [] mat[i];, the error is 'Access violation reading location 0xDDDDDDCD.' and i'm not sure what am i doing wrong. I mean i only delete the memory i dynamically alocated. Later edit: even if i use this instead of my method :

Graph(int nr_noduri) {


this->nr_noduri = nr_noduri;
    mat = new bool* [nr_noduri];
    for (int i = 0; i < nr_noduri; i++) {
        mat[i] = new bool[nr_noduri];
    }
    for (int i = 0; i < nr_noduri; i++) {
        for (int j = 0; j < nr_noduri; j++) {
            mat[i][j] = 0;
        }
    }
}

My code is :

 #include <iostream>
#include <cstdlib>
using namespace std;

class Graph {
    bool** mat;
    int nr_noduri;

public:
    Graph(int nr_noduri) {
        this->nr_noduri = nr_noduri;
        mat = (bool**)calloc(nr_noduri, sizeof(bool*));
        for (int i = 0; i < nr_noduri; i++) {
            mat[i] = (bool*)calloc(nr_noduri, sizeof(bool));
        }
    }

    int size() {
        return nr_noduri;
    }

    void addArc(int v, int w) {
        if (v < nr_noduri && w < nr_noduri) {
            mat[v][w] = true;
        }
        else cout << "Not enough nodes !" << endl;
    }

    bool isArc(int v, int w) {
        return (mat[v][w] == true);

    }

    void print() {
        for (int i = 0; i < nr_noduri; i++) {
            cout << endl;
            for (int j = 0; j < nr_noduri; j++) {
                cout << mat[i][j] << " ";
            }
        }
        cout << endl;
    }

    ~Graph() {
        //cout << nr_noduri;
        for (int i = 0; i < nr_noduri; i++) {
            delete [] mat[i];
        }
        delete[] mat;
    }

    friend void dfs(Graph g, int v, bool vazut[]);
};

void dfs(Graph g, int v, bool vazut[]) {
    int w;
    vazut[v] = true;
    for (w = 0; w < g.size(); w++) {
        if (g.isArc(v, w) && !vazut[w]) {
            cout << v << "->" << w;
            dfs(g, w, vazut);
        }
    }
}


int main() {
    int nr_noduri;
    cin >> nr_noduri;
    Graph v(nr_noduri);
    v.print();
    v.addArc(1, 2);
    v.addArc(2, 5);
    cout << v.isArc(1, 2) << endl;
    v.print();
    bool vazut[100];
    dfs(v, 1, vazut);
    return 0;
}

Answer 1

You cannot use delete to deallocate memory that was allocated by calloc (or any of the malloc family of functions). Use new instead to allocate memory.

Graph(int nr_noduri) {
    this->nr_noduri = nr_noduri;
    mat = new bool*[nr_noduri];
    for (int i = 0; i < nr_noduri; i++) {
        mat[i] = new bool[nr_noduri];
    }
}

Better yet, use std::vector<std::vector<bool>> to hold the data.

class Graph {
   std::vector<std::vector<bool>> mat;

   Graph(int nr_noduri) : mat(nr_noduri, std::vector<bool>(nr_noduri) {}

   ...
};

Answer 2

This line:

void dfs(Graph g, int v, bool vazut[])

has the first parameter g passed by value, thus will be a temporary copy of the Graph that is passed in. If Graph does not have correct copy semantics, then the call to dfs will cause undefined behavior.

The Graph contains a member mat that points to dynamically allocated memory. In addition, Graph has a destructor that issues a delete [] on this memory. So when Graph is copied, that mat pointer is also copied. You now have two mat pointers pointing to the same memory. When the temporary goes out of scope, delete [] will be issued on the mat pointer.

That is probably the reason why you are getting runtime issues -- the memory mat was pointing to has already been deleted, and you're deleting it again a second time.

To fix this issue you have two choices:

1. Pass Graph by reference to dfs instead of by value, or
2. Fix your Graph class to handle copies correctly.

For item 1:

void dfs(Graph& g, int v, bool vazut[])

that avoids the temporary copy from being made.

---

However, that to me is just a band-aid solution to avoid having to hit the copy bug (even though you should pass-by-reference anyway).

A better one is to make the Graph class safely copyable, meaning that copies can be made correctly, without a "double deletion" errors you're seeing now.

To do that, add the following functions to complete the rule of 3 to allow copying to be performed correctly:

#include <algorithm>
//…
Graph(const Graph& rhs) : mat(nullptr), nr_noduri(rhs.nr_noduri)
{
    mat = new bool* [rhs.nr_noduri];
    for (int i = 0; i < rhs.nr_noduri; i++) {
        mat[i] = new bool[rhs.nr_noduri];
    }
    for (int i = 0; i < rhs.nr_noduri; i++) {
        for (int j = 0; j < rhs.nr_noduri; j++) {
            mat[i][j] = rhs.mat[i][j];
        }
    }
}

Graph& operator=(const Graph& rhs)
{
    if ( this != &rhs )
    {
        Graph temp(rhs);
        std::swap(temp.mat, mat);
        std::swap(temp.nr_noduri, nr_noduri);
    }
    return *this;
}

Your class was lacking a user-defined copy constructor and assignment operator (which uses the copy / swap idiom).

---

Another unrelated issue is the way you're building your 2D matrix. You're using one of the worst methods, and that is to allocate pointers, then in a loop, allocate each row.

It not only is a bottleneck in terms of speed (calling the allocator for each row), it is not cache-friendly due to the rows being allocated in different parts of the heap, in addition to heap fragmentation, and if one of those calls to new[] within the loop fails, you have to rollback all of the successful calls to new[] if you don't want to leak memory.

See this solution for a better method of creating a 2D array.