Archived

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

Linked list, STL, whathave you...

This topic is 4943 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

Hey all, I am new to coding in C++ but I have been doing it in C for ages. I am updating my sprite engine to use C++ from C and I ran into some trouble. Sprites are a structure and they are processed within a linked list like so. The game world has the following data: SpritePtr HeadSprite; SpritePtr TailSprite; Each sprite has the following data: SpritePtr NextSprite; SpritePtr PrevSprite; So, drawing them is simply a matter of itterating thrugh the list. You take the worlds HeadSprite, draw it, grab that sprites NextSprite, and keep itterating till you reach a NULL value. Now, C++ throws a wrench into my finely tuned C game engine Cuz now I wan''t to change sprites and the game world to classes as oposed to structures. Only problem is, how do you make a linked list with classes? Can you have a pointer to a class? Can it be done similarly to this? I have googled for this issue and come up with sketchy results at best. Many resources seem to point me in the direction of the STL linked list object. Quite frankly, I don''t understand it. It dosn''t seem to work in the same way I like to structure my Linked lists eaither. If someone could explain it to me, or perhapse explain how I can create a linked list in C++ I would be more than thankfull.

Share this post


Link to post
Share on other sites
You use std::list wich is a doubly linkedlist.
#include <list>
#include <iostream>

int main()
{
std::list<int> intList; // creates a linked list of int's

intList.push_back(45); // add 45 at the end

intList.push_back(23);
std::list<int>::iterator pos = intList.begin();
// print all elements in the list

for (; pos != intList.end(); ++pos)
{
std::cout << *pos << std::endl;
}
}
And yes you can have a pointer to a class.

[edited by - Eriond on May 30, 2004 7:33:25 PM]

[edited by - Eriond on May 30, 2004 7:34:24 PM]

Share this post


Link to post
Share on other sites
You can do it pretty much the exact same way if you like.

Classes are a type, so you can make a pointer to a class (instance) just as you would to a struct. In fact, C++ kept "structs", but they are syntactic sugar for classes (they default to public contents instead of private).

The STL provides a variety of container classes for you, one of which is a linked list. Having a big library is good; it lets you avoid rewriting silly stuff like linked lists all the time. The concept of a "container" is also important, as I''m getting to...

The STL linked list (std::list<type > is itself a class; it holds the equivalent of HeadSprite/TailSprite, and a bunch of other useful stuff. It is also templated (note: Standard *Template* Library), meaning that you can create a list to hold any particular type of object that you like. The compiler will generate a specific sort of list tailored to hold whatever object it is that you want.

(If memory serves, std::list is a double-linked list and std::slist is a singly-linked list.)

The other nice thing that gets provided by each STL container is iterator functionality. Conceptually, an iterator is an object that knows about some container; keeps track of a position in the container; and can be asked to provide the "next" element from the container. This lets you write algorithms that, for example, do something to each item in the container, without actually knowing what kind of container it is. You just take the iterator as input, and grab everything, one at a time.

Note "algorithms". Now we''re getting into more frightening territory, but the STL also provides a bunch of algorithms for you - and perhaps not in the sense you''re used to. The tricky part is that some of them require you to make your own classes which represent pieces of the algorithm. (Remember that classes are a little packaging-together of data and related code; in C you only had the option to put data in a little bundle. But now that they can mix freely, you can make mostly-code, or code-only bundles too.)

But once you''ve wrapped your head around that, you get access to really nice things like std::foreach. Pass in a container of whatever type (they all provide the needed iterators by themselves), and a special object that wraps around a function call, and voila, the function is called for you, using each item of the container in turn as a parameter. This is the stuff that the Lisp advocates have been raving about for decades, you know.

(By the way, I actually *hate* C++. But this kind of stuff is easy to praise, at least on a superficial level - especially when the alternative is the old-school C way of doing things. Only systems programmers should have to deal with that stuff these days; application programmers have much, much better things to do with their time. Of course, a lot of these things can be done much more nicely in even higher-level languages, like Java or Perl or Python or (whatever dialect of) Lisp (though it''s not for everyone), but there''s no reasoning with some people...)

Oh, you must be dying for some actual code by now. But I think I''d best let someone else fill that in because I''d probably make some subtle mistake

Share this post


Link to post
Share on other sites
If you want to keep your linked list as it is, you can, obviously. You can either make accessor functions to access the private pointers:
SpritePtr* getNextSprite(return this->NextSprite) 


or you can keep it as it is (in a struct) or make a class out of the struct and make the members public.

The only difference between a class and a struct in C++ is that the first defaults to private, and that the second defaults o public.

Share this post


Link to post
Share on other sites
A "class" isn''t a thing. A "class" is just a collection of data layout and functions. You use new(), or other construction methods, to create instances of classes, just like you use malloc() to allocate memory for structs.

In fact, in C++, a "class" is EXACTLY like a "struct" except the default protection is private, not public. Really. Wherever you see something like:


struct Foo {
int x;
char * y;
};


You could instead write:


class Foo {
public:
int x;
char * y;
};


Same thing going the other way: wherever you see a class, you can write it as a struct that makes the default access private.

Share this post


Link to post
Share on other sites
well thanks alot guys!

I understand the whole thing alot better.

Classes are just fancy structs then. I had my suspicions :D

I suppose this means a function can return a class instance, just as you can return a struct pointer etc.

I may port over my linked list functionality, but as Z described the STL may be more to my benifit.

you all helped me alot on this one, thanks a bundle.

Share this post


Link to post
Share on other sites
quote:
Original post by psyjax
Classes are just fancy structs then. I had my suspicions :D
Just to drive the point home, since some people have trouble with it: classes are structs. They are completely equivalent, except for the default access, which is pretty minor. Other than that, anything you can do with a class, you can do with a struct, and vice versa.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by ze_jackal
Just to drive the point home, since some people have trouble with it: classes <em>are</em> structs.
I can see how that could confuse someone coming from a C background and not knowing much C++, such as psyjax...

Share this post


Link to post
Share on other sites