1

私は先週、このメモリリークを理解しようとして過ごしましたが、この時点で必死です。助けてくれてうれしいです。

メソッドsolve（深さ優先探索を実行）のすべての反復でクラスPartialGraphのインスタンスを作成するクラスSolverがあります。すべての反復で、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は次のようになります。2つの配列があり、どちらもデストラクタで削除されています。すべてのコンストラクターとoperator=は、配列に新しいメモリを割り当てます。（クラスエッジは3つの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は、PartialGraph.cppの53行目でリークしていると言っていますが、ほとんどすべてのインスタンスが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

インスタンスカウンターも作成しましたが、すべてのインスタンスを破棄したようです。私が言ったように、私は本当に必死です、そして助けは歓迎されるでしょう

4

1 に答える 1

0

簡単な答え：デストラクタを直接呼び出すことは絶対にしないでください。代わりに使用deleteするので、どこにでも、pnew->~PartialGraph();が必要delete pnew;です。一般的に、すべてnewが対応するdelete場所を持っている必要があります。複数の削除が1つの新しいものにマップされる可能性があり、その逆もあるため、このルールには注意が必要です。

コードを見ているときに見つけたボーナスリーク：

  • 投稿の実行可能コードの最初の行：this->pg=*new Graph(orig.pg);。別の一般的なルール：もしあなたがそうするコードを持っているなら*new Foo(...)、あなたはおそらくリークを作成しているでしょう（そしておそらくあなた自身のために不必要な仕事を作成しています）。この場合、正常にthis->pg = orig.pg動作するはずです。現在のコードは、orig.pgを新しく割り当てられたオブジェクトにコピーしてから、新しく作成されたオブジェクトをthis-> pgにコピーします。これにより、2つのコピー操作が実行されます。this-> pg=orig.pgは1つのコピーです。
  • 最初の数行PartialGraph::operator =（）。コピーコンストラクタ、代入演算子、およびデストラクタは、正しく理解するのが難しい場合があります。すべてのコンストラクターで、新しいノードとエッジがあり、デストラクタに一致する削除があるので、問題ありません。ただし、代入演算子を実行すると、既存の配列へのポインターが上書きされますが、削除はされません。新しいアレイを作成する前に、既存のアレイを削除する必要があります。

最後に、yikes。StackOverflow用にコードをフォーマットするのは面倒かもしれませんが、インデントがコード構造と一致しないため、Solver ::solve（）でコードを読み取ろうとするのは面倒です。この投稿を見ると、23回の閲覧があり、回答はありませんでした。それはあなたの問題を解決することに興味を持っていたが、おそらくフォーマットによって延期された23人です。コードのフォーマットにさらに23分を費やし、それらの人々のそれぞれを1分以上節約した場合、宇宙をある程度節約できたはずです（おそらく答えを早く得ることに加えて）。

于 2012-11-02T01:07:37.573 に答える