Kann ich Speicherleckage von C++ Code fragen?

Question

#include<iostream> 
#include<vector> 
#include<list> 
#include<string> 

using namespace std; 

class Edge; 

class Node 
{ 

    public : 

    int cost; 

    vector<Edge* > edges; 

    Edge* from; 

    string name; 

    bool onq; 

    Node() 
    { 
     cost = 100; 
     from = NULL; 
     onq = false; 
    } 

    ~Node() 
    { 
     vector<Edge *>().swap(edges); 
     delete from; 
    } 


    void clear() 
    { 
     cost = 0; 
     vector<Edge *>().swap(edges); 
     from = NULL; 
    } 
}; 

class Edge 
{ 
    public: 

    Node* destination; 

    int capacity; 

    int cost; 

    Edge* dual; 

    Edge() 
    { 
    } 

    ~Edge() 
    { 
     vector<Edge*>().swap(destination->edges); 

     delete destination; 

     delete dual; 

     destination = NULL; 
     dual = NULL; 
    } 

    Edge(Node* n, int c, int s) 
    { 
     capacity = c; 

     cost = s; 

     destination = n; 

     dual = NULL; 
    } 

}; 

int MCMF(Node* src, Node* snk, vector<Node*> &nodes) 
{ 
    int result = 0; 

    list<Node* > queue; 

while(true) 
{ 
    for(int i = 0 ; i < nodes.size() ; ++i) 
    { 
     nodes.at(i)->cost = 100; 
     nodes.at(i)->from = NULL; 
    } 

    src->cost = 0; 

    queue.clear(); 
    queue.push_back(src); 

    src->onq = true; 

    int count = 0; 

    while(!queue.empty()) 
    { 
     Node* node = queue.front(); 
     queue.pop_front(); 
     node->onq = false; 

     for(int i = 0 ; i < node->edges.size() ; ++i) 
     { 
      Edge* edge = node->edges[i]; 

      if(edge->capacity > 0 && node->cost + edge->cost < edge->destination->cost) 
      { 
       edge->destination->cost = node->cost + edge->cost; 

       edge->destination->from = edge; 

       if(!edge->destination->onq) 
       { 
        edge->destination->onq = true; 
        queue.push_back(edge->destination); 
       } 
      } 
     } 
    } 

    if(snk->from == NULL) 
     break; 

    int min = 0x7FFFFFFF; 

    for(Node* node = snk ; node->from != NULL ;) 
    { 
     Edge* edge = node->from; 

     if(edge->capacity < min) 
      min = edge->capacity; 

     node = edge->dual->destination; 
    } 

    for(Node* node = snk ; node->from != NULL ;) 
    { 
     Edge* edge = node->from; 

     edge->capacity -= min; 

     edge->dual->capacity += min; 

     node = edge->dual->destination; 
    } 
    result += snk->cost; 


    for(list<Node*>::iterator iter = queue.begin() ; iter != queue.end() ; ++iter) 
     delete (*iter); 

    queue.clear(); 

} 

return result; 

} 

void link(Node *node1, Node *node2, int capacity, int cost) 
{ 
    Edge* e1 = new Edge(node2, capacity, cost); 
    Edge* e2 = new Edge(node1, 0, -cost); 

    e1->dual = e2; 
    e2->dual = e1; 

    node1->edges.push_back(e1); 
    node2->edges.push_back(e2); 

} 

int main() 
{ 
    int n, m; 

    vector<Node* > nodes; 

    while(cin >> n >> m) 
    { 
     if(n == 0 && m == 0) 
      break; 

     nodes.clear(); 

     Node* source = new Node(); 
     nodes.push_back(source); 

     Node* sink = new Node(); 
     nodes.push_back(sink); 

     vector<vector<Node* > > position(n); 

     for(int i = 0 ; i < n ; ++i) 
     { 
      int p; 

      cin >> p; 

      position[i] = vector<Node*>(p); 

      for(int j = 0 ; j < p ; ++j) 
      { 
       Node* node = new Node; 

       position[i][j] = node; 


      nodes.push_back(node); 

      link(node, sink, 1, 0); 
     } 
    } 

    for(int i = 0 ; i < m ; ++i) 
    { 
     Node* student = new Node(); 

     nodes.push_back(student); 

     link(source, student, 1, 0); 

     int year, cost; 

     cin >> year; 
     cost = 13 - year*4; 

     for(int j = 0 ; j < 4 ; ++j) 
     { 
      int pre; 
      cin >> pre; 

      for(int k = 0 ; k < position[pre].size() ; ++k) 
      { 
       link(student, position[pre][k], 1, cost+j); 
      } 
     } 
    } 

    cout << 13*m-MCMF(source, sink, nodes) << endl; 

    delete source; 
    delete sink; 

    for(vector<vector<Node*> >::iterator iter1 = position.begin() ; iter1 != position.end() ; ++ iter1) 
     for(vector<Node*>::iterator iter2 = (*iter1).begin(); iter2 != (*iter1).end() ; ++iter2) 
      delete (*iter2); 

    vector<vector<Node *> >().swap(position); 

    vector<Node*>().swap(nodes); 
    } 
} 

