链表的链表的析构函数

Question

对于我的一个程序中的作业类我们必须制作一个邻接列表，它是一个链表的链表，看起来像这样。

A->B->C
↓
B->A->D
↓
C->D
↓
D->A->B->C

我在尝试释放在析构函数中分配的内存时遇到内存泄漏问题。一段时间以来，我一直在努力解决这个问题，但还没有 found/come 找到任何可行的解决方案。

另外请忽略头文件中包含的实现。我们被告知可以完成这项任务。

Valgrind 错误消息：

==2316== HEAP SUMMARY:
==2316== in use at exit: 48 bytes in 2 blocks
==2316== total heap usage: 3 allocs, 1 frees, 64 bytes allocated
==2316==
==2316== 48 (32 direct, 16 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 2
==2316== at 0x4C2B0E0: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2316== by 0x4012EE: main (main.cpp:34)
==2316==
==2316== LEAK SUMMARY:
==2316== definitely lost: 32 bytes in 1 blocks
==2316== indirectly lost: 16 bytes in 1 blocks
==2316== possibly lost: 0 bytes in 0 blocks
==2316== still reachable: 0 bytes in 0 blocks
==2316== suppressed: 0 bytes in 0 blocks
==2316==
==2316== For counts of detected and suppressed errors, rerun with: -v
==2316== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

这是我正在使用的一些代码（使用 gcc c++11 编译）：
linkedlist.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

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

template<typename T> class LinkedList
{
private:
    Node<T>* head;
    Node<T>* tail;
    Node<T>* curr;
    unsigned int size;

    void insertAtHead(T val)
    {
        Node<T>* temp = new Node<T>;
        temp->data = val;
        temp->next = nullptr;
        head = temp;
        tail = temp;
        curr = temp;
        size++;
    }

public:
    LinkedList()
    {
        head = nullptr;
        tail = nullptr;
        curr = nullptr;
        size = 0;
    }

    ~LinkedList()
    {
        Node<T>* nodePtr = head;
        Node<T>* temp;

        while (nodePtr != nullptr)
        {
            temp = nodePtr;
            nodePtr = nodePtr->next;
            delete temp;
        }

        size = 0;
    }

    void insertAtTail(T val)
    {
        if (head == nullptr)
            insertAtHead(val);
        else
        {
            Node<T>* temp = new Node<T>;
            temp->data = val;
            curr->next = temp;
            temp->next = nullptr;
            tail = temp;
            curr = temp;
            size++;
        }
    }
    // returns the value at the node location passed if it exists within the
    // linked list, otherwise nothing is returned
    T get(int location)
    {
        // std::cout << "size: " << size << std::endl;

        if (location >= 0 && location <= size)
        {
            Node<T>* temp = head;
            unsigned int counter = 0;

            while (counter != location)
            {
                temp = temp->next;
                counter++;
            }

            return temp->data;
        }
    }
};
#endif // LINKEDLIST_H

main.cpp

#include "linkedlist.h"

int main()
{
    LinkedList<LinkedList<int>*> matrix;
    matrix.insertAtTail(new LinkedList<int>);
    matrix.get(0)->insertAtTail(6);

    return 0;
}

Answer 1

并非所有路径 get(location) return 一个值。

使用编译器的警告来查找此类问题（例如 -Wall -Wextra -pedantic）。

此外，请确保在构造时初始化所有成员。

struct Node
{
    T data {};
    Node<T>* next = nullptr;
};

和

Node<T>* head = nullptr;
Node<T>* tail = nullptr;
Node<T>* curr = nullptr;

更新

更仔细地查看后，确实您从未删除外部列表中作为数据 T 的指针。由于您的列表不知道 T 是否是（拥有的）指针，因此它无法决定删除。

通常，我们使用智能指针包装器来解决这个问题。在您的情况下，您可能不会 "be allowed" 使用它，因此，在删除列表节点之前编写额外的循环来删除数据指针。

建议修复

这是一个重新设计的示例，它可以选择使用 NodeFree 类型模板参数，因此您可以为外部列表传入 std::default_delete<T>：

template <typename T> struct DefaultNodeFree {
    void operator()(T &) const {}
};

template<typename T, typename NodeFree = DefaultNodeFree<T> > class LinkedList
{
private:

    struct Node {
        T data {};
        Node* next = nullptr;

        ~Node() { NodeFree()(data); }
    };

所以你可以像这样使用它：

typedef LinkedList<int> inner;
LinkedList<inner*, std::default_delete<inner> > matrix;

matrix.insertAtTail(new LinkedList<int>);
matrix.get(0)->insertAtTail(6);

泄漏消失了。

现场演示

Live On Coliru

#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <cassert>
#include <memory>

template <typename T> struct DefaultNodeFree {
    void operator()(T &) const {}
};

template<typename T, typename NodeFree = DefaultNodeFree<T> > class LinkedList
{
private:

    struct Node {
        T data {};
        Node* next = nullptr;

        ~Node() { NodeFree()(data); }
    };

    Node* head = nullptr;
    Node* tail = nullptr;
    Node* curr = nullptr;
    unsigned int size;

    void insertAtHead(T val)
    {
        Node* temp = new Node;

        temp->data = val;
        temp->next = nullptr;

        head = temp;
        tail = temp;
        curr = temp;

        size++;
    }

public:
    LinkedList()
    {
        head = nullptr;
        tail = nullptr;
        curr = nullptr;
        size = 0;
    }

    ~LinkedList()
    {
        Node* nodePtr = head;

        while (nodePtr != nullptr)
        {
            Node* temp = nodePtr;
            nodePtr = nodePtr->next;
            delete temp;
            size -= 1;
        }

        assert(size == 0);
    }

    void insertAtTail(T val)
    {
        if (head == nullptr)
            insertAtHead(val);
        else
        {
            Node* temp = new Node;
            temp->data = val;
            curr->next = temp;
            temp->next = nullptr;
            tail = temp;
            curr = temp;
            size++;
        }
    }

    // returns the value at the node location passed if it exists within the
    // linked list, otherwise nothing is returned
    T get(unsigned location)
    {
        // std::cout << "size: " << size << std::endl;

        if (location >= 0 && location <= size)
        {
            Node* temp = head;
            unsigned int counter = 0;

            while (counter != location)
            {
                temp = temp->next;
                counter++;
            }

            return temp->data;
        }

        return {};
    }
};
#endif // LINKEDLIST_H

int main()
{
    typedef LinkedList<int> inner;
    LinkedList<inner*, std::default_delete<inner> > matrix;

    matrix.insertAtTail(new LinkedList<int>);
    matrix.get(0)->insertAtTail(6);
}

Answer 2

根据我的经验，当你使用模板时，你可以在同一个头文件中实现它们，但你必须将实现与声明分开。

一个常见的解决方案是在头文件中编写模板声明，并在头文件末尾包含实现。在此处阅读最高投票 Why can templates only be implemented in the header file?

我不确定这是否是您的问题，但上次我尝试按照您的方式实施模板时，我的程序根本无法运行。

链表的链表的析构函数

Destructor for LinkedList of LinkedLists

c++

c++11

memory-management

memory-leaks

destructor

建议修复

现场演示