c++ - 我对内存泄漏有什么不了解？

Question

对于我正在上的一门课，我们正在用 C++ 实现我们自己的单向链表，以便我们可以更好地理解数据结构的功能。目前，我已经完成了代码，它通过了所有测试用例，但是运行 valgrind 我发现我仍然有内存泄漏。

我已经实现了应该删除每个节点对象的代码，只要它从列表中删除，但显然我做错了什么。 关于我缺少的内存管理，我不了解什么？

我的代码通过了一些基本测试，没有内存泄漏，但是当使用我的教授提供的更严格的测试用例时，valgrind 出现了严重的内存泄漏问题。

这是我的链表类:

template<typename T>
class LinkedList: public LinkedListInterface<T> {

    private:

        struct Node {
            Node(T val) {
                value = val;
                next = NULL;
            }
            T value;
            Node *next;
        };

        Node *head;

    public:

    LinkedList() {
        head = NULL;

    }

    ~LinkedList() {

    }

    void insertHead(T value) {
        cout << "In insertHead function" << endl;
        Node *newNode = new Node(value);
        if(head == NULL){
            head = newNode;
        }
        else {
            newNode->next = head;
            head = newNode;
        }
    }

    //don't allow duplicate values in the list. Implement later.
    void insertTail(T value) {
        cout << "In insertTail function" << endl;
        Node *newNode = new Node(value);

        if(head == NULL) {
            head = newNode;
        }
        else {
            //find last node
            Node *fakeIterator = head;
            //while what fake iterator is pointing to is not NULL then make it point to the next pointer.
            while (fakeIterator->next != NULL) {
                fakeIterator = fakeIterator->next;
            }
            //set that node's next pointer to newNode
            fakeIterator->next = newNode;
        }
    }

    void insertAfter(T value, T insertionNode) {
        cout << "In insertAfter function" << endl;
        Node *fakeIterator = head;

        while(fakeIterator != NULL) {
            if (fakeIterator->value == insertionNode) {
                Node *newNode = new Node(value);
                newNode->next = fakeIterator->next;
                fakeIterator->next = newNode;
                break;
            }
            fakeIterator = fakeIterator->next;
        }
    }

    string toString() {
        cout << "In toString function" << endl;
        stringstream ss;
        Node *fakeIterator = head;
        while (fakeIterator != NULL) {
            if (fakeIterator->next == NULL)
                ss << fakeIterator->value;
            else
                ss << fakeIterator->value << ", ";

            fakeIterator = fakeIterator->next;
        }

        return ss.str();
    }

    void remove(T value) {
        cout << "In remove function" << endl;
        if (head != NULL) {
            Node *fakeIterator = head;
            if(head->value == value) {
                Node *nodeToDelete = head;//new Node(value);
                // nodeToDelete = head;
                head = head->next;
                delete nodeToDelete;
            }
            else {
                while(fakeIterator->next != NULL) {
                    //if the value of the node after this one equals the value
                    if ( (fakeIterator->next)->value == value) {
                        //make a temp node to store the node being destroyed
                        Node *nodeToDelete = fakeIterator->next;
                        //change "next" to point to the item after the one being deleted
                        fakeIterator->next = fakeIterator->next->next;
                        //delete the node
                        delete nodeToDelete;
                        break;
                    }
                    fakeIterator = fakeIterator->next;
                }
            }
        }
    }

    void clear() {
        cout << "In clear function" << endl;
        while (head != NULL) {
            remove(head->value);
        }
    }

    T at(int index) {
        cout << "In at function" << endl;
        Node *fakeIterator = head;
        if (head == NULL) {
            throw out_of_range("list is empty");
        }
        for (int i = 0; i < index ; i++) {
            cout << "2" << endl;
            if (fakeIterator->next == NULL) {
                cout << "3" << endl;
                throw out_of_range("index does not exist");
                break;
            }
            fakeIterator = fakeIterator->next;
            cout << "4" << endl;
        }

        return fakeIterator->value;
    }

    int size() {
        cout << "In size function" << endl;
        int sizeOfList = 0;
        Node *fakeIterator = head;
        while (fakeIterator != NULL) {
            if (fakeIterator->next == NULL)
                return sizeOfList;
            else
                sizeOfList++;

            fakeIterator = fakeIterator->next;
        }
    }

};

这是 valgrind 的输出:

