C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Stack Overflow          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message MiniDisc_2k2 Guest Posted: Sat Jun 28, 2003 12:45 pm    Post subject: Stack Overflow All right, now here's a hard one: I was making a class which implements a linked list, and I need it to have a destructor (for obvious reasons). Unfortunately, if there's too many items in the linked list, I get a stack overflow (because the destructor is recursive, as you will see in a minute). Anyone see a way around this? (Simplified Example) class LinkedList { public: LinkedList *next; LinkedList *prev; int value; LinkedList(); ~LinkedList(); }; LinkedList::LinkedList() { next = prev = NULL; } LinkedList::~LinkedList() { if (next!=NULL) delete next; prev->next = NULL; } This destructor ensures that if the first element is deleted, none of the later elements will be "lost to the void." Is there any other destructor you guys can see that isn't recursive and ensures that memory leaks won't occur? Thanks for any help -- MiniDisc_2k2 [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Thomas Mang Guest Posted: Sat Jun 28, 2003 11:26 pm    Post subject: Re: Stack Overflow MiniDisc_2k2 schrieb: Quote: All right, now here's a hard one: I was making a class which implements a linked list, and I need it to have a destructor (for obvious reasons). Unfortunately, if there's too many items in the linked list, I get a stack overflow (because the destructor is recursive, as you will see in a minute). Anyone see a way around this? The answer is very, very simple: just use std::list<int>. If you are not familiar with the standard containers, I strongly suggest you to study them. regards, Thomas [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Dave Harris Guest Posted: Sat Jun 28, 2003 11:27 pm    Post subject: Re: Stack Overflow [email]MattDelB (AT) nospam (DOT) com[/email] (MiniDisc_2k2) wrote (abridged): Quote: LinkedList::~LinkedList() { if (next!=NULL) delete next; prev->next = NULL; } This destructor ensures that if the first element is deleted, none of the later elements will be "lost to the void." Is there any other destructor you guys can see that isn't recursive and ensures that memory leaks won't occur? You can keep the recursion to 1 level by removing nodes from the list before deleting: LinkedList::~LinkedList() { while (next != NULL) { LinkedList *nextNext = next->next; next->next = NULL; delete next; next = nextNext; } prev->next = NULL; } But is this what you want to do anyway? Perhaps deleting a node should not delete all the following ones, but merely unhook itself? LinkedList::~LinkedList() { if (next != NULL) next->prev = prev; if (prev != NULL) prev->next = next; } Now the following nodes will not be "list to the void". They'll still be in the list. -- Dave Harris, Nottingham, UK [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Corey Murtagh Guest Posted: Sun Jun 29, 2003 12:04 am    Post subject: Re: Stack Overflow MiniDisc_2k2 wrote: Quote: All right, now here's a hard one: I was making a class which implements a linked list, and I need it to have a destructor (for obvious reasons). Unfortunately, if there's too many items in the linked list, I get a stack overflow (because the destructor is recursive, as you will see in a minute). Anyone see a way around this? (Simplified Example) snip LinkedList::~LinkedList() { if (next!=NULL) delete next; prev->next = NULL; } You forgot to test prev before you assign to it. This method will truncate the list at the item you're deleting. While there may be advantages to doing so, wouldn't it be better to just delete the item and leave the list otherwise intact? You can still write a Truncate() method to do the above (or a non-broken version of the above at least :>) when needed. Try this instead: LinkedList::~LinkedList() { if (next) next->prev = prev; if (prev) prev->next = next; } // delete all items after this in list void LinkedList::Truncate() { if (!next) return; LinkedList* work = next; while (work->next) work = work->next; while (work != this) { LinkedList* temp = work->prev; delete work; work = temp; } // NB: this->next will be cleared by destructor above } This is more normal for a linked list implementation I think. -- Corey Murtagh The Electric Monk "Quidquid latine dictum sit, altum viditur!" [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Thomas Richter Guest Posted: Sun Jun 29, 2003 11:21 am    Post subject: Re: Stack Overflow MiniDisc_2k2 wrote: Quote: LinkedList::~LinkedList() { if (next!=NULL) delete next; prev->next = NULL; } Well, write an iterative one (but see my notes below): LinkedList::~LinkedList() { LinkedList *current = next,*keep; while(current) { keep = current->next; current->next = NULL; delete current; current = keep; } } Will recurse at most once per loop because it unlinks the elements before they get deleted. However: Do you think your design is sane? The problem here is that you need the caller to desctruct the head of the list to destruct all of it. If you delete erraneously an element in the middle of the list, the "next" pointer of the previous element remains "dangling". Recommendation: Introduce a "node" (list element) class that only destructs itself, and a "head" (list header node) class that destructs itself, and all its children. Greetings, Thomas [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Drew Hall Guest Posted: Sun Jun 29, 2003 11:22 am    Post subject: Re: Stack Overflow Hi, First, if you are doing this for more than just a learning exercise, you should consider using std::list instead--it's doubly-linked just as yours is, and interacts well with the standard algorithms. The simple answer to your stack overflow problem is to replace recursion with iteration. To do so, your best bet (in my opinion) is to have a separate "ListNode" class whose destructor is a no-op. Then, in the LinkedList class, you just iterate over the nodes & delete them one by one (make sure that you get a pointer to the next node before you delete the current one, obviously). But that's about all there is to it--no stack overflow problems anymore. Good luck! Drew "MiniDisc_2k2" <MattDelB (AT) nospam (DOT) com> wrote Quote: All right, now here's a hard one: I was making a class which implements a linked list, and I need it to have a destructor (for obvious reasons). Unfortunately, if there's too many items in the linked list, I get a stack overflow (because the destructor is recursive, as you will see in a minute). Anyone see a way around this? (Simplified Example) class LinkedList { public: LinkedList *next; LinkedList *prev; int value; LinkedList(); ~LinkedList(); }; LinkedList::LinkedList() { next = prev = NULL; } LinkedList::~LinkedList() { if (next!=NULL) delete next; prev->next = NULL; } This destructor ensures that if the first element is deleted, none of the later elements will be "lost to the void." Is there any other destructor you guys can see that isn't recursive and ensures that memory leaks won't occur? [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Michael Tiomkin Guest Posted: Sun Jun 29, 2003 11:30 am    Post subject: Re: Stack Overflow "MiniDisc_2k2" <MattDelB (AT) nospam (DOT) com> wrote Quote: All right, now here's a hard one: I was making a class which implements a linked list, and I need it to have a destructor (for obvious reasons). Unfortunately, if there's too many items in the linked list, I get a stack overflow (because the destructor is recursive, as you will see in a minute). Anyone see a way around this? (Simplified Example) class LinkedList { public: LinkedList *next; LinkedList *prev; int value; LinkedList(); ~LinkedList(); }; LinkedList::LinkedList() { next = prev = NULL; } LinkedList::~LinkedList() { if (next!=NULL) delete next; prev->next = NULL; } This destructor ensures that if the first element is deleted, none of the later elements will be "lost to the void." Is there any other destructor you guys can see that isn't recursive and ensures that memory leaks won't occur? I think that your destructor will enter infinite loop for every non-empty list. It will never find a NULL 'next' ptr because the assignment is put AFTER deletion of the next item. Try to change the condition used to stop the loop, e.g. LinkedList::~LinkedList() { if (next != this) // next is different from current { // exclude the current item; prev might be == next prev->next = next; next->prev = prev; delete next; } } If you want an iterative destructor, you can prevent all the other destructors from entering the loop with modification of their data, e.g. LinkedList::~LinkedList() { while(next != this) // next is different from current, otherwise nothing to do { // prepare the next step LinkedList * next_step = next->next; // will be invalid after deletion next->next = next; // makes 'next == this' in 'next' delete next; next = next_step; } } BTW, you have a problem that your 'LinkedList' is never empty. Most of containers (including your pockets and bank accounts) allow themselves to be empty. The solution can be to make an internal class/struct of a node, and to keep a ptr to a head node of a list. When the head is null, the list is empty. Another solution can be to use a dummy node as a head of the list. As usual, we have the space/time problem here: the first solution needs less memory, but the second solution runs faster - the iterators are much simpler. An example of the first solution is given below. I think you can find an example of the second solution in your STL implementation of double linked list. class LinkedList { private: struct node { node *next; node *prev; int value; }; node *head; public: LinkedList() { head = 0;} ~LinkedList() { while (head) { node * next = head->next; delete head; head = next; } } ... insert/delete/find a value ... }; Good luck! Michael [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Dave Harris Guest Posted: Sun Jun 29, 2003 12:36 pm    Post subject: Re: Stack Overflow [email]emonk (AT) slingshot (DOT) co.nz[/email] (Corey Murtagh) wrote (abridged): Quote: // delete all items after this in list void LinkedList::Truncate() [9 lines of code] I can't resist pointing out a shorter version: void LinkedList::Truncate() { while (next) delete next; } (The original problem needs a "delete this;" at the end too.) -- Dave Harris, Nottingham, UK [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top MiniDisc_2k2 Guest Posted: Sun Jun 29, 2003 10:14 pm    Post subject: Re: Stack Overflow Quote: I think that your destructor will enter infinite loop for every non-empty list. It will never find a NULL 'next' ptr because the assignment is put AFTER deletion of the next item. Try to change the condition used to stop the loop, e.g. Uh, I have no idea what you're talking about, but the NULL condition works. Quote: LinkedList::~LinkedList() { if (next != this) // next is different from current this will _never_ be true. I never initialized it to this. Quote: BTW, you have a problem that your 'LinkedList' is never empty. Here's how it's empty: int main() { LinkedList* first_element = NULL; } It's empty. It's not really a container but more a bunch of addresses strung together. This class should NEVER be used as a non-pointer type (unless dereferencing it to get the data out). I didn't want to make a full-blown container because it's just more coding and what I had done was sufficient. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT Page 1 of 1   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.