question about destructors and user-defined structs

[kotoro]

I just wanted to check whether the following destructors are necessary at all or whether they are implicitly defined. Would the compiler define an implicit destructor that deletes *next when you delete an instantiation of these structs?
as far as using the objects in my main method, I know I would have to delete after using new, I'm just wondering if delete would implicitly follow the pointers to the end of the list or if I have to write that behavior into the struct myself.

typedef struct posnode posnode;
struct posnode
{
	unsigned char file;
	short int pos;
	posnode *next;
	posnode(void)
	{
		file=0;
		pos=0;
		next=NULL;
	}
	posnode(char f,short int p)
	{
		file=f;
		pos=p;
		next=NULL;
	}
	void insert_after(posnode *p)
	{
		posnode *temp;
		temp=next;
		next=p;
		p->next=temp;
	}
	~posnode()
	{
		delete next;
	}
};
typedef struct match match ;
struct match
{
	posnode *head;
	posnode *tail;
	match *next;
	match(void)
	{
		head=NULL;
		tail=NULL;
		next=NULL;
	}
	void addpos(posnode *p)
	{
		if(head==NULL)
		{
			head=p;
			tail=p;
		}
		else
		{
			tail->next=p;
			tail=p;
		}
	}
	~match()
	{
		delete next;
		delete head;
	}
};

also there is a practical reason that I'm writing this structure this way instead of using the STL list, I have an extreme need to save memory as much as possible.

[Aakanaar]

you'll have to write it into the stuctures yourself. That would be a good candidate for the destructors.

[kotoro]

ok assuming that they're necessary, have I done this correctly?

[anilpanicker]

struct posnode
In the destructor, you don't require
delete next;
because 'next' is not created during the construction of posnode.
Similarly
struct match
destructor you don't require
delete next;
delet head;

[kotoro]

yes but they ARE created shortly after, and it doesnt hurt you if you delete NULL right?

[anilpanicker]

I'm assuming that
posnode *next;
holds the next node.
Then the program will crash.
See this small example: Run it and see (remove the comment), because we delete next node when we are on one node it will go in a loop will crash when it cannot access the memory any more.
We don't require to delete next; in the destructor.
Each node will destroy itself when you call delete for that node.
Hope you understand.

#include<iostream>
using std::cout;

class Node{
public:
	int Id;
	Node(){Id=0;}
	Node(int id):Id(id){}
	~Node(){
		cout<< "I'm->" << Id << " : I'm inside the destructor\n";
		/*
		if(next !=NULL){
			delete next;
			next=NULL;
		}
		*/		
	}
	Node* next;
};

void study(){
	Node* a= new Node(1);
	Node* b= new Node (2);
	Node* c= new Node (3);
	// Assign the next
	a->next=b;
	b->next=c;
	c->next=NULL;
	//c->next=a;
	delete c;
	c=NULL;
	delete a;
	a=NULL;
	delete b;
	b=NULL;

	
}

int main(){
	study();
	

	return 0;
}

[kotoro]

well as far as your example goes, I wouldn't allow the program to get into a situation where it tries to delete b after deleting a, there won't be any standing pointers to the inside of the list except for the first element and last element and those will not be accessed after the list is destroyed. The pointers that iterate over the list will only access data, not delete it, deletions occur in bulk if at all, which means the references would be lost and create a memory leak unless there is a garbage collector to come and cleans it up or the destructor invokes a delete against the elements it points to.

[anilpanicker]

The program is crashing at line 32 while deleting a,
when it deleting a, its next b will be deleted from a's destructor. it won't reach line 34 delete b.
Any order this will happen.
If you are planning to use your program in somer way, please ignore my comments.

[kotoro]

say I add several posnodes to a match, and if I use delete on the match struct, the posnodes would have no pointers to them. Is the only way to be absolutely sure to avoid a memory leak to iterate through the list and delete all the nodes on the way through before using delete on the match struct?

and I think I see the reason that code crashes, deleting c if c->next == a attempts to deletes the entire list, because if I remove the comment it becomes a circular list; I dont intend to be using circular lists, and whenever I delete these objects it will be deleted from the head to the tail. Individual nodes are only added once I'm sure they belong there, so they wouldn't be deleted by themselves. Besides, if they were, i'd have fixed the references involved effectively removing them from the linked list and rendering them into isolated nodes beforehand.


If we take a look at the destructor you wrote, writing it this way keeps it from looping like crazy, but it still drags the destructor into parts of memory that it doesn't belong if you try to delete any of the nodes and then delete any other node following that without setting the reference to null first. With this destructor you can destroy the linked list in circular form by using delete at any point in the loop.

	~Node()
	{
		Node* temp;
		cout<< "I'm->" << Id << " : I'm inside the destructor\n";
		/**/
		if(next !=NULL)
		{
			temp=next;
			next=NULL;
			delete temp;
		}
		//*/		
	}

However my code isn't like this, it has the following structs

