0

我正在创建一个链接列表，但我不断收到内存泄漏。有时它说问题出在 at() 函数中，有时在 remove() 函数中，但对我来说这一切看起来都很紧凑。是什么导致内存泄漏？

这是我的链表代码：

void LinkedList::insertHead(int value)
{
    if (value < 0) {
        return;
    }
    iterator pos(this, head);
    for (int i = 0; i < num_items; i++) {
        if (pos.current->data == value)
            return;
        else
            pos++;
    }
    head = new Node(value, NULL, head);
    if (head->next != NULL)
        head->next->prev = head;
    if (tail == NULL)
        tail = head;
    num_items++;
}

void LinkedList::insertTail(int value)
{
    if (value < 0) {
        return;
    }
    iterator pos(this, head);
    for (int i = 0; i < num_items; i++) {
        if (pos.current->data == value)
            return;
        else
            pos++;
    }
    if (tail != NULL) {
        tail->next = new Node(value, tail, NULL);
        tail = tail->next;
        num_items++;
    } else
        insertHead(value);
}

void LinkedList::insertAfter(int value, int insertionNode)
{
    if (value < 0) {
        return;
    }
    iterator pos(this, head);
    for (int i = 0; i < num_items; i++) {
        if (pos.current->data == value)
            return;
        else
            pos++;
    }
    pos = iterator(this, head);
    for (int i = 0; i < num_items; i++) {
        if (pos.current->data == insertionNode)
            break;
        else
            pos++;
    }
    if (pos.current == NULL || pos.current->data != insertionNode) {
        return;
    } /*else if(pos.current==NULL)
        insertTail(value);*/
    else {
        Node *new_node = new Node(value, pos.current, pos.current->next);
        if (pos.current->next != NULL)
            pos.current->next->prev = new_node;
        pos.current->next = new_node;
        num_items++;
    }

}

void LinkedList::remove(int value)
{
    if (value < 0) {
        return;
    }
    iterator pos(this, head);
    for (int i = 0; i < num_items; i++) {
        if (pos.current->data == value)
            break;
        else
            pos++;
    }
    if (pos.current->data != value) {
        return;
    }
    if (pos.current == head) {
        Node *removed_node = head;
        head = head->next;
        delete removed_node;
        if (head != NULL)
            head->prev = NULL;
        else
            tail = NULL;
        num_items--;
    } else if (pos.current == tail) {
        Node *removed_node = tail;
        tail = tail->prev;
        delete removed_node;
        if (tail != NULL)
            tail->next = NULL;
        else
            head = NULL;
        num_items--;
    } else {
        Node *removed_node = pos.current;
        removed_node->prev->next = removed_node->next;
        removed_node->next->prev = removed_node->prev;
        delete removed_node;
        num_items--;
    }
}

void LinkedList::clear()
{
    if (num_items == 0)
        return;
    if (head != NULL)
        remove(head->data);
    num_items = 0;
}

int LinkedList::at(int index)
{
    if (index < 0 || index >= num_items)
        return -1;
    iterator pos(this, head);
    for (int i = 0; i < index; i++)
        pos++;
    return pos.current->data;
}

int LinkedList::size()
{
    return num_items;
}

这是迭代器的代码：

class iterator {
    friend class LinkedList;
private:
    LinkedList * parent;
    Node *current;
    iterator(LinkedList * my_parent, Node * position):parent(my_parent),
        current(position) {
    }
public:
    int &operator*() const {
        if (current == NULL)
            throw "Attempt to dereference end()";
        return current->data;
    }

    int *operator->() const {
        if (current == NULL)
            throw "attempt to dereference end()";
        return &(current->data);
    }

    iterator & operator++() {
        if (current == NULL)
            throw "Attempt to advance past end()";
        current = current->next;
        return *this;
    }

    iterator & operator--() {
        if (current == parent->head)
            throw "Attempt to move before begin()";
        if (current == NULL)
            current = parent->tail;
        else
            current = current->prev;
        return *this;
    }

    iterator operator++(int) {
        iterator return_value = *this;
        ++(*this);
        return return_value;
    }

    iterator operator--(int) {
        iterator return_value = *this;
        --(*this);
        return return_value;
    }

    bool operator==(const iterator & other) {
        return current == other.current;
    }

    bool operator!=(const iterator & other) {
        return !operator==(other);
    }
};

按要求输出：

