переменная, созданная в куче, не была удалена в C ++ - PullRequest
Новая
       23

переменная, созданная в куче, не была удалена в C ++

0 голосов
/ 21 апреля 2019

Я искал код поиска BFS, предоставленный в здесь : 

// Program to print BFS traversal from a given 
// source vertex. BFS(int s) traverses vertices  
// reachable from s. 
#include<iostream> 
#include <list> 

using namespace std; 

// This class represents a directed graph using 
// adjacency list representation 
class Graph 
{ 
    int V;    // No. of vertices 

    // Pointer to an array containing adjacency 
    // lists 
    list<int> *adj;    
public: 
    Graph(int V);  // Constructor 

    // function to add an edge to graph 
    void addEdge(int v, int w);  

    // prints BFS traversal from a given source s 
    void BFS(int s);   
}; 

Graph::Graph(int V) 
{ 
    this->V = V; 
    adj = new list<int>[V]; 
} 

void Graph::addEdge(int v, int w) 
{ 
    adj[v].push_back(w); // Add w to v’s list. 
} 

void Graph::BFS(int s) 
{ 
    // Mark all the vertices as not visited 
    bool *visited = new bool[V]; 
    for(int i = 0; i < V; i++) 
        visited[i] = false; 

    // Create a queue for BFS 
    list<int> queue; 

    // Mark the current node as visited and enqueue it 
    visited[s] = true; 
    queue.push_back(s); 

    // 'i' will be used to get all adjacent 
    // vertices of a vertex 
    list<int>::iterator i; 

    while(!queue.empty()) 
    { 
        // Dequeue a vertex from queue and print it 
        s = queue.front(); 
        cout << s << " "; 
        queue.pop_front(); 

        // Get all adjacent vertices of the dequeued 
        // vertex s. If a adjacent has not been visited,  
        // then mark it visited and enqueue it 
        for (i = adj[s].begin(); i != adj[s].end(); ++i) 
        { 
            if (!visited[*i]) 
            { 
                visited[*i] = true; 
                queue.push_back(*i); 
            } 
        } 
    } 
} 

// Driver program to test methods of graph class 
int main() 
{ 
    // Create a graph given in the above diagram 
    Graph g(4); 
    g.addEdge(0, 1); 
    g.addEdge(0, 2); 
    g.addEdge(1, 2); 
    g.addEdge(2, 0); 
    g.addEdge(2, 3); 
    g.addEdge(3, 3); 

    cout << "Following is Breadth First Traversal "
         << "(starting from vertex 2) \n"; 
    g.BFS(2); 

    return 0; 
}

В конструкторе класса Graph они создали список смежности в куче, но никогда не использовали удаление дляосвободить память.У меня такой вопрос:

а) Есть ли вероятность утечки памяти?

Если есть утечка памяти, как мы можем решить эту проблему?

Ответы [ 2 ]

1 голос
/ 21 апреля 2019

Есть ли вероятность утечки памяти?

Да, существует большая вероятность утечки памяти.

Если есть утечка памяти, как мы можем решить эту проблему?

Как правило, это можно решить путем реализации деструктора. Опять же, согласно правилу из трех , нам также потребуется конструктор копирования , на тот случай, если конечный пользователь решит скопировать один список в другой.

Но на самом деле мы могли бы обойти это, если бы не выделялся динамически во-первых! Давайте переопределим с помощью std::vector: 

class Graph 
{ 
    int V;

    vector<list<int>> adj;    
public: 
    Graph(int V);

    // ...
}; 

Graph::Graph(int V)
{ 
    this->V = V;
    adj.assign(V, list<int>());     // std::vector::assign
} 

void Graph::BFS(int s) 
{ 
    // Mark all the vertices as not visited 
    vector<bool> visited(V);                       //  see note below  *
    for(int i = 0; i < V; i++) 
        visited[i] = false; 

    // Create a queue for BFS 
    list<int> queue;

    // Mark the current node as visited and enqueue it 
    visited[s] = true; 
    queue.push_back(s); 

    // 'i' will be used to get all adjacent 
    // vertices of a vertex 
    list<int>::iterator i; 

    while(!queue.empty()) 
    { 
        // Dequeue a vertex from queue and print it 
        s = queue.front(); 
        cout << s << " "; 
        queue.pop_front(); 

        // Get all adjacent vertices of the dequeued 
        // vertex s. If a adjacent has not been visited,  
        // then mark it visited and enqueue it 
        for (i = adj[s].begin(); i != adj[s].end(); ++i) 
        { 
            if (!visited[*i]) 
            { 
                visited[*i] = true; 
                queue.push_back(*i); 
            } 
        } 
    } 
}

Существует множество других мелких проблем с этим кодом, но я оставлю это в качестве упражнения для читателя.

* Примечание: vector<bool> не ваш нормальный вектор.

1 голос
/ 21 апреля 2019

Да, есть утечки.

  1. Утечка 1 - new list<int>[V];
  2. Утечка 2 - new bool[V];

Похоже, какой-то парень с фоном Java или C # написал этот кусок кода. Чтобы исправить утечки, используйте delete[] в функции void Graph::BFS(int s), также используйте деструктор для удаления списка.

Тогда вы можете рассмотреть std::shared_ptr.

...