我正在创建一个链表，但我不断得到内存泄漏。有时它说问题出在 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 s或 Invalid write s，然后解决内存泄漏。
从您的评论中，您似乎对调试过程有点困惑。这个问题是关于内存泄漏的，但事实证明这是崩溃的症状。希望这个答案能帮助你更好地理解如何理解valgrind报告的输出，但你应该花一些时间浏览它的文档，以便你能够从中提取尽可能多的信息。为此，您的问题已得到解决。但是，让我稍微扩展一下这个答案，以讨论一些有关调试的信息。
调试只是一种解决问题的练习，擅长它是一种技能。这是一个可以比作解决犯罪或谜团的过程，所以调试是程序员成为侦探的时候。与大多数人类工作一样，有些人比其他人更擅长调试。但是任何人都可以成为一个熟练的调试者，因为通过实践，你也可以成为一个更好的调试者。
我在高中和大学期间学习了很多数学，所以我偏向于认为调试与解决数学问题非常相似。随着时间的推移，你会获得一种直觉，知道如何更快地推动自己找到解决方案，但在高层次上，我采取的过程在很大程度上遵循乔治·波利亚在他的书《如何解决它》中列出的步骤。
第一：了解问题所在。输入是什么？输出是什么？程序预期会产生什么输出？您的程序需要哪些假设和前提条件？所有这些条件都满足了吗？
第二：制定计划。问题是新的还是与您过去遇到的问题相似？异常结果与程序的特定部分之间是否存在关系？程序的这一部分需要哪些假设和前提条件才能使其正常运行？你能测试这些条件吗？
第三：执行计划。如果问题不是新问题，请尽可能通过应用与之前类似的修复来解决问题。否则，请逐步检查程序的状态，以确保满足所有假设和前提条件。确定程序行为在什么时候偏离了它应该执行的操作。在偏差点，了解偏差的原因，并采取适当的纠正措施。
第四：回头看。更正程序后，采取必要的步骤来说服自己修复是正确的。无论过去通过什么测试，都应该通过。无论什么测试导致失败，现在都应该通过。确定可能暴露该部分代码中其他弱点的新测试。了解引入问题的原因，并想办法在将来更改编写程序的方式，从而降低犯相同错误的可能性，或者使问题的原因更容易识别。
在 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->data时，pos.current可能会NULL吗？