我正试图修复这个双链表中的一些内存泄漏。我的析构函数似乎出错了。我需要删除析构函数之外的任何东西吗?有了这个，我试图保持所有的删除语句在它。任何帮助都是感激的。下面是valgrind给我的:
==29075== Invalid read of size 8
==29075== at 0x400BC0: DblLinkedList<int>::~DblLinkedList() (DblLinkedList.cpp:32)
==29075== by 0x400ABF: main (DblLinkedList.cpp:215)
==29075== Address 0x5a04050 is 16 bytes inside a block of size 24 free'd
==29075== at 0x4C2A4BC: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==29075== by 0x400BBB: DblLinkedList<int>::~DblLinkedList() (DblLinkedList.cpp:31)
==29075== by 0x400ABF: main (DblLinkedList.cpp:215)
==29075==
==29075== Invalid read of size 8
==29075== at 0x400BEC: DblLinkedList<int>::~DblLinkedList() (DblLinkedList.cpp:36)
==29075== by 0x400ABF: main (DblLinkedList.cpp:215)
==29075== Address 0x5a040a8 is 8 bytes inside a block of size 24 free'd
==29075== at 0x4C2A4BC: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==29075== by 0x400BE7: DblLinkedList<int>::~DblLinkedList() (DblLinkedList.cpp:35)
==29075== by 0x400ABF: main (DblLinkedList.cpp:215)
==29075==
==29075== Invalid read of size 8
==29075== at 0x400BF8: DblLinkedList<int>::~DblLinkedList() (DblLinkedList.cpp:34)
==29075== by 0x400ABF: main (DblLinkedList.cpp:215)
==29075== Address 0x5a04048 is 8 bytes inside a block of size 24 free'd
==29075== at 0x4C2A4BC: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==29075== by 0x400BBB: DblLinkedList<int>::~DblLinkedList() (DblLinkedList.cpp:31)
==29075== by 0x400ABF: main (DblLinkedList.cpp:215)
==29075==
==29075== Invalid free() / delete / delete[] / realloc()
==29075== at 0x4C2A4BC: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==29075== by 0x400BE7: DblLinkedList<int>::~DblLinkedList() (DblLinkedList.cpp:35)
==29075== by 0x400ABF: main (DblLinkedList.cpp:215)
==29075== Address 0x5a04040 is 0 bytes inside a block of size 24 free'd
==29075== at 0x4C2A4BC: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==29075== by 0x400BBB: DblLinkedList<int>::~DblLinkedList() (DblLinkedList.cpp:31)
==29075== by 0x400ABF: main (DblLinkedList.cpp:215)
==29075==
==29075==
==29075== HEAP SUMMARY:
==29075== in use at exit: 96 bytes in 4 blocks
==29075== total heap usage: 7 allocs, 4 frees, 168 bytes allocated
==29075==
==29075== 24 bytes in 1 blocks are definitely lost in loss record 1 of 4
==29075== at 0x4C2B1C7: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==29075== by 0x400D00: DblLinkedList<int>::insertFirst(int) (DblLinkedList.cpp:75)
==29075== by 0x4009FB: main (DblLinkedList.cpp:192)
==29075==
==29075== 24 bytes in 1 blocks are definitely lost in loss record 2 of 4
==29075== at 0x4C2B1C7: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==29075== by 0x400D54: DblLinkedList<int>::insertLast(int) (DblLinkedList.cpp:85)
==29075== by 0x400A28: main (DblLinkedList.cpp:196)
==29075==
==29075== 24 bytes in 1 blocks are definitely lost in loss record 3 of 4
==29075== at 0x4C2B1C7: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==29075== by 0x400B84: DblLinkedList<int>::~DblLinkedList() (DblLinkedList.cpp:26)
==29075== by 0x400ABF: main (DblLinkedList.cpp:215)
==29075==
==29075== 24 bytes in 1 blocks are definitely lost in loss record 4 of 4
==29075== at 0x4C2B1C7: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==29075== by 0x400B92: DblLinkedList<int>::~DblLinkedList() (DblLinkedList.cpp:27)
==29075== by 0x400ABF: main (DblLinkedList.cpp:215)
==29075==
==29075== LEAK SUMMARY:
==29075== definitely lost: 96 bytes in 4 blocks
==29075== indirectly lost: 0 bytes in 0 blocks
==29075== possibly lost: 0 bytes in 0 blocks
==29075== still reachable: 0 bytes in 0 blocks
==29075== suppressed: 0 bytes in 0 blocks
==29075==
==29075== For counts of detected and suppressed errors, rerun with: -v
==29075== ERROR SUMMARY: 10 errors from 8 contexts (suppressed: 2 from 2)
代码如下:
#include <iostream>
using namespace std;
template <class T>
class DblLinkedList
{
private:
struct node
{
T data;
node* prev;
node* next;
};
node* head;
node* tail;
int count;
public:
DblLinkedList() {
head = nullptr;
tail = nullptr;
count = 0;
}
/** This seems to be the
problem right here **/
~DblLinkedList(){
node* p = new node;
node* q = new node;
p = head;
q = tail;
while(p->next != nullptr){
delete p;
p = p->next;
}
while(q->prev != nullptr){
delete q;
q = q->prev;
}
}
void createList(T[], int);
void insertFirst(T);
void insertLast(T);
void insertAfter(T,T);
};
//creating DblLinkedList
template<class T>
void DblLinkedList<T>::createList(T x[], int n)
{
node* q;
node* p = new node; //first node
head = p;
p->data = x[0];
p->next = nullptr;
p->prev = nullptr;
for(int tom = 1; tom < n; tom++){
q = p;
p = p->next = new node;
p->data = x[tom];
p->next = nullptr;
p->prev = q;
count++;
}
tail = p;
}
//insert new node at start of DblLinkedList
template <class T>
void DblLinkedList<T>::insertFirst(T item){
node *p = new node;
p->data = item;
p->prev = nullptr;
head->prev = p;
count++;
}
//insert node at end of DblLinkedlist
template<class T>
void DblLinkedList<T>::insertLast(T item){
node *p = new node;
p->data = item;
p->prev = nullptr;
head->prev = p;
count++;
}
//insert new node after an item in DbLinkedList
template <class T>
void DblLinkedList<T>::insertAfter(T item, T k)
{
node *q = head;
while (q != nullptr){
if(q->data == k){ break; }
q = q->next;
}
if(q == nullptr)
{
cout << key << "not found" << endl;
return;
}
node *p = new node;
p->data = item;
p->next = q->next;
p->prev = q;
q->next = p;
count++;
}
int main()
{
int x[2] = {33,44};
DblLinkedList<int> dList;
dList.createList(x, 2);
cout << "Insert First 22" << endl;
dList.insertFirst(22);
cout << "Insert Last 55" << endl;
dList.insertLast(55);
cout << "Insert 66 After 33" << endl;
dList.insertAfter(66,33);
return 0;
}
修复内存泄漏最简单的方法是使用std::list:
#include <list>
#include <iostream>
#include <algorithm>
int main()
{
int const x[2] = {33,44};
std::list<int> dList(std::begin(x), std::end(x));
std::cout << "Insert First 22" << std::endl;
dList.push_front(22);
std::cout << "Insert Last 55" << std::endl;
dList.push_back(55);
std::cout << "Insert 66 After 33" << std::endl;
std::list<int>::iterator it {
std::find(std::begin(dList), std::end(dList), 33) };
if( it!=dList.end() ) {
dList.insert(it, 66);
}
for( auto const li : dList ) {
std::cout << "o " << li << std::endl;
}
return 0;
}
$ valgrind ./a.out
==7126== Memcheck, a memory error detector
==7126== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==7126== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==7126== Command: ./a.out
==7126==
Insert First 22
Insert Last 55
Insert 66 After 33
o 22
o 66
o 33
o 44
o 55
==7126==
==7126== HEAP SUMMARY:
==7126== in use at exit: 0 bytes in 0 blocks
==7126== total heap usage: 5 allocs, 5 frees, 120 bytes allocated
==7126==
==7126== All heap blocks were freed -- no leaks are possible
==7126==
==7126== For counts of detected and suppressed errors, rerun with: -v
==7126== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 4 from 4)
删除双链表与删除单链表相同。您不必遍历尾部来清理列表。
while(p->next != nullptr)
{
delete p; // p is deleted here
p = p->next; // never perform a operation on pointer which is deleted
}
应该是
node* p = head;
while( p != 0 ) {
node* next = p->next;
delete p;
p = next;
}
head = 0;
使用容器作为指针以避免内存管理的开销。您可以使用unique_ptr容器来管理指针。你可以在下面找到更多的细节
http://en.wikipedia.org/wiki/Smart_pointer http://www.cplusplus.com/reference/memory/unique_ptr/http://www.cplusplus.com/reference/memory/unique_ptr/unique_ptr/