struct Posnode
{
	unsigned short int file;
	short int pos;
	struct Posnode *next;
	Posnode(char f,short int p)
	{
		file=f;
		pos=p;
		next=NULL;
	}
	void insert_after(struct Posnode *p)
	{
		struct Posnode *temp;
		temp=next;
		next=p;
		p->next=temp;
	}
#ifdef DEBUG_DESTRUCTORS
	~Posnode(void)
	{
		cout<<"posnode deleted"<<endl;
	}
#endif
};
typedef struct Posnode posnode;
struct Match
{
	struct Posnode *head;
	struct Posnode *tail;
	struct Match *next;
	Match(void)
	{
		head=NULL;
		tail=NULL;
		next=NULL;
	}
	void addpos(struct Posnode *p)
	{
		if(head==NULL)
		{
			head=p;
			tail=head;
		}
		else
		{
			tail->next=p;
			tail=tail->next;
		}
	}
#ifdef DEBUG_DESTRUCTORS
	~Match(void)
	{
		if(head!=NULL)
		{
			cout<<"match deleted"<<endl;
		}
	}
#endif
};
typedef struct Match match;
struct Matchlist
{
	struct Match *head;
	struct Match *tail;
	Matchlist(void)
	{
		head=NULL;
		tail=NULL;
	}
	void addmatch(struct Match *m)
	{
		if(head==NULL)
		{
			head=m;
			tail=head;
		}
		else
		{
			tail->next=m;
			tail=tail->next;
		}
	}
#ifdef DEBUG_DESTRUCTORS
	~Matchlist()
	{
		cout<<"Matchlist deleted"<<endl;
	}
#endif
};
typedef struct Matchlist matchlist;

These are contained in a
deque <matchlist> matches;

These are constructed dynamically during a DNA data mining algorithm with a pointer to a match object; The new match object has its next==NULL at all times while it is being constructed, if the match passes muster it is stored in the matchlist using the addmatch member function.

As the list inside a match object is being built, posnodes are created whenever new positions are found that are part of the match and are stored in the match object using its addpos member function.

Any references made to the master list are access-only, the only time any of these things faces deletion is when the match is being checked before it is added to the matchlist in the deque or at the end of the program.

The key to my worry about memory leaks lies in the potential for the new match object to NOT pass the requirements and need to be deleted. At that point I need to make sure all the attached posnodes are cleaned up, and as long as the deletion can procede from head to tail, no references will remain.

[anilpanicker]

Now there is no delete next ; in the destructor so no confusion.
You may need to modify the position of ifdef-endif tags, otherwise this destructor is used only in the DEBUG mode

	~Matchlist()
	{
#ifdef DEBUG_DESTRUCTORS
		cout<<"Matchlist deleted"<<endl;
#endif
	}

I have created this example function to show you how to create and delete all the objects without making a any memory leak

void Example1();
int main(){
	Example1();
	return 0;
}

void Example1(){

	deque <matchlist> matches;
	// we will create two match
	match* a= new match();
	match* b= new match();
	// we put 5 posnode each in these match
	// Note 10 posnodes are created with 'new'

	for(int i=0; i<10; i++){
		if(i<5){
				a->addpos(new posnode(char(65+i),i));
		
		}else{
			b->addpos(new posnode(char(65+i),i));
		
		}
	
	}
	// create a match list
	matchlist ml;
	ml.addmatch(a);
	ml.addmatch(b);

	// put these matches in the matches
	matches.push_back(ml);
	
	// Now we have a 'matches' with one 'matchlist' which has 
		//dynamicaly created match a and match b
	// match a has five dynamicllay created posnode objects
	//match b has five dynamicllay created pos nodeobjects

	// To avoid memory leak we should delete the dynamically created objects before it goes out of scope
	// In this case 'matches'- the top level object which has all other objects
	// 'matches' goes out of scope when this function returns
	// so we need to delete all dynamically created objects when
	//'matches' goes out of scope when this function returns
	for(int j=0; j<matches.size();j++){
	
		matchlist aList=matches.at(j);
		match* amatch=aList.head;
		while(amatch != NULL){
			match* tempMatch=amatch->next;
			posnode* aposList=amatch->head;
			while(aposList !=0){
				posnode* tempPosnode=aposList->next;
				cout<< char(aposList->file)<<"-" <<aposList->pos<<"\n";
				delete aposList;
				aposList=tempPosnode;
			
			}

			delete amatch;
			amatch=tempMatch;
		}
	}

	// clear matches

	matches.clear();
}

Here
deque <matchlist> matches; is used local to the Example1() function. If you are using this as a global variable, then do the same clean up just before it goes out of scope
The output of this is given below

A-0
posnode deleted
B-1
posnode deleted
C-2
posnode deleted
D-3
posnode deleted
E-4
posnode deleted
match deleted
F-5
posnode deleted
G-6
posnode deleted
H-7
posnode deleted
I-8
posnode deleted
J-9
posnode deleted
match deleted
Matchlist deleted
Matchlist deleted
Matchlist deleted
Press any key to continue

After the first 5 posnode deleted, a match is deleted
Then second 5 posnode deleted, a match is deleted
There are three Matchlist delted
First one come from the local variable aList
the second one comes from .clear()
the third one comes from variable ml, when this function return to main it goes out of scope