Thread: Inheriting Linked List

Originally Posted by robolee

Hi, straight to the point: I have a good working linked list that I want a bunch of structs to inherit. Using "struct blah : Object {code};" doesn't work and I know I could get the same thing by copying the code and pasting it into all my structs and renaming parts but that would be a whole lot of copypasta and a big mess... I've read a lot of stuff on inheritance and other stuff and have learnt everything I know about c++ from internet resources, and I've been working on this linked list business for ages and I finally decided to just join a random forum and ask for help (the whole thing would have been a whole damned lot quicker if I just asked in the first place but I guess I like to struggle at things on my own).

Here's the linked list stuff, I want a way for a regular struct to inherit it:

Code:

typedef struct Object{//an "object" of the list
	Object *Next;
	Object *Previous;
	void Add();
	void Remove(Object *n);
	void CleanList();
} Object;

Object *First;
Object *Last;
Object *ListPointer;

void Object::Add(){
	Object *Temp;
	if (First){// If the list already has a First (the list exists)
		Temp = new Object;		//NULL <-- |First|...|Last| --> NULL
		Last->Next = Temp;		//NULL <-- |First|...|Last| --> |temp|
		Temp->Previous = Last;	//NULL <-- |First|...|Last| <-> |temp|
		Temp->Next = NULL;		//NULL <-- |First|...|Last| <-> |temp| --> NULL
		Last = Temp;			//NULL <-- |First|...|oldL| <-> |Last| --> NULL
		ListPointer = Last;		//NULL <-- |First|...|Last| --> NULL //and last is pointed to by the list
		Temp = NULL;
		delete Temp;
	}
	else{//there is no list yet
		ListPointer = new Object;
		First = ListPointer;
		Last = ListPointer;
		ListPointer->Next = NULL;
		ListPointer->Previous = NULL;// NULL <-- |newPA| --> NULL
		First = ListPointer;
		Last = ListPointer;// NULL <-- |new/First/Last| --> NULL
	}
};
void Object::Remove(Object *n){
	if (n != First){
		if (n->Next){
			Object *tempb;
			tempb = new Object;
			tempb->Previous = n->Previous;
			delete tempb;
		}
		if (Last == n){
			Last = n->Previous;
		}
	}
	if (n != Last){
		if (n->Previous){
			Object *tempc;
			tempc = new Object;
			tempc->Next = n->Next;
			delete tempc;
		}
		if (First == n){
			First = n->Next;
		}
	}
	n->Next = NULL;
	n->Previous = NULL;
};
void Object::CleanList(){				 // Destroys the entire list
	Object *tempa, *r;
	r = new Object;
	tempa = new Object;
	r = First;	// Start at the First Object of this list, for better speed
	while (r){				// While r still means something
		tempa = r->Next;			// Save our next APointer
		r->Remove(r);				// Remove the one we're at
		r = tempa;				// And advance.
	}
	delete r;
	delete tempa;
	delete ListPointer;
	First = NULL;
	Last = NULL;
};

Oh dear, that code has too many bugs in it to ever hope to possibly cover in one post.

Ah crap, I clicked the wrong button. I'm just going to pick one function:
Here goes:

Code:

void Object::CleanList(){				 // Destroys the entire list
	Object *tempa, *r;

tempa shouldn't even be declared here as it is only used inside the while loop and should thus be declared there.

Code:

	r = new Object;

Don't use new here, you don't allocate memory to perform a clear of the list. All this does is leak

Code:

	tempa = new Object;

Again, don't use new here. All this does is leak

Code:

	r = First;	// Start at the First Object of this list, for better speed

First should not be a global, it should be a member variable. This list cannot be reused, i.e. you can't have two or more lists.

One thing done right! You've correctly avoided accessing deleted memory!

Code:

	while (r){				// While r still means something
		tempa = r->Next;			// Save our next APointer
		r->Remove(r);				// Remove the one we're at
		r = tempa;				// And advance.
	}

Code:

	delete r;

r is NULL here. delete wont have any effect here.

Code:

	delete tempa;

tempa is also NULL here

Code:

	delete ListPointer;

Assuming remove already deletes the node pointed to (as it should), then this is a double-delete bug

Code:

	First = NULL;
	Last = NULL;

If these were correctly member variables of some kind of reusable list class then these lines wouldn't be necessary

Code:

};

Last but not least, never claim code is bug-free.

I think you haven't understood a word I have written, I have a bunch of structs with data and linked list functions and pointers, I want to take out the repetitive linked list stuff write it out once, and have a way for the different structs to inherit the linked list functions and pointers so I have all these structs with different linked lists.

this "Object" struct won't do anything because there is no data, I know that, however if I take my particle linked list then I can do stuff with it, the "Object" struct does nothing.

I already have a partially working game engine, I know for a fact that my linked list implementation works because I had over 6 particles (bullets) on screen at the same time, and after many shots there were no apparent memory leaks.

seems the above got in before I posted this, but what I mean by bug free is debugger didn't flag any bugs, I wouldn't claim to have perfectly bug-free code in any other way than that. and I don't think most people could claim it in any way other than that.

what? there were a few bullets on screen because they were all shot one after another and disappeared after they left the screen, reducing the lifetime of theparticles removes the bullets before they get chance to go off-screen, showing that the remove function either works or are you trying to say that they disappear by coincidence when remove is called due to a bug. however I think this version and the version in the game engine might be slightly different, I'm ill have a huge headache and am now going to bed.