• Advertisement

Archived

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

Linked lists

This topic is 6559 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
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
quote:

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.



You couldn''t be more incorrect, even if you tried really hard. STL algorithms are extensible. The user supplies the definition of the algorithm. The very fact that you''d assume this tells me you haven''t looked at <algorithm> in any great detail.

It''s no skin off of my back if you don''t want to use STL. It just means the rest of us get to code circles around you.

Share this post


Link to post
Share on other sites
Why write my own class for a linked list?

Biggest reason:
I can write a linked list class implementation by myself faster than I could look up the specification of the STL List. I can practically do this with my eyes closed. Since it takes me more effort to use the STL List than write my own class, I usually don't bother.

Also, please realize I wasn't saying STL sucks. I just felt that the STL answer to m_grinder's original question may have confused him. (read his second post...)

When its new, the whole thing can be very confusing. If one does not understand how STL works, it can be difficult to implement it. Furthermore, if one wishes to learn how to write linked lists, list <>, won't show them.

Lastly, don't assume you can "Code circles" around someone simply because you're using STL and they are not. It is simply a nice convenience. Any and all coding skill comes from experience, not language features.

*oof*

Use STL. its rich in vitamins A and D!

Edited by - Oofnish on 3/7/00 2:56:22 PM

Share this post


Link to post
Share on other sites
Eek! See, while it''s admirable that you can code up a list quickly, I always thought that was a very academic exercise. STL is sooo easy to use (once you learn it), I find it hard to believe that it''s not the easiest route.

Furthermore, if you decide your architecture calls for a different kind of container than a list, it''s really easy to do with STL. This can be done with your own classes only with careful planning.

True, the learning curve on STL is steep. But after you get to the plateau, you have all this functionality to do whatever you need! All the containers and algorithms work in the same way--it''s a thing of beauty.

By the way, I didn''t assume that kressilac could be out-coded because he doesn''t use STL. I assumed so because both his points against using the library were incorrect AND he doesn''t use STL.

I hope everyone here understands that STL is part of the standard C++ library. If you don''t understand STL, you don''t understand the C++ library in its entirety. It''s like saying, "Wow, I really could use sprintf() here for text formatting, but I think I''ll write my own function instead because I don''t trust Microsoft''s implementation".

In a world where time-to-market is everything (even more than quality, and you all know that''s true nowadays), you have to be able to use all the tools at your disposal.

Share this post


Link to post
Share on other sites
You are correct in saying that I have barely used STL. I tried to do it once and ran into the same problem that Oofnish did. I can code it faster myself and get on to other aspects of my code. I just found the learning curve not worth my time.

I did not know that STL was extensible. I stand corrected on a point that I thought was told to me in better confidence. I can only assume that extending STL has drawbacks and is not the wonderful fix everything that it seems to be from the posts on this thread. Surely changing someone elses library has to involve planning for when that library gets updated. Could this be a cause of portability issues? I know that the Template specification under C++ hasn''t been stable for very long. Could the C++ spec change the implementation of STL in the near future(seems logical that it could)?

On the code bloat issue, I have not been the only one to state that openly here. Even the article posted in this thread admits to it as everything is inlined and therefore repeated multiple times in the code. The article attempts to dismiss the issue of code bloat but I am not sure that I believe this one yet. In cetrain cases under the usage of the proper STL programmer, I am sure code bloat can be minimized, but in the hands of average to novice programmers code bloat has to remain an issue just as performance of C++ over C is an issue to the novice C++ programmer.

Kressilac

Share this post


Link to post
Share on other sites
Part of the problem with STL and the c++ "Standard" is that its not yet globally implemented. In fact, to my knowledge, there aren''t any current C++ implementations that fully conform to the standard, especially in the area of templates (and by inference STL). There is a standard, but at this point its slightly difficult to work with due to these inconsistencies among compilers.
I use Visual C++ 6.0, which is notoriously poor with its implementation; many "standard" syntaxes simply don''t work. Yes, there are better implementations out there (gcc and c Builder I believe) but vc6 is what I have easy access to. Part of my concern, therefore, is learning how to use the "standard" libraries, and having them change in future versions.

I like the stuff. Its cool. but I _can_ write a linked list(double ended queue/tree/graph) faster than I could spend time learning a library that may change soon.




*oof*

Share this post


Link to post
Share on other sites
There are two separate issues that are being confused here. Yes, some complicated template features are not well implemented by certain compilers (MSVC), but that does not mean that any library which uses templates is therefore also broken and/or going to change. STL itself is written using a relatively small subset of the template features in C++, and is therefore very stable on every platform I have seen, including VC6. Theirs may not be the best, but it''s still pretty damn good. Even if MS does get their act together and fix their compiler to address issues like partial specialization, it really won''t matter, because the STL will continue to work as it always has. And if you''re truly worried about your version of STL, and being able to change it, you can use SGI''s. It''s not only one of the best, it''s also freely available, with all the source. (And, yes I have actually modified my copy of STL in the past, but not to fix bugs.)

Finally, I don''t think the learning curve is that difficult, if you approach learning it correctly. I would strongly suggest Matt Austern''s EXCELLENT book, which correctly teaches the set of concepts that comprise STL, then show how the different components are all models of those concepts. Once you grasp that, you realize that the components are VERY orthogonal, allowing you to mix and match containers, algorithms, and just about anything else with ease.

Also, the language IS standard now. STL isn''t going to change anytime soon. (Well, no sooner than some core part of C++ itself.)

Finally, extending the STL is actually very easy, since the whole premise of STL is that you only specify interfaces to things, and any suitable object can be plugged in. (This is also covered very well by Austern.)

- Want to change how things get sorted? Write a new comparison function, and give it to sort().
- Want to make a stack or queue, but use your own data structure? Write the data structure with a few basic member functions, and use the stack or queue adaptors.

Believe me... I used to hate STL more than anyone else on this board. I cursed it six ways from Sunday every time I had to use it. But after a little while, I realized that all of that stemmed from ignorance, and that it made my life so much easier. It''s worth climbing that learning curve... really.

-Brian

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Thanx guys, this line of argument sure help me in making my likedlist fully functional.
Anyway I managed to create my own linked list stuff and I''m a very happy boy. Hope this discussion continues long after I''m dead, from boredom.

Just kidding, your replys actually inspired me to start reading up on the whole STL bit.

m_grinder

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You SHOULD learn how to write your own linked list routines. It''s a pretty funamental computer science technique that a lot of different algorithims rely on you knowing. It''s good for giving your knowledge of pointers a work-out too...

STL''s fine & dandy but it''s not suitable for every situation as suggested above - what about portability?

Share this post


Link to post
Share on other sites
Technically the whole point of STL is portability. I''ve used it on both Windows and HP UNIX. That''s why they call it the Standard Template Library.

-fel

Share this post


Link to post
Share on other sites
Yeah, as was stated above, STL is part of the C++ standard library. Do you not use strcmp() because of portability concerns? Of course not. Reasonably well-written STL code compiles fine on many different platforms... as I do frequently.

-Brian

Share this post


Link to post
Share on other sites

  • Advertisement