das ist mein ganzer Code

dieser Code erstellt für MCMF Graph-Algorithmus

Ich gebe diesen Code zu Algorithmus Website aber nicht, weil der Speicher Überschuss

dieser Code mehr als 128 MB hat ... .

ich denke, dass

ich versuche, fangen Speicherleck in Link-Funktion nicht frei Speicher zugewiesen in Visual Studio dann erschienen viele log, aber ich kann nicht glauben, Lösung

Im sorry, um Code der Länge

kann ich Lösung diese Zuordnung

Sie danken

Answer 1

Diese Fragen sind so gut wie unmöglich zu beantworten, weil niemand wirklich weiß, was in der Online-Richter vor sich geht, aber hier ist ein Brummen-dinger eines Speicherverlust für Sie zu beheben:

Klasse Node s destructor,

~Node() 
{ 
    vector<Edge *>().swap(edges); 
    delete from; 
} 

delete s ein Edge vor Edge ‚s destructor definiert wurde. Das ist uncool, weil das Programm den-Destruktor nicht aufrufen kann, um Ressourcen freizugeben, die Edge besitzt. Und es sieht aus wie ~Edge alles andere als trivial ist:

~Edge() 
{ 
    vector<Edge*>().swap(destination->edges); 

    delete destination; 

    delete dual; 

    destination = NULL; 
    dual = NULL; 
} 

Keiner dieser Code wird immer laufen. Übrigens ist die Einstellung von destination und dual auf NULL verschwendeter Aufwand. Diese Edge ist in ein paar Taktzyklen verschwunden, also wird sich niemand darum kümmern.

Auch, vector<Edge*>().swap(destination->edges); wird fast sicher nicht tun, was Sie tun wollen. Es befreit keines von diesen Edge s. Es bewegt nur die Zeiger auf ein temporäres Objekt, das kurz davor ist, den Bereich zu verlassen und diese Kantenzeiger für immer zu verlieren.

Lösung:

Verschieben ~Node, die nach der Definition von ~Edge

class Node 
{ 
    ... 
    ~Node(); // declare only 
    ... 
}; 

class Edge 
{ 
    ... 
}; 

Node::~Node() 
{ 
    vector<Edge *>().swap(edges); 
    delete from; 
} 

Und über diesen vector<Edge *>().swap(edges); wahrscheinlich nichts für Sie von Nutzen zu tun. Ich vermute, Sie sind nach etwas mehr wie folgt aus:

Node::~Node() 
{ 
    for (Edge * edge: edges) 
    { 
     delete edge; 
    } 
    delete from; 
} 

Und ich empfehle wirklich schwer, darüber nachzudenken, was Sie mit from tun.

Auf den zweiten Gedanken, überdenken Sie, wie Sie das tun. Das Löschen der Edge::destination ist mit ziemlicher Sicherheit eine schlechte Idee, denn wenn es sich nicht um einen eindirektionalen Baum handelt, könnte jeder gegebene Node das Ziel eines anderen Edge sein. delete alles mehr als einmal ist keine gute Idee. Die gleiche Node durch mehr als ein Objekt dargestellt ist auch eine schlechte Idee.

Answer 2

einen Vektor Clearing entbindet nicht die Speicher von den Objekten, auf die die Vektorelemente zeigen. Sie müssen den Speicher für alle Edge * im Vektor löschen, bevor Sie den Vektor selbst löschen. Tun Sie dies in jedem anderen Teil Ihres Codes, der einen Zeigervektor enthält. Fügen Sie dem ~ Node() dasselbe hinzu.

void clear() 
    { 
     cost = 0; 
     for(int i = 0; i < edges.size(); i++){ 
      edges[i]->~Edge(); 
     } 
     vector<Edge *>().swap(edges); 
     from = NULL; 
    }