🎉 Celebrating 25 Years of GameDev.net! 🎉
Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!
Template Linked Lists
Author
I am writing a linked list for my level editor for my game, and am having a little trouble. I''m writing it as a template class, because I need to use it for two or three different types, and that''s where the trouble I''m having lies. I''ve made a linked list before, and I think most of my code seems sound. What would be great is to have some method other than using templates. I have head people talking about making a list class, and making everything that needs a list derive from that class. How is this done? I know more about OOP and inheritance than about templates, and I think I would rather use it than the templates. So how would I do this? Or is there some other alternative to easily use one copy of the list code with multiple types (all classes, no base types)?
------------------------------
Jonathan Little
invader@hushmail.com
http://www.crosswinds.net/~uselessknowledge
Basically you do:
class LinkedListNode {
private:
LinkedListNode * next;
public:
LinkedListNode();
LinkedListNode * GetNextNode();
void SetNextNode(LinkedListNode *next_node);
}
Or whatever functionality you need. And then:
class FlyingCows : LinkedListNode {
public:
int velocity;
int direction;
}
Then you can use:
FlyingCows * head = new FlyingCows();
head->SetNextNode(new FlyingCows());
Or whatever you want.
An alternative is to use void * for data in your linked list. Then you only have one set of linked list code for all data types.
Edited by - SiCrane on 1/23/00 8:51:16 PM
class LinkedListNode {
private:
LinkedListNode * next;
public:
LinkedListNode();
LinkedListNode * GetNextNode();
void SetNextNode(LinkedListNode *next_node);
}
Or whatever functionality you need. And then:
class FlyingCows : LinkedListNode {
public:
int velocity;
int direction;
}
Then you can use:
FlyingCows * head = new FlyingCows();
head->SetNextNode(new FlyingCows());
Or whatever you want.
An alternative is to use void * for data in your linked list. Then you only have one set of linked list code for all data types.
Edited by - SiCrane on 1/23/00 8:51:16 PM
When using the void data type you must remember that any traversal of the list checking for values must explicitly cast the void pointer to whatever class the list is storing. Casting can become expensive as the number of nodes that need to be searched increases. If your keeping order in the list as well then all inserts, updates, and deletes imply searches, therefore casts. Just thought I would let you know that while void seems to be the answer it is pretty heavily penalized by the performance you get in return.
Kressilac
ps Templates were used as a way to tell the compiler that this list stores this element. It is a direct attempt to get around the casting problem of using the void pointer.
Kressilac
ps Templates were used as a way to tell the compiler that this list stores this element. It is a direct attempt to get around the casting problem of using the void pointer.
Or just use the STL 
. It gets old rewriting the same old base ADTs over and over again. In the absence of a specific reason not to use an STL class in your implementation, I''d say use ''em 
Oh, and remember,
#pragma warning(disable:C4786) is your friend, if you do end up using STL inside Visual C++.
Notwen
. It gets old rewriting the same old base ADTs over and over again. In the absence of a specific reason not to use an STL class in your implementation, I''d say use ''em Oh, and remember,
#pragma warning(disable:C4786) is your friend, if you do end up using STL inside Visual C++.
Notwen
Casting is more expensive in C++ than it is in C. This has to do with inheritance and the like. Casting a void pointer in C has almost no overhead.
Casting has performance penalties?? Since when. Its all done at compile time. There should be no runtime overhead involved.
The only cast with a penalty hit would be dynamic cast, and that can only be allowed if you switch on RTTI, which of course is another different story altogether.
Avoid void* at all cost. It''s not type safe
Avoid void* at all cost. It''s not type safe
Author
I think I like SiCrane''s method. I was forgetting that you could refer to a derived class with a pointer to the base class in C++. It''s been a while since I used inheritance I don''t want to use the STL because I''m still learning, and I want to go through the motions this time. So I think this sounds like a good approach.
I don''t want to use the STL because I''m still learning, and I want to go through the motions this time. So I think this sounds like a good approach.
Casting can have performance penalties in C++ when casting classes. At run-time certain information about a class is stored so that the correct version of a virtual function can be called.
For example, I have a Sprite class, and it specifies the virtual function void Tick(void). Then I create a Cow class that is descended from Sprite, Cow then overrides void Tick(void). If I have a linked list of Sprites, stored as a void *, and I slip a Cow in there, then at runtime I cast them to sprites, it should call the Tick for all the non-Cow sprites and the Cow Tick for the Cow objects. That incurs a runtime overhead. The key here is that it should know a Cow is a Cow even if I'm calling it a Sprite.
There's a couple of other times when you get a runtime penalty for casting, but virtual function calls are the big one.
Edited by - SiCrane on 1/24/00 12:32:04 AM
For example, I have a Sprite class, and it specifies the virtual function void Tick(void). Then I create a Cow class that is descended from Sprite, Cow then overrides void Tick(void). If I have a linked list of Sprites, stored as a void *, and I slip a Cow in there, then at runtime I cast them to sprites, it should call the Tick for all the non-Cow sprites and the Cow Tick for the Cow objects. That incurs a runtime overhead. The key here is that it should know a Cow is a Cow even if I'm calling it a Sprite.
There's a couple of other times when you get a runtime penalty for casting, but virtual function calls are the big one.
Edited by - SiCrane on 1/24/00 12:32:04 AM
But that has nothing to do with the cast. Its just normal polymorphism. That''s why virtual funcs are slower than any others. If you had a list of Sprite object pointers instead of void pointers, it would still do the exact same thing at runtime. Casts are all compiled, not dynamic.
The only time it matters is with RTTI as dot said. But who uses that for games?
The only time it matters is with RTTI as dot said. But who uses that for games?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement