在C ++中没有删除在堆上创建的变量

Question

我正在研究here中提供的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类的构造函数中，他们在堆中创建了一个邻接列表，但是他们从不使用删除来释放内存。我的问题如下

a）是否存在内存泄漏的可能性？

如果有任何内存泄漏我们怎么能解决这个问题？

Answer 1

是的，有泄漏。

1. 泄漏1是new list<int>[V];
2. 泄漏2是new bool[V];

看起来像Java或C＃背景的人写了这段代码。要修复泄漏，在函数delete[]中使用void Graph::BFS(int s)也使用析构函数来删除列表。

然后，你可能会考虑std::shared_ptr。

Answer 2

是否存在内存泄漏的可能性？

是的，内存泄漏的可能性很高。

如果有任何内存泄漏我们怎么能解决这个问题？

通常，这可以通过实现析构函数来解决。然后，根据rule of three，我们还需要一个复制构造函数，以防最终用户决定将一个列表复制到另一个列表。

但是我们实际上可以通过不首先动态分配来回避这个问题！让我们用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> isn't your normal vector.