链表的链表的析构函数
Destructor for LinkedList of LinkedLists
对于我的一个程序中的作业 类 我们必须制作一个邻接列表,它是一个链表的链表,看起来像这样。
A->B->C
↓
B->A->D
↓
C->D
↓
D->A->B->C
我在尝试释放在析构函数中分配的内存时遇到内存泄漏问题。一段时间以来,我一直在努力解决这个问题,但还没有 found/come 找到任何可行的解决方案。
另外请忽略头文件中包含的实现。我们被告知可以完成这项任务。
Valgrind 错误消息:
==2316== HEAP SUMMARY:
==2316== in use at exit: 48 bytes in 2 blocks
==2316== total heap usage: 3 allocs, 1 frees, 64 bytes allocated
==2316==
==2316== 48 (32 direct, 16 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 2
==2316== at 0x4C2B0E0: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2316== by 0x4012EE: main (main.cpp:34)
==2316==
==2316== LEAK SUMMARY:
==2316== definitely lost: 32 bytes in 1 blocks
==2316== indirectly lost: 16 bytes in 1 blocks
==2316== possibly lost: 0 bytes in 0 blocks
==2316== still reachable: 0 bytes in 0 blocks
==2316== suppressed: 0 bytes in 0 blocks
==2316==
==2316== For counts of detected and suppressed errors, rerun with: -v
==2316== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
这是我正在使用的一些代码(使用 gcc c++11 编译):
linkedlist.h
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
template<typename T> struct Node
{
T data;
Node<T>* next;
};
template<typename T> class LinkedList
{
private:
Node<T>* head;
Node<T>* tail;
Node<T>* curr;
unsigned int size;
void insertAtHead(T val)
{
Node<T>* temp = new Node<T>;
temp->data = val;
temp->next = nullptr;
head = temp;
tail = temp;
curr = temp;
size++;
}
public:
LinkedList()
{
head = nullptr;
tail = nullptr;
curr = nullptr;
size = 0;
}
~LinkedList()
{
Node<T>* nodePtr = head;
Node<T>* temp;
while (nodePtr != nullptr)
{
temp = nodePtr;
nodePtr = nodePtr->next;
delete temp;
}
size = 0;
}
void insertAtTail(T val)
{
if (head == nullptr)
insertAtHead(val);
else
{
Node<T>* temp = new Node<T>;
temp->data = val;
curr->next = temp;
temp->next = nullptr;
tail = temp;
curr = temp;
size++;
}
}
// returns the value at the node location passed if it exists within the
// linked list, otherwise nothing is returned
T get(int location)
{
// std::cout << "size: " << size << std::endl;
if (location >= 0 && location <= size)
{
Node<T>* temp = head;
unsigned int counter = 0;
while (counter != location)
{
temp = temp->next;
counter++;
}
return temp->data;
}
}
};
#endif // LINKEDLIST_H
main.cpp
#include "linkedlist.h"
int main()
{
LinkedList<LinkedList<int>*> matrix;
matrix.insertAtTail(new LinkedList<int>);
matrix.get(0)->insertAtTail(6);
return 0;
}
并非所有路径 get(location)
return 一个值。
使用编译器的警告来查找此类问题(例如 -Wall -Wextra -pedantic
)。
此外,请确保在构造时初始化所有成员。
struct Node
{
T data {};
Node<T>* next = nullptr;
};
和
Node<T>* head = nullptr;
Node<T>* tail = nullptr;
Node<T>* curr = nullptr;
更新
更仔细地查看后,确实您从未删除外部列表中作为数据 T
的指针。由于您的列表不知道 T
是否是(拥有的)指针,因此它无法决定删除。
通常,我们使用智能指针包装器来解决这个问题。在您的情况下,您可能不会 "be allowed" 使用它,因此,在删除列表节点之前编写额外的循环来删除数据指针。
建议修复
这是一个重新设计的示例,它可以选择使用 NodeFree
类型模板参数,因此您可以为外部列表传入 std::default_delete<T>
:
template <typename T> struct DefaultNodeFree {
void operator()(T &) const {}
};
template<typename T, typename NodeFree = DefaultNodeFree<T> > class LinkedList
{
private:
struct Node {
T data {};
Node* next = nullptr;
~Node() { NodeFree()(data); }
};
所以你可以像这样使用它:
typedef LinkedList<int> inner;
LinkedList<inner*, std::default_delete<inner> > matrix;
matrix.insertAtTail(new LinkedList<int>);
matrix.get(0)->insertAtTail(6);
泄漏消失了。
现场演示
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <cassert>
#include <memory>
template <typename T> struct DefaultNodeFree {
void operator()(T &) const {}
};
template<typename T, typename NodeFree = DefaultNodeFree<T> > class LinkedList
{
private:
struct Node {
T data {};
Node* next = nullptr;
~Node() { NodeFree()(data); }
};
Node* head = nullptr;
Node* tail = nullptr;
Node* curr = nullptr;
unsigned int size;
void insertAtHead(T val)
{
Node* temp = new Node;
temp->data = val;
temp->next = nullptr;
head = temp;
tail = temp;
curr = temp;
size++;
}
public:
LinkedList()
{
head = nullptr;
tail = nullptr;
curr = nullptr;
size = 0;
}
~LinkedList()
{
Node* nodePtr = head;
while (nodePtr != nullptr)
{
Node* temp = nodePtr;
nodePtr = nodePtr->next;
delete temp;
size -= 1;
}
assert(size == 0);
}
void insertAtTail(T val)
{
if (head == nullptr)
insertAtHead(val);
else
{
Node* temp = new Node;
temp->data = val;
curr->next = temp;
temp->next = nullptr;
tail = temp;
curr = temp;
size++;
}
}
// returns the value at the node location passed if it exists within the
// linked list, otherwise nothing is returned
T get(unsigned location)
{
// std::cout << "size: " << size << std::endl;
if (location >= 0 && location <= size)
{
Node* temp = head;
unsigned int counter = 0;
while (counter != location)
{
temp = temp->next;
counter++;
}
return temp->data;
}
return {};
}
};
#endif // LINKEDLIST_H
int main()
{
typedef LinkedList<int> inner;
LinkedList<inner*, std::default_delete<inner> > matrix;
matrix.insertAtTail(new LinkedList<int>);
matrix.get(0)->insertAtTail(6);
}
根据我的经验,当你使用模板时,你可以在同一个头文件中实现它们,但你必须将实现与声明分开。
一个常见的解决方案是在头文件中编写模板声明,并在头文件末尾包含实现。
在此处阅读最高投票 Why can templates only be implemented in the header file?
我不确定这是否是您的问题,但上次我尝试按照您的方式实施模板时,我的程序根本无法运行。
对于我的一个程序中的作业 类 我们必须制作一个邻接列表,它是一个链表的链表,看起来像这样。
A->B->C
↓
B->A->D
↓
C->D
↓
D->A->B->C
我在尝试释放在析构函数中分配的内存时遇到内存泄漏问题。一段时间以来,我一直在努力解决这个问题,但还没有 found/come 找到任何可行的解决方案。
另外请忽略头文件中包含的实现。我们被告知可以完成这项任务。
Valgrind 错误消息:
==2316== HEAP SUMMARY:
==2316== in use at exit: 48 bytes in 2 blocks
==2316== total heap usage: 3 allocs, 1 frees, 64 bytes allocated
==2316==
==2316== 48 (32 direct, 16 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 2
==2316== at 0x4C2B0E0: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2316== by 0x4012EE: main (main.cpp:34)
==2316==
==2316== LEAK SUMMARY:
==2316== definitely lost: 32 bytes in 1 blocks
==2316== indirectly lost: 16 bytes in 1 blocks
==2316== possibly lost: 0 bytes in 0 blocks
==2316== still reachable: 0 bytes in 0 blocks
==2316== suppressed: 0 bytes in 0 blocks
==2316==
==2316== For counts of detected and suppressed errors, rerun with: -v
==2316== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
这是我正在使用的一些代码(使用 gcc c++11 编译):
linkedlist.h
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
template<typename T> struct Node
{
T data;
Node<T>* next;
};
template<typename T> class LinkedList
{
private:
Node<T>* head;
Node<T>* tail;
Node<T>* curr;
unsigned int size;
void insertAtHead(T val)
{
Node<T>* temp = new Node<T>;
temp->data = val;
temp->next = nullptr;
head = temp;
tail = temp;
curr = temp;
size++;
}
public:
LinkedList()
{
head = nullptr;
tail = nullptr;
curr = nullptr;
size = 0;
}
~LinkedList()
{
Node<T>* nodePtr = head;
Node<T>* temp;
while (nodePtr != nullptr)
{
temp = nodePtr;
nodePtr = nodePtr->next;
delete temp;
}
size = 0;
}
void insertAtTail(T val)
{
if (head == nullptr)
insertAtHead(val);
else
{
Node<T>* temp = new Node<T>;
temp->data = val;
curr->next = temp;
temp->next = nullptr;
tail = temp;
curr = temp;
size++;
}
}
// returns the value at the node location passed if it exists within the
// linked list, otherwise nothing is returned
T get(int location)
{
// std::cout << "size: " << size << std::endl;
if (location >= 0 && location <= size)
{
Node<T>* temp = head;
unsigned int counter = 0;
while (counter != location)
{
temp = temp->next;
counter++;
}
return temp->data;
}
}
};
#endif // LINKEDLIST_H
main.cpp
#include "linkedlist.h"
int main()
{
LinkedList<LinkedList<int>*> matrix;
matrix.insertAtTail(new LinkedList<int>);
matrix.get(0)->insertAtTail(6);
return 0;
}
并非所有路径 get(location)
return 一个值。
使用编译器的警告来查找此类问题(例如 -Wall -Wextra -pedantic
)。
此外,请确保在构造时初始化所有成员。
struct Node
{
T data {};
Node<T>* next = nullptr;
};
和
Node<T>* head = nullptr;
Node<T>* tail = nullptr;
Node<T>* curr = nullptr;
更新
更仔细地查看后,确实您从未删除外部列表中作为数据 T
的指针。由于您的列表不知道 T
是否是(拥有的)指针,因此它无法决定删除。
通常,我们使用智能指针包装器来解决这个问题。在您的情况下,您可能不会 "be allowed" 使用它,因此,在删除列表节点之前编写额外的循环来删除数据指针。
建议修复
这是一个重新设计的示例,它可以选择使用 NodeFree
类型模板参数,因此您可以为外部列表传入 std::default_delete<T>
:
template <typename T> struct DefaultNodeFree {
void operator()(T &) const {}
};
template<typename T, typename NodeFree = DefaultNodeFree<T> > class LinkedList
{
private:
struct Node {
T data {};
Node* next = nullptr;
~Node() { NodeFree()(data); }
};
所以你可以像这样使用它:
typedef LinkedList<int> inner;
LinkedList<inner*, std::default_delete<inner> > matrix;
matrix.insertAtTail(new LinkedList<int>);
matrix.get(0)->insertAtTail(6);
泄漏消失了。
现场演示
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <cassert>
#include <memory>
template <typename T> struct DefaultNodeFree {
void operator()(T &) const {}
};
template<typename T, typename NodeFree = DefaultNodeFree<T> > class LinkedList
{
private:
struct Node {
T data {};
Node* next = nullptr;
~Node() { NodeFree()(data); }
};
Node* head = nullptr;
Node* tail = nullptr;
Node* curr = nullptr;
unsigned int size;
void insertAtHead(T val)
{
Node* temp = new Node;
temp->data = val;
temp->next = nullptr;
head = temp;
tail = temp;
curr = temp;
size++;
}
public:
LinkedList()
{
head = nullptr;
tail = nullptr;
curr = nullptr;
size = 0;
}
~LinkedList()
{
Node* nodePtr = head;
while (nodePtr != nullptr)
{
Node* temp = nodePtr;
nodePtr = nodePtr->next;
delete temp;
size -= 1;
}
assert(size == 0);
}
void insertAtTail(T val)
{
if (head == nullptr)
insertAtHead(val);
else
{
Node* temp = new Node;
temp->data = val;
curr->next = temp;
temp->next = nullptr;
tail = temp;
curr = temp;
size++;
}
}
// returns the value at the node location passed if it exists within the
// linked list, otherwise nothing is returned
T get(unsigned location)
{
// std::cout << "size: " << size << std::endl;
if (location >= 0 && location <= size)
{
Node* temp = head;
unsigned int counter = 0;
while (counter != location)
{
temp = temp->next;
counter++;
}
return temp->data;
}
return {};
}
};
#endif // LINKEDLIST_H
int main()
{
typedef LinkedList<int> inner;
LinkedList<inner*, std::default_delete<inner> > matrix;
matrix.insertAtTail(new LinkedList<int>);
matrix.get(0)->insertAtTail(6);
}
根据我的经验,当你使用模板时,你可以在同一个头文件中实现它们,但你必须将实现与声明分开。
一个常见的解决方案是在头文件中编写模板声明,并在头文件末尾包含实现。 在此处阅读最高投票 Why can templates only be implemented in the header file?
我不确定这是否是您的问题,但上次我尝试按照您的方式实施模板时,我的程序根本无法运行。