如何防止广义链表中的内存泄漏？

Question

我实现了自己的链表数据结构。数据存储在 Node 结构中。代码如下

// NODE

template <typename T>
struct Node
{
    T data;
    Node<T> *next;
    Node(T);
};

template <typename T>
Node<T>::Node(T d) : data(d), next(NULL) {}

// LIST

#include "node.cpp"

template <typename T>
class List
{
    Node<T> *head;
    int size;

public:
    List();                       // Default constructor
    List(const List &);           // Copy constructor
    void push_back(const T &);    // Insert element to the end of the list
    int get_size() const;         // Get the current size of the list
    T &operator[](int) const;     // Overload [] operator
    void operator=(const List &); // Overload = operator
    ~List();                      // Destructor
};

template <typename T>
List<T>::List() : head(NULL), size(0) {}

template <typename T>
List<T>::List(const List &list) : head(NULL), size(0)
{
    for (int i = 0; i < list.size; i++)
        push_back(list[i]);
}

template <typename T>
void List<T>::push_back(const T &data)
{
    // Create new Node with data
    Node<T> *nn = new Node<T>(data);

    // Find insert position
    if (head == NULL)
    {
        head = nn;
        size++;
        return;
    }

    Node<T> *traverse = head;
    while (traverse->next)
        traverse = traverse->next;

    // Traverse points to end of the list
    traverse->next = nn;
    size++;
}

template <typename T>
int List<T>::get_size() const
{
    return size;
}

template <typename T>
T &List<T>::operator[](int index) const
{
    int count = 0;
    Node<T> *traverse = head;
    while (traverse && count < index)
    {
        traverse = traverse->next;
        count++;
    }
    return traverse->data;
}

template <typename T>
void List<T>::operator=(const List<T> &list)
{
    Node<T> *traverse = head;

    while (head)
    {
        traverse = head;
        head = head->next;
        delete traverse;
    }

    size = 0;
    for (int i = 0; i < list.getSize(); i++)
        push_back(list[i]);
}

template <typename T>
List<T>::~List()
{
    Node<T> *traverse = head;

    while (head)
    {
        traverse = head;
        head = head->next;
        delete traverse;
    }
}

问题出在内存泄漏上。考虑以下 main 文件

#include "list.cpp"

using namespace std;

List<int *> l;

void func()
{
    int *i = new int[2];
    i[0] = 1;
    i[1] = 2;
    l.push_back(i);
}

int main()
{
    func();
    return 0;
}

根据 Valgrind，此程序存在内存泄漏。这是因为 Node 没有析构函数，所以它不能删除其中的 data 。但是，我无法向 Node 添加析构函数，因为假设我正在使用 List<int>，因此删除未动态分配的内容是错误的。简而言之，每当我为 List 使用动态分配的数据类型时，我都会发生内存泄漏。我怎样才能克服这种情况？谢谢。

Answer 1

使用std::unique_ptr作为节点的数据类型，例如：

List<std::unique_ptr<int[]>> l;

当每个节点被销毁时，其析构函数将销毁其 unique_ptr 数据，这将依次调用 delete[] 它持有的 int* 指针。

Answer 2

您示例中的泄漏与列表无关。你泄漏相同：

void func()
{
    int *i = new int[2];
    i[0] = 1;
    i[1] = 2;
}

您必须 delete 通过 new 创建的内容和 delete[] 通过 new[] 创建的内容。要修复泄漏：

void func()
{
    int *i = new int[2];
    i[0] = 1;
    i[1] = 2;
    l.push_back(i);
    delete [] i;
}

但是，请注意，在 delete[] 之后，列表中有一个悬空指针。

当您将原始指针推送到对象时，删除对象不是 List 的职责。该列表不知道它们是否拥有指针。例如：

void func()
{
    int i = 0;
    l.push_back(&i);
}

此处无需删除任何内容。（不过，这里也一样：一旦函数 returns 你在列表中有一个悬空指针）

以上都不是 "ok"。不要使用原始拥有指针！改用智能指针。如果你想要一个整数列表，那么使用 List<int> （或者更确切地说 std::list<int>）。

如何防止广义链表中的内存泄漏？

How to prevent memory leak in generalized linked list?

c++

memory

pointers

memory-leaks

linked-list