23 users logged in
Proud partner of GDC 2025
Before posting, review our community guidelines.
Support GameDev.net with a monthly GDNet+ subscription!
Linked list question...
August 02, 2001 08:45 AM
i have a generic linked list template that has a struct defined for each node which, in turn, has a void pointer to point off to some data (whatever you want to include in the list). Each node is auto-generated an ID when it is added, which is the search indicator. NOTE: the structure for the node is outside of the template class definition.
My question is this -
Using this list in a tile based game, should i iterate through the entire list until a match is found on the void pointer's data? i have a feeling this will be too slow - if so, anyone have any recommendations as to how i should set this up (i.e. create another linked list type specific for this game)?
Lastly, can template functions be virtual?
Thanks!!!
"You call him Dr. Grip, doll!"
Edited by - the_grip on August 2, 2001 9:52:14 AM
"You call him Dr. Grip, doll!"
August 02, 2001 08:55 AM
i don't mean to bugger on and on about this, but here is my header file for the template code:
Thanks!
"You call him Dr. Grip, doll!"
Edited by - the_grip on August 2, 2001 10:03:11 AM
|
Thanks!
"You call him Dr. Grip, doll!"
Edited by - the_grip on August 2, 2001 10:03:11 AM
"You call him Dr. Grip, doll!"
122
August 02, 2001 09:21 AM
Hi,
a linked list is fine for fast insertions, but it doesnt say anything about how fast it finds its entries. This depends on
1) if and how you sort your list
2) how you find elements (linear search or whatever)
If insertions should be fast, you should try to sort your list.
On what your list is sorted depends on the usage (e.g. rendering materials -> minimize state changes, texture changes etc.).
Once it is sorted you can either insert elements by e.g. a binary search (divide list in 2 parts, if new element is in upper part divide it again etc.), or, more tricky, let the user of your template insert the element and offer just a method as "insertBeforeLastElement". The user can then iterate through the list (draw all materials) and will decide to where the new element belongs and just insert it.
There''s a lot of literature on this, it''s worth the digging since your game speed will strongly relate on those data management..
- thomas
a linked list is fine for fast insertions, but it doesnt say anything about how fast it finds its entries. This depends on
1) if and how you sort your list
2) how you find elements (linear search or whatever)
If insertions should be fast, you should try to sort your list.
On what your list is sorted depends on the usage (e.g. rendering materials -> minimize state changes, texture changes etc.).
Once it is sorted you can either insert elements by e.g. a binary search (divide list in 2 parts, if new element is in upper part divide it again etc.), or, more tricky, let the user of your template insert the element and offer just a method as "insertBeforeLastElement". The user can then iterate through the list (draw all materials) and will decide to where the new element belongs and just insert it.
There''s a lot of literature on this, it''s worth the digging since your game speed will strongly relate on those data management..
- thomas
- thomas
August 02, 2001 09:33 AM
quote:
Can template class members be virtual? Thanks!
i guess a better way to phrase this would be:
Can you derive classes from a template class? Any examples (just syntax... pseudo code would be fine)?
Perhaps this violates the need and use of a template...
"You call him Dr. Grip, doll!"
Edited by - the_grip on August 2, 2001 10:46:55 AM
"You call him Dr. Grip, doll!"
1,394
August 02, 2001 10:06 AM
Hello,
Well, I am using something similar, I am using the STL std::deque thought, not something I wrote, I thought iterating one by one to search for one item would be a pain, so what I did is that I use a Binary search tree, since I do need to iterate each object in the deque to see if it should be drawn or not, the deque is an easy way to do it, however if I want to find an object it might take too much time.
anyway what I do is to have the BSTree keep references to the objects, the object class has in itself an ID, so the tree node struct looks like this:
when I push a new object in the node I imediatly insert a reference to it to the tree (IE Node->Object = (void *) &deque[deque.sixe()-1]
. then when you search the tree you use Node->Object->GetId();
so I use a deque to store objects, and a Binary search tree of references to search for objects.
hope, this will at least give you an idea.
Well, I am using something similar, I am using the STL std::deque thought, not something I wrote, I thought iterating one by one to search for one item would be a pain, so what I did is that I use a Binary search tree, since I do need to iterate each object in the deque to see if it should be drawn or not, the deque is an easy way to do it, however if I want to find an object it might take too much time.
anyway what I do is to have the BSTree keep references to the objects, the object class has in itself an ID, so the tree node struct looks like this:
struct Node{ void *Object; Node *left; Node *right;} when I push a new object in the node I imediatly insert a reference to it to the tree (IE Node->Object = (void *) &deque[deque.sixe()-1]
. then when you search the tree you use Node->Object->GetId();so I use a deque to store objects, and a Binary search tree of references to search for objects.
hope, this will at least give you an idea.
122
August 02, 2001 10:35 AM
I don''t think so.
Templates are kind of inline functions; their methods are expanded like a macro by the compiler. But you can write a class implementing this template from which you can derive.
- thomas
Templates are kind of inline functions; their methods are expanded like a macro by the compiler. But you can write a class implementing this template from which you can derive.
- thomas
- thomas
August 02, 2001 07:28 PM
That''s a whole lot of code just for a linked list!
Why are you using void pointers? The whole point of templates is that you can get away from nastiness such as void pointers. And you don''t appear to actually use type ''T'' anywhere.
Apart from that, the code of your list isn''t really the issue. If you need to find things quickly, a list is not the best structure. You''re better going for some sort of sorted structure so you can perform some sort of logarithmic-time search on it.
Why are you using void pointers? The whole point of templates is that you can get away from nastiness such as void pointers. And you don''t appear to actually use type ''T'' anywhere.
Apart from that, the code of your list isn''t really the issue. If you need to find things quickly, a list is not the best structure. You''re better going for some sort of sorted structure so you can perform some sort of logarithmic-time search on it.
August 03, 2001 08:33 AM
Actually, the void* is outside of the template... it's only there in that one return value b/c of the data node structure (i can't seem to get the node code to work if i put the structure inside the template... that was initially what the T type was for).
i have some code that casts the void pointer to type T, but i didn't include it (rather just the void* return).
Additionally, i'm fairly new to this type of stuff
"You call him Dr. Grip, doll!"
Edited by - the_grip on August 3, 2001 9:36:18 AM
i have some code that casts the void pointer to type T, but i didn't include it (rather just the void* return).
Additionally, i'm fairly new to this type of stuff
"You call him Dr. Grip, doll!"
Edited by - the_grip on August 3, 2001 9:36:18 AM
"You call him Dr. Grip, doll!"
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
Recommended Tutorials
Advertisement