Archived

This topic is now archived and is closed to further replies.

RolandofGilead

searching, sorting, TBS

Recommended Posts

This post is similar but does pose different questions than an earlier post, please read on. Especially the second question. Thanks. Yea! I finally understand how linked lists work! Now for the problem. I can make and search a linked list, no prob. I can even pre-sort stuff before putting it into the list and I have an idea on how to perform a binary search on the list. Does anyone have any other ideas on how to perform a very fast search on a linked list? Each node in my list is an actual unit on the battlefield, so if I sort my list what variable(s) inherent to strategy games would be ideal to use? I love the forums. Create. Edited by - RolandofGilead on August 5, 2001 6:36:06 PM

Share this post


Link to post
Share on other sites
Treating the game map as the XZ plane, it makes sense to sort units by their Z coordinates, so they can be drawn back-to-front if you''re making a 2d game, or front-to-back if you''re doing a 3D one so as to avoid too much overdraw.

An insertion sort would probably make sense in that situation.

Share this post


Link to post
Share on other sites
The words "sort" and "linked list" should generally not appear in the same sentence. Unless you''re doing something tricky, it''s very expensive to search a linked list for any value, regardless of whether it''s sorted or not.

If you''re STL-savvy, it sounds like you should be using a map. If not, you might want to look into hash tables (yes, I know about the non-standard hash_map, but I''ve never used it so I can''t speak to it).

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
If you''re really bent on using a linked list look into skip lists. They provide insert and search operations of order O(lgn). The problem with them is the added overhead they require for storing so many damn links. You should really be using the STL map though, which is implemented with red-black trees--a specific implementation of 2-3-4 trees. Red-black trees are a balanced (mostly) BSTs that give all of the benefits of skip lists without nearly as much overhead.

Share this post


Link to post
Share on other sites
.-If you have understood what binary search, you know that it needs random access. have another look at it.

.-Searching lists is not good. You should have a look ate the STL´s list search() method, it is specially designed for lists.

.-If a list becomes big, swicht to a tree-like data structure.

.-My last advice is to have a look to STL. It is really powerful.

What the hells!

Share this post


Link to post
Share on other sites