So I was implementing Kruskal's algorithm for building a minimum spanning tree given a list of edges (using the union-by-rank with path compression for the DisjointSet ADT).
I have an MST class, an Edge class, a Compare class, and a DisjointSet class.
My main.cpp looks like this:
int main(int argc, char *argv[]) {
std::string numNodes;
std::string numEdges;
// Assume I got the numNodes/numEdges (redacted to reduce clutter)
MST* mst = new MST(std::stoi(numNodes), std::stoi(numEdges));
//parse edges and their corresponding weights (build priority queue)
for(int i = std::stoi(numEdges); i > 0; i--) {
//Assume I got node1,node2, and edgeWeight (redacted to reduce clutter)
Edge* e = new Edge(std::stoi(node1), std::stoi(node2), std::stoi(edgeWeight));
mst->addEdgeToList(e);
}
mst->buildMST();
delete mst;
return 0;
}
My MST class looks like this:
class MST {
public:
MST(); //both constructors initialize all member vars except mst and edges
MST(int nodes, int edges); //they both do: vertices = new DisjointSet(nodes)
~MST() { delete vertices; }
void addEdgeToList(Edge* e);
void buildMST();
void printMst();
private:
std::vector<Edge> mst;
DisjointSet* vertices;
std::priority_queue<Edge*, std::vector<Edge*>, Compare > edges; //min-heap
int numNodes;
int numEdges;
int totalWeight;
int givenEdges;
bool isConnected;
};
Now, what was happening is that I would get a core dump whenever in main I called delete mst
before return 0
. I narrowed it down to the point that I found that the error was in my DisjointSet constructor. My DisjointSet class looks like this:
class DisjointSet {
public:
//DisjointSet(int numElements) : ds(numElements, -1) {} //this causes core dump
DisjointSet(int numElements) { for(int i = numElements; i > 0; i--) { ds.push_back(-1); }}
int find(int x);
void unionSets(int root1, int root2);
private:
std::vector<int> ds;
};
I had been using the commented out constructor: one that should have called the vector (ds) constructor to initialize ds with numElements to have the value -1. The code ran, except when I called delete mst, I got a core dump and through some debugging I found that for some reason whenever it called this constructor it also called the destructor! (What???) The uncommented line of code should be doing the same thing, and this way it doesn't give me a core dump. What is it about delegating constructors that causes this to happen? I know if I run into an exception delegating constructors call the destructor but I shouldn't be getting an exception.
Aucun commentaire:
Enregistrer un commentaire