==18072== Invalid read of size 4
==18072==    at 0x402556: LinkedList::remove(int) (LinkedList.cpp:115)
==18072==    by 0x405946: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==18072== 
segmentation fault
This segmentation fault was most likely caused by insertHead(), insertTail(), insertAfter(), or remove()
==18072== 
==18072== HEAP SUMMARY:
==18072==     in use at exit: 4,074 bytes in 118 blocks
==18072==   total heap usage: 981 allocs, 863 frees, 158,945 bytes allocated
==18072== 
==18072== 16 bytes in 1 blocks are still reachable in loss record 1 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x405888: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 32 bytes in 1 blocks are still reachable in loss record 2 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x4020B2: Factory::getLinkedList() (Factory.cpp:21)
==18072==    by 0x40587B: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 32 bytes in 2 blocks are still reachable in loss record 3 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x407AC5: TADuck::insertHead(int) (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x405D91: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 48 bytes in 2 blocks are still reachable in loss record 4 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
==18072==    by 0x405D84: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 48 bytes in 2 blocks are indirectly lost in loss record 5 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x40247A: LinkedList::insertAfter(int, int) (LinkedList.cpp:88)
==18072==    by 0x405137: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 192 bytes in 8 blocks are indirectly lost in loss record 6 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x402308: LinkedList::insertTail(int) (LinkedList.cpp:47)
==18072==    by 0x404D9F: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 216 bytes in 9 blocks are indirectly lost in loss record 7 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
==18072==    by 0x404341: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 216 bytes in 9 blocks are indirectly lost in loss record 8 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
==18072==    by 0x404BAD: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 240 bytes in 10 blocks are indirectly lost in loss record 9 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x402308: LinkedList::insertTail(int) (LinkedList.cpp:47)
==18072==    by 0x4046B1: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 240 bytes in 10 blocks are indirectly lost in loss record 10 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x40247A: LinkedList::insertAfter(int, int) (LinkedList.cpp:88)
==18072==    by 0x404897: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 256 bytes in 1 blocks are still reachable in loss record 11 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x4074AD: std::vector<int, std::allocator<int> >::_M_insert_aux(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, int const&) (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x402B7C: fillMasterList(std::vector<int, std::allocator<int> >&, int) (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x404B82: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 432 bytes in 18 blocks are indirectly lost in loss record 12 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
==18072==    by 0x402BFD: initList(LinkedListInterface*, LinkedListInterface*) (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x403F78: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 456 bytes in 19 blocks are indirectly lost in loss record 13 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
==18072==    by 0x4039E9: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 480 bytes in 20 blocks are indirectly lost in loss record 14 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
==18072==    by 0x402BFD: initList(LinkedListInterface*, LinkedListInterface*) (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x4040DF: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 480 (24 direct, 456 indirect) bytes in 1 blocks are definitely lost in loss record 15 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
==18072==    by 0x4039E9: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 480 (24 direct, 456 indirect) bytes in 1 blocks are definitely lost in loss record 16 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
==18072==    by 0x402374: LinkedList::insertTail(int) (LinkedList.cpp:52)
==18072==    by 0x404D9F: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 537 bytes in 1 blocks are possibly lost in loss record 17 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x38C88B9F48: std::string::_Rep::_S_create(unsigned long, unsigned long, std::allocator<char> const&) (in /usr/lib64/libstdc++.so.6.0.18)
==18072==    by 0x38C88BAB1A: std::string::_Rep::_M_clone(std::allocator<char> const&, unsigned long) (in /usr/lib64/libstdc++.so.6.0.18)
==18072==    by 0x38C88BABB3: std::string::reserve(unsigned long) (in /usr/lib64/libstdc++.so.6.0.18)
==18072==    by 0x38C8898F75: std::basic_stringbuf<char, std::char_traits<char>, std::allocator<char> >::overflow(int) (in /usr/lib64/libstdc++.so.6.0.18)
==18072==    by 0x38C889D195: std::basic_streambuf<char, std::char_traits<char> >::xsputn(char const*, long) (in /usr/lib64/libstdc++.so.6.0.18)
==18072==    by 0x38C88949A4: std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long) (in /usr/lib64/libstdc++.so.6.0.18)
==18072==    by 0x4036B6: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 537 bytes in 1 blocks are possibly lost in loss record 18 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x38C88B9F48: std::string::_Rep::_S_create(unsigned long, unsigned long, std::allocator<char> const&) (in /usr/lib64/libstdc++.so.6.0.18)
==18072==    by 0x38C88BAB1A: std::string::_Rep::_M_clone(std::allocator<char> const&, unsigned long) (in /usr/lib64/libstdc++.so.6.0.18)
==18072==    by 0x38C88BABB3: std::string::reserve(unsigned long) (in /usr/lib64/libstdc++.so.6.0.18)
==18072==    by 0x38C8898F75: std::basic_stringbuf<char, std::char_traits<char>, std::allocator<char> >::overflow(int) (in /usr/lib64/libstdc++.so.6.0.18)
==18072==    by 0x38C889D195: std::basic_streambuf<char, std::char_traits<char> >::xsputn(char const*, long) (in /usr/lib64/libstdc++.so.6.0.18)
==18072==    by 0x38C88949A4: std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long) (in /usr/lib64/libstdc++.so.6.0.18)
==18072==    by 0x403A7C: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 720 (24 direct, 696 indirect) bytes in 1 blocks are definitely lost in loss record 19 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
==18072==    by 0x404341: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== 936 (24 direct, 912 indirect) bytes in 1 blocks are definitely lost in loss record 20 of 20
==18072==    at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==18072==    by 0x4021F1: LinkedList::insertHead(int) (LinkedList.cpp:20)
==18072==    by 0x402BFD: initList(LinkedListInterface*, LinkedListInterface*) (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x403F78: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072== 
==18072== LEAK SUMMARY:
==18072==    definitely lost: 96 bytes in 4 blocks
==18072==    indirectly lost: 2,520 bytes in 105 blocks
==18072==      possibly lost: 1,074 bytes in 2 blocks
==18072==    still reachable: 384 bytes in 7 blocks
==18072==         suppressed: 0 bytes in 0 blocks
==18072== 
==18072== For counts of detected and suppressed errors, rerun with: -v
==18072== ERROR SUMMARY: 7 errors from 7 contexts (suppressed: 2 from 2)
4

2 回答 2

1

您的valgrind输出报告内存泄漏。但是，现在可以忽略这些，因为您的程序由于对内存位置的无效读取而遭受了分段错误0x0：

==18072== Invalid read of size 4
==18072==    at 0x402556: LinkedList::remove(int) (LinkedList.cpp:115)
==18072==    by 0x405946: testAll() (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==    by 0x401E81: main (in /users/guest/s/scalen/Desktop/To Students/dont_run_me)
==18072==  Address 0x0 is not stack'd, malloc'd or (recently) free'd

segmentation fault

您需要找到行在哪里115，并弄清楚为什么代码试图推迟无效的内存位置。作为一个例子，我将用我找到的第一个来说明（我不知道这是否valgrind是抱怨的那个，因为我不知道你的代码的行号是什么）：

    for (int i = 0; i < num_items; i++) {
        if (pos.current->data == value)
            break;
        else
            pos++;
    }
    if (pos.current->data != value) {
        return;
    }

在没有匹配的情况下，value似乎不太可能pos.current指向有意义的条目。因此，取消引用它以检查它是否与早期不匹配return可能是错误的做法。相反，检查for循环是否真的通过了整个列表：

    int i;
    for (i = 0; i < num_items; i++) {
        //...
    }
    if (i == num_items) {
        return;
    }

遇到 中报的错误valgrind，先解决segmentation故障，然后是Invalid reads 或Invalid writes，然后是内存泄漏。

从您的评论来看，您似乎对调试过程有些困惑。这个问题是关于内存泄漏的，但事实证明这是崩溃的症状。希望这个答案可以帮助您更好地理解如何理解valgrind报告的输出，但是您应该花一些时间阅读它的文档，以便能够从中提取尽可能多的信息。为此，您的问题已得到解决。但是，让我稍微扩展一下这个答案，讨论一下关于调试的问题。

调试只是一种解决问题的练习，擅长它是一种技能。这是一个可以比作解决犯罪或谜团的过程，因此调试是程序员成为侦探的时候。与大多数人类努力一样，有些人在调试方面比其他人要好得多。但是任何人都可以成为熟练的调试器，因为通过练习你可以成为更好的调试器也是事实。

我在高中和大学期间学习了很多数学，所以我偏向于认为调试与解决数学问题非常相似。随着时间的推移，你会获得关于如何更快地推动自己解决问题的直觉，但在高层次上，我所采取的过程在很大程度上遵循 George Polya 在他的《如何解决它》一书中提出的步骤。

  1. 第一：了解问题。输入是什么？输出是什么？程序预期会产生什么输出？您的程序需要哪些假设和前提条件？这些条件都满足了吗？

  2. 第二：制定计划。问题是新问题还是与您过去遇到的问题相似？异常结果与程序的特定部分之间是否存在关系？程序的该部分需要哪些假设和先决条件才能正确运行？你能测试这些条件吗？

  3. 第三：执行计划。如果问题不是新问题，请尽可能应用类似于您之前所做的修复来解决问题。否则，请逐步检查程序的状态，以确保满足所有假设和前提条件。确定程序行为在什么时候偏离了它应该做的事情。在偏差点，了解偏差的原因，并采取适当的纠正措施。

  4. 第四：回头看。修正程序后，采取必要的步骤让自己相信修正是正确的。过去通过的任何测试都应该仍然通过。任何导致失败的测试现在都应该通过。识别可能暴露该部分代码中其他弱点的新测试。理解为什么会出现这个问题，并想出一些方法可以改变你将来编写程序的方式，从而降低发生相同错误的可能性，或者使问题的原因更容易识别。

于 2013-10-01T01:56:54.530 回答
1

在此代码段中remove，

iterator pos(this, head);
for (int i = 0; i < num_items; i++) {
    if (pos.current->data == value)
        break;
    else
        pos++;
}
if (pos.current->data != value) {
    return;
}

您将 pos 推进到列表的最后（如果value没有找到，至少），那么当您之后尝试访问时可能pos.current是这样吗？NULLpos.current->data

于 2013-10-01T02:00:37.720 回答