==14052== Process terminating with default action of signal 2 (SIGINT)
==14052==    at 0x57BFFE0: __read_nocancel (in /lib64/libc-2.17.so)
==14052==    by 0x574CB83: _IO_file_underflow@@GLIBC_2.2.5 (in /lib64/libc-2.17.so)
==14052==    by 0x574DD51: _IO_default_uflow (in /lib64/libc-2.17.so)
==14052==    by 0x5748729: getchar (in /lib64/libc-2.17.so)
==14052==    by 0x4024C1: main (main.cpp:88)
==14052== 
==14052== HEAP SUMMARY:
==14052==     in use at exit: 16,468 bytes in 696 blocks
==14052==   total heap usage: 2,924 allocs, 2,228 frees, 523,457 bytes allocated
==14052== 
==14052== 96 (16 direct, 80 indirect) bytes in 1 blocks are definitely lost in loss record 10 of 18
==14052==    at 0x4C29203: operator new(unsigned long) (vg_replace_malloc.c:334)
==14052==    by 0x40442F: LinkedList<int>::insertHead(int) (LinkedList.h:58)
==14052==    by 0x4034A0: void parse_instruction<int>(std::string, std::basic_ofstream<char, std::char_traits<char> >&, LinkedList<int>*) (main.cpp:101)
==14052==    by 0x4023AC: main (main.cpp:67)
==14052== 
==14052== 585 (16 direct, 569 indirect) bytes in 1 blocks are definitely lost in loss record 15 of 18
==14052==    at 0x4C29203: operator new(unsigned long) (vg_replace_malloc.c:334)
==14052==    by 0x403BEB: LinkedList<std::string>::insertHead(std::string) (LinkedList.h:58)
==14052==    by 0x402C84: void parse_instruction<std::string>(std::string, std::basic_ofstream<char, std::char_traits<char> >&, LinkedList<std::string>*) (main.cpp:101)
==14052==    by 0x402371: main (main.cpp:64)
==14052== 
==14052== 15,528 (16 direct, 15,512 indirect) bytes in 1 blocks are definitely lost in loss record 18 of 18
==14052==    at 0x4C29203: operator new(unsigned long) (vg_replace_malloc.c:334)
==14052==    by 0x403DE3: LinkedList<std::string>::insertAfter(std::string, std::string) (LinkedList.h:94)
==14052==    by 0x402DF6: void parse_instruction<std::string>(std::string, std::basic_ofstream<char, std::char_traits<char> >&, LinkedList<std::string>*) (main.cpp:111)
==14052==    by 0x402371: main (main.cpp:64)
==14052== 
==14052== LEAK SUMMARY:
==14052==    definitely lost: 48 bytes in 3 blocks
==14052==    indirectly lost: 16,161 bytes in 687 blocks
==14052==      possibly lost: 0 bytes in 0 blocks
==14052==    still reachable: 259 bytes in 6 blocks
==14052==                       of which reachable via heuristic:
==14052==                         stdstring          : 259 bytes in 6 blocks
==14052==         suppressed: 0 bytes in 0 blocks
==14052== Reachable blocks (those to which a pointer was found) are not shown.
==14052== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==14052== 
==14052== For counts of detected and suppressed errors, rerun with: -v
==14052== ERROR SUMMARY: 3 errors from 3 contexts (suppressed: 0 from 0)

Answer 1

首先，我想鼓励您在数据结构方面进行培训，我认为这是学习编程的最佳方式，从指针和内存到分而治之算法和多线程应用程序。

现在，我发现您的代码没有严格遵循 Stackoverflow Minimum Reproducible Example guidelines ，因为它包含与泄漏无关的方法，如“at”、“toString”和“size”，并且没有提供可用于重现 valgrind 输出的案例。我建议您仔细关注他们，否则您将来可能会获得反对票。就我而言，我将利用它来尝试帮助您更多地改进您的 LinkedList 实现。

我看到的主要问题是 LinkedList 的析构函数什么都不做(只释放它自己使用的内存，而不是它的节点)，所以如果你的程序在添加一个元素后结束，说:

int main() {    
  auto l = new LinkedList<int>();
  l->insertHead(1);
  // l->remove(1);
  delete l;
}

1个节点(head)对应的内存会被泄露。我推荐的实现是:

~LinkedList() {
  while (head != NULL) {
    Node *nodeToDelete = head;
    head = head->next;
    delete nodeToDelete;
  }
}

如果您在您创建的每个 LinkedList 上调用 delete，或者如果您觉得准备好了，您可以使用智能指针在 LinkedLists 超出范围时调用 delete，就好像您没有使用指针。但是对于它们，如果没有析构函数，您也会遇到泄漏，析构函数不能正确释放每个 LinkedList 节点。我希望这对你有帮助，如果你想了解更多并且有兴趣让你所有的 LinkedList 方法像你的教授期望的那样工作，下面我会给你其他建议。祝你好运。

---

另一方面，当您的 size 方法不为 null 时，它似乎不计算头部。我将其简化为:

int size() {
  cout << "In size function" << endl;
  int sizeOfList = 0;
  Node *fakeIterator = head;
  while (fakeIterator != NULL) {
    ++sizeOfList;
    fakeIterator = fakeIterator->next;
  }
  return sizeOfList;
}

---

智能指针奖励:

#include <memory>

int main() {    
  auto l = make_unique<LinkedList<int>>();
  l->insertHead(1);
}

Valgrind 输出:

==3288== Memcheck, a memory error detector
==3288== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==3288== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==3288== Command: ./run
==3288== 
In insertHead function
==3288== 
==3288== HEAP SUMMARY:
==3288==     in use at exit: 0 bytes in 0 blocks
==3288==   total heap usage: 4 allocs, 4 frees, 73,760 bytes allocated
==3288== 
==3288== All heap blocks were freed -- no leaks are possible
==3288== 
==3288== For counts of detected and suppressed errors, rerun with: -v
==3288== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)