Jump to content
  • Advertisement

Archived

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

m_grinder

Linked lists

This topic is 6733 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a class and want to create a linked list of class objects. I knew how to do this once but I guess I'm getting old and senile. m_grinder By the way, I'm using C++. Edited by - m_grinder on 3/7/00 2:23:08 AM

Share this post


Link to post
Share on other sites
Advertisement
STL - CList<>

Great little template class that I use for all linked list purposes, ''cause it does the trick.

Share this post


Link to post
Share on other sites
hmm.. Looked trugh the help and got completly lost. I tried a couple of different ideas but it didn''t seem to work out the way I planned.

Could someone please give me some sample code to get me started?

m_grinder

Share this post


Link to post
Share on other sites
Just a quick note, CList is decidedly NOT STL. That''s Microsoft''s class library. The STL list is just list<>

-Brian

Share this post


Link to post
Share on other sites
whoops, my bad!
#include
Shouldaveknownmswouldhavecomeupwithsomethingdifferent.

Anyway it still works, but it''s not "plug and play" as such. If the documentation doesn''t seem to make sense to you, perhaps you need to study templates a bit more.

Share this post


Link to post
Share on other sites
If you just want a linked list of class objects, STL might be overkill. Here''s an example of a linked list that uses class "Myclass".


#include "Myclass.h" // for Myclass implementation

class list_node {
public:
Myclass data; // data for this node
list_node* next; // next item in list
};

class List {
private:
list_node* head; // first item in list
int list_size; // number of items in the list
public:
list_node& Next(list_node*); // returns next item in list
list_node& First(); // returns first item in list
int Size(); // returns size of list
void Insert(Myclass*); // adds an item to the list
void Delete(list_node*); // removes an item from list
};


The function implementations are pretty standard for a linked list. You could use STL of course, but there''s a lot
of extra stuff provided that you may not need. =)

feel free to beat me up if this wasn''t helpful at all.


*oof*

Share this post


Link to post
Share on other sites
[pounding *oof*]

Why write your own class?

#include <list>
using namespace std;

typedef list<MyClass> MyList;

void main ()
{
MyList list;
MyClass obj;
obj.Init (); // or whatever
list.push_back (obj); // puts obj on end of list
list.push_back (obj2); // ditto
list.push_back (obj3);
list.pop_front (); // removes first object in list

list.front ().Print (); // calls Print on first element
list.back ().Print (); // calls Print on last element

for (MyList::iterator it = list.begin (); it != list.end (); it++)
{
it->Print (); // calls Print on each element, from first to last
}
}

STL. Learn it. Live it. Love it.



Edited by - Stoffel on 3/7/00 11:16:19 AM

Share this post


Link to post
Share on other sites
I have to agree with you, Stoffel. But more specifically:

Yes, STL list has lots of functionality you may never use. Who cares? It''s not like the linker can''t strip all of that code out for you. Besides, why risk writing your own list and screwing it up (or wasting time debugging it) when someone else has endured the agony for you -- and has also written everything to be about as fast as possible. I was going to say "I can''t figure out why people don''t like using STL, and want to write their own containers." Then I remembered something...

Jump back to 1995, a Computer Science II class with a naive freshman computer science student. STL is part of the curriculum, but I think the whole idea is stupid. Time and again, I can''t even get simple programs to work, and sometimes it IS the fault of the library. (It was 1995, after all.) But more often than not, some small error in my code ends up being the culprit. After many, many times of blaming STL (and even renaming it Satan''s Template Library), only to discover that it worked as it was supposed to, I concede that it does work pretty well. Wait a few years, use it heavily on several projects, and read the entire SGI documentation (or Austern''s book, if you prefer paper), and now I worship STL, and have devoted my graduate studies to generic programming. Moral of the story: Four years of undergradute brainwashing and indoctrination goes a long way. (:

Seriously, STL rocks. Templated, generic libraries are the next big thing, and they are already being applied, very successfully, to other problem domains. The performance far exceeds that of OO libraries (littered with virtual functions).

-Brian

Share this post


Link to post
Share on other sites
Two things to consider when using STL. STL compiles all of the code of the template for every class you make from it. This contributes greatly to code bloat. STL can be nice but why would you want your code size to become that huge.

STL is not somehting you can change. Any deviation from the standard generic algorithms in STL means that STL might not perform the way you would like it to.

Kressilac
Oh the other thing about STL is that when your customer calls about a bug and you locate it in STL, telling them that you''re waiting for Microsoft to update VC++ or worse for some standards body to update STL is not a valid excuse. If you wrote your own class you can fix the bug asap.

Share this post


Link to post
Share on other sites
This is from Paul Pedriana''s "High Performance Game Programming in C++" presentation at the 1998 GDC:

"You may ask, "Does making templated inlined classes cause code bloat?" If you have 200 classes, and you declare STL containers for each of them, does it cause 200 copies of the entire STL class definition to be created and linked in? Basically, no. Since the classes are implemented as inlined templates with no virtual functions or multiple inheritance, any functions you don''t call will never get used. The functions that do get used will be implemented inline. While this is certainly faster than implementing them as separate functions, code that gets called repeatedly effectively gets instantiated multiple times. However, STL classes are generally small classes whose most common operations can be implemented with just a few instructions. So in practice, while there is a slight size increase, practice has shown that it is not very much. A common reply of fans of basic C containers is that you can simply create a single C list struct that holds pointers to void* and thus you can store virtually anything in it. Well, you can do this same thing with an STL container as well, and get identical performance, so it is a non-issue."

You can check out his entire article at www.ccnet.com/~paulp/HPGP/HPGP.html.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!