c++ - Valgrind报告在运行之间发生变化的许多地方出现内存泄漏

标签 c++ memory-leaks linked-list

我正在创建一个链表，但我不断收到内存泄漏。有时它说问题出在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)

最佳答案

您的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 read或Invalid write，然后内存泄漏。



根据您的评论，您似乎对调试过程有些困惑。这个问题是关于内存泄漏的，但事实证明这是崩溃的征兆。希望这个答案可以帮助您更好地理解如何理解valgrind报告的输出，但是您应该花一些时间浏览其documentation，以便能够从中提取最大的信息量。您可以。为此，您的问题已得到解决。但是，让我稍微扩展一下此答案，以讨论有关调试的一些知识。

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

我在高中和大学期间学过很多数学，因此我对调试与解决数学问题非常相似的看法有偏见。随着时间的流逝，您对如何更快地找到解决方案有了直觉，但总的来说，我所遵循的过程很大程度上遵循了乔治·波利亚（George Polya）在其《 How to Solve It》中提出的步骤。


第一：了解问题。输入什么？输出是什么？该程序预期产生什么输出？您的程序需要哪些假设和前提条件？是否满足所有这些条件？
第二：制定计划。这个问题是新的还是与您过去遇到的问题类似？异常结果与程序的特定部分之间是否存在关系？要使程序的该部分正确运行，需要哪些假设和前提条件？您能够测试这些条件吗？
第三：执行计划。如果问题不是新问题，请尽可能应用与以前相同的修复程序来解决问题。否则，请逐步检查程序的状态，以确保满足所有假设和前提条件。确定程序行为在什么时候偏离了应该做的事情。在偏差点，了解偏差的原因，并采取适当的纠正措施。
第四：回头。程序更正后，请采取必要的步骤使自己确信此修复程序是正确的。过去通过的任何测试都应该仍然通过。不管导致失败的任何测试，现在都应该通过。确定可能暴露出代码那部分其他弱点的新测试。了解导致问题的原因，并考虑将来可以更改程序编写方式的方式，这些方式可以减少产生相同错误的可能性，也可以使问题的原因更容易识别。

关于c++ - Valgrind报告在运行之间发生变化的许多地方出现内存泄漏，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19106277/

上一篇：C++ 和数组递归

下一篇：c++ - 查找摊销时间复杂度

相关文章：

c++ - Memcached 如何确保它在内存中的页面不会被其他页面换出？

c++ - 未初始化的两个实例之一

algorithm - 链表的简单排序

c++ - 头文件/cpp 文件中定义的函数表现不同

c++ - 在 Makefile 中自动选择与 C++11 兼容的 g++ 版本

http - node.js - 可能的 http 服务器内存泄漏

c++ - 帮助修复内存泄漏

c++ - 为什么 jeprof 评估的 jemalloc 内存配置文件似乎显示所有内存分配？

java - 在链表类中实现 Iterator 接口(interface)

c# - C#中链表的大小

©2024 IT工具网  联系我们