1

我上周一直在试图找出这个内存泄漏，我在这一点上很绝望。我很高兴有任何帮助。

我有类 Solver，它在方法求解的每次迭代中创建类 PartialGraph 的实例（执行深度优先搜索）。在每次迭代中，PartialGraph 都应该被复制到堆栈中，并被销毁

求解器.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();

求解器.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 包含三个整数）

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

部分图.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地方。请注意，这条规则有一些技巧，因为多次删除可能会映射到一个新的，反之亦然。

我在查看代码时发现的额外漏洞：

  • 您帖子中的第一行可执行代码：this->pg=*new Graph(orig.pg);. 另一个一般规则：如果你有这样的代码*new Foo(...)，你可能会造成泄漏（并且可能会为自己创造不必要的工作）。在这种情况下，this->pg = orig.pg应该可以正常工作。您当前的代码将 orig.pg 复制到新分配的对象中，然后将新创建的对象复制到 this->pg 中，这会导致两次复制操作。this->pg = orig.pg 只是一个副本。
  • 前几行 PartialGraph::operator=()。复制构造函数、赋值运算符和析构函数可能很难正确使用。在你的所有构造函数中，你都有新的节点和边，并且你在析构函数中有匹配的删除，所以没关系。但是，当您执行赋值运算符时，您会覆盖指向现有数组的指针，但不会删除它们。在创建新数组之前，您需要删除现有数组。

最后，哎呀。我知道为 StackOverflow 格式化代码可能会很痛苦，但是尝试读取 Solver::solve() 中的代码非常痛苦，因为缩进与代码结构不匹配。当我查看这篇文章时，有 23 次浏览，没有任何回复。那是 23 个人对解决您的问题感兴趣，但可能被格式推迟了​​。如果你多花 23 分钟来格式化代码，并且它为每个人节省了超过一分钟，那么你就会为整个宇宙节省一些时间（除了可能更快地得到你的答案）。

于 2012-11-02T01:07:37.573 回答