对于我正在学习的一个类，我们在c++中实现了自己的单链表，这样我们就可以更好地理解数据结构的功能。目前，我已经完成了代码，它通过了所有的测试用例，但运行valgrind时，我发现我仍然存在内存泄漏。
我已经实现了每当从列表中删除每个Node对象时都应该删除它的代码，但显然我做错了什么关于我缺少的内存管理，我有什么不了解的地方
我的代码通过了一些基本测试，没有内存泄漏，但当使用教授提供的更严格的测试用例时，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)
首先，我想鼓励您在数据结构培训中，我认为这是学习编程的最佳方式，从指针和内存到分治算法和多线程应用程序。
现在，我发现您的代码没有严格遵循Stackoverflow最小可再现示例指南，因为它包含与泄漏无关的方法，如"at"、"toString"one_answers"size"，并且没有给出可用于再现valgrind输出的情况。我建议你小心遵循它们，否则你将来可能会获得否决票。在我的情况下，我将利用这一点来帮助您改进LinkedList的实现。
我看到的主要问题是LinkedList析构函数什么都不做(只释放自己使用的内存，而不是节点使用的内存(，所以如果你的程序在添加了一个元素后结束，比如：
int main() {
auto l = new LinkedList<int>();
l->insertHead(1);
// l->remove(1);
delete l;
}
与1个节点(头(对应的内存将泄漏。我建议的实施方式是：
~LinkedList() {
while (head != NULL) {
Node *nodeToDelete = head;
head = head->next;
delete nodeToDelete;
}
}
如果您在创建的每个LinkedList上调用delete，或者如果您觉得有准备，您可以使用智能指针，当它们超出范围时，可以在LinkedList中调用delete，就像您没有使用指针一样。但有了它们，如果没有析构函数，也会导致泄漏，因为析构函数不能正确释放每个LinkedList节点。我希望这能对你有所帮助，下面我给你其他建议，以防你想了解更多，并有兴趣让你的所有LinkedList方法都能像你的教授所期望的那样发挥作用。祝你好运。
另一方面，当不为空时，您的size方法似乎不计算头部。我会把它简化为：
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)