Прекарах миналата седмица, опитвайки се да разбера това изтичане на памет и в този момент съм отчаян. Ще се радвам на всяка помощ.
Имам клас Solver, който създава екземпляр на класа PartialGraph във всяка итерация в метода solve (извършване на първо търсене в дълбочина). Във всяка итерация PartialGraph трябва да се копира в стека и да се унищожи
Solver.h
class Solver {
public:
Solver(Graph pg);
PartialGraph solve(PartialGraph p, int bestest);
Graph pg;
stack<PartialGraph> stackk;
bool isSpanningTree(PartialGraph* p);
Solver(const Solver& orig);
~Solver();
Solver.cpp
Solver:: Solver(const Solver& orig){
this->pg=*new Graph(orig.pg);
}
Solver::Solver(Graph gpg) {
this->pg=gpg;
}
PartialGraph Solver::solve(PartialGraph init, int bestest){
int best=bestest;
int iterace=0;
PartialGraph bestGraph;
stackk.push(init);
while(stackk.size()!=0) {
PartialGraph m = stackk.top();
stackk.pop();
for(int i=m.rightestEdge+1;i<pg.edgeNumber;i++){
*******(line 53 )PartialGraph* pnew= m.addEdge(pg.edges[i]);
if(m.generatedNodes==pnew->generatedNodes){
pnew->~PartialGraph();
continue; }
if(isSpanningTree(pnew)){
if(best>pnew->maxDegree){
best=pnew->maxDegree;
bestGraph=*pnew;
}
if(pnew->maxDegree==2){
pnew->~PartialGraph();
return bestGraph;
}
pnew->~PartialGraph();
continue;
}
if(pnew->maxDegree==best){
pnew->~PartialGraph();
continue; }
stackk.push(*pnew);
*******(line 101 )pnew->~PartialGraph();
}
}
return bestGraph;
}
bool Solver::isSpanningTree(PartialGraph* p){
if(p->addedEdges!=this->pg.nodeNumber-1){return false;}
return p->generatedNodes==this->pg.nodeNumber;
}
Solver::~Solver(){
this->pg.~Graph();
};
PartialGraph изглежда така, има два масива, и двата изтрити в деструктора. Всеки конструктор и operator= заделя нова памет за масивите. (Class Edge държи три int)
PartialGraph::PartialGraph(int nodeNumber,int edgeNumber) {
nodeCount=nodeNumber;
edgeCount=0;
nodes=new int[nodeCount];
edges=new Edge[0];
rightestEdge=-1;
generatedNodes=0;
addedEdges=0;
for(int i=0;i<nodeCount;i++){
this->nodes[i]=0;
}
maxDegree=0;
}
PartialGraph::PartialGraph(const PartialGraph& orig){
this->nodes=new int[orig.nodeCount];
edges=new Edge[orig.edgeCount];
this->nodeCount=orig.nodeCount;
this->rightestEdge=orig.rightestEdge;
this->edgeCount=orig.edgeCount;
this->maxDegree=orig.maxDegree;
this->addedEdges=orig.addedEdges;
this->generatedNodes=orig.generatedNodes;
for(int i=0;i<this->nodeCount;i++){
this->nodes[i]=orig.nodes[i];
}
for(int i=0;i<this->edgeCount;i++){
this->edges[i]=orig.edges[i];
}
}
PartialGraph::PartialGraph(){
}
PartialGraph::PartialGraph(const PartialGraph& orig, int i){
this->nodes=new int[orig.nodeCount];
edges=new Edge[orig.edgeCount+1];
this->nodeCount=orig.nodeCount;
this->rightestEdge=orig.rightestEdge;
this->edgeCount=orig.edgeCount;
this->maxDegree=orig.maxDegree;
this->addedEdges=orig.addedEdges;
this->generatedNodes=orig.generatedNodes;
for(int i=0;i<this->nodeCount;i++){
this->nodes[i]=orig.nodes[i];
}
for(int i=0;i<this->edgeCount;i++){
this->edges[i]=orig.edges[i];
}
}
PartialGraph &PartialGraph::operator =(const PartialGraph &orig){
nodes=new int[orig.nodeCount];
edges=new Edge[orig.edgeCount];
this->nodeCount=orig.nodeCount;
this->rightestEdge=orig.rightestEdge;
this->edgeCount=orig.edgeCount;
this->maxDegree=orig.maxDegree;
this->addedEdges=orig.addedEdges;
this->generatedNodes=orig.generatedNodes;
for(int i=0;i<this->nodeCount;i++){
this->nodes[i]=orig.nodes[i];
}
for(int i=0;i<this->edgeCount;i++){
this->edges[i]=orig.edges[i];
}
}
PartialGraph* PartialGraph::addEdge(Edge e){
PartialGraph* npg=new PartialGraph(*this, 1);
npg->edges[this->edgeCount]=e;
npg->addedEdges++;
npg->edgeCount++;
if(e.edgeNumber>npg->rightestEdge){npg->rightestEdge=e.edgeNumber;}
npg->nodes[e.node1]=npg->nodes[e.node1]+1;
npg->nodes[e.node2]=npg->nodes[e.node2]+1;
if(npg->nodes[e.node1]>npg->maxDegree){npg->maxDegree=npg->nodes[e.node1];}
if(npg->nodes[e.node2]>npg->maxDegree){npg->maxDegree=npg->nodes[e.node2];}
if(npg->nodes[e.node1]==1){npg->generatedNodes++;}
if(npg->nodes[e.node2]==1){npg->generatedNodes++;}
return npg;
}
PartialGraph:: ~PartialGraph() //destructor
{
delete [] nodes;
delete [] edges;
};
PartialGraph.h
class PartialGraph {
public:
PartialGraph(int nodeCount,int edgeCount);
PartialGraph* addEdge(Edge e);
PartialGraph(const PartialGraph& orig);
PartialGraph();
~PartialGraph();
static int counter;
PartialGraph(const PartialGraph& orig, int i);
void toString();
int nodeCount;
int edgeCount;
int generatedNodes;
int *nodes;
Edge *edges;
int maxDegree;
int rightestEdge;
int addedEdges;
PartialGraph &operator =(const PartialGraph &other); // Assn. operator
};
Работи добре, но когато входните данни са твърде големи, получавам лошо разпределение. Valgrind казва, че изтичам на ред 53 на PartialGraph.cpp, но съм почти сигурен, че всички екземпляри са унищожени на ред 101 или по-рано в итерацията.
(244,944 direct, 116 indirect) bytes in 5,103 blocks are definitely lost in
at 0x4C2AA37: operator new(unsigned long)
(in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
by 0x4039F6: PartialGraph::addEdge(Edge) (PartialGraph.cpp:107)
by 0x404197: Solver::solve(PartialGraph, int) (Solver.cpp:53)
by 0x4016BA: main (main.cpp:35)
LEAK SUMMARY:
definitely lost: 246,305 bytes in 5,136 blocks
indirectly lost: 1,364 bytes in 12 blocks
Дори направих брояч на инстанции и изглеждаше, че унищожавам всички инстанции. Както казах, наистина съм отчаян и помощта би била добре дошла