c++ - Destructor for LinkedList of LinkedLists -
for assignment in 1 of programming classes have make adjacency list linked list of linked lists this.
a->b->c
↓
b->a->d
↓
c->d
↓
d->a->b->c
i'm having trouble memory leak when trying free memory allocated in destructor. i've been trying figure out while haven't found/come solutions work.
also, please ignore implementation included in header file. told ok assignment.
valgrind error message:
==2316== heap summary:
==2316== in use @ 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 lost in loss record 2 of 2
==2316== @ 0x4c2b0e0: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2316== 0x4012ee: main (main.cpp:34)
==2316==
==2316== leak summary:
==2316== 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== counts of detected , suppressed errors, rerun with: -v
==2316== error summary: 1 errors 1 contexts (suppressed: 0 0)
here of code i'm using (compiled 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 value @ node location passed if exists within // linked list, otherwise nothing 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; }
not paths of get(location) return value.
use compiler's warnings find issues these (e.g. -wall -wextra -pedantic).
also, make sure initialize members @ construction.
struct node { t data {}; node<t>* next = nullptr; }; and
node<t>* head = nullptr; node<t>* tail = nullptr; node<t>* curr = nullptr; update
after reviewing more closely, indeed never delete pointer data t in outer list. since list doesn't know whether t (owned) pointer, cannot decide delete.
usually, use smart pointer wrappers address this. in case may not "be allowed" use that, so, write loop delete data pointers before deleting list nodes.
suggested fix
here's reworked example optionally takes nodefree type template argument, can pass in std::default_delete<t> outer list:
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); } }; so can use like:
typedef linkedlist<int> inner; linkedlist<inner*, std::default_delete<inner> > matrix; matrix.insertattail(new linkedlist<int>); matrix.get(0)->insertattail(6); and leak gone.
live demo
#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 value @ node location passed if exists within // linked list, otherwise nothing 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); }
Comments
Post a Comment