Home grown or save your time?

Use the one in stl.

I don't use STL, but I don't write an entire class or template either. I just add simple linked-list capability to things that need it. It's about 5-10 lines each for add, remove and rearrange.

Quote:

Original post by Kris_A I don't use STL, but I don't write an entire class or template either. I just add simple linked-list capability to things that need it. It's about 5-10 lines each for add, remove and rearrange.

So, let's see... 5-10 lines each means 30 lines, add to this the traversal code (either 10 lines once and 10 lines for each traversal, or 60 lines once to implement an iterator and no additional work per traversal), the code to replace various standard library algorithms (copy, for_each) which represents quite a nice bit of code, this adds up to 500 lines. Now, writing, debugging, profiling and optimizing 500 lines of code to reach the same level as the STL ought to take you two days. If you want advanced functionality (and an optimized one at that) such as templated allocators, sorting, wrapping push_front and push_back iterators, add a couple of weeks.

If std::list provides what you need, use it. If you need something it doesn't provide, but can be built on top of it, then use it and build that thing on top of it. Only if you have needs so specific, precise and exotic that the standard implementation does not provide them at all, should you roll out your own implementation. Otherwise, you're just spending more time to get an often inferior result.

Quote:

this adds up to 500 lines. Now, writing, debugging, profiling and optimizing 500 lines of code to reach the same level as the STL ought to take you two days

Well, it doesn't. If I wanted to use STL then I would. If I wanted someone to tell me what to do, I would be asking a question not answering one. If Skute doesn't want to do it the same way, that's fine by me...

Quote:

Original post by Skute Hi, im wondering whether it will pay to write my own list template class, or to use the one in the stl? Im writing my EntityManager class, so need to keep a list of entities. Not sure whether to write my own list class or not....

Want to create a game? use the STL.
Have a deep craving to battle with pointers and do silly misstakes but learn how a linked list work? Write your own, then use the STL instead.

As for the intrusive approach mentioned earlier, simply don't to that you'll end up with a class that has severe personality problems and tries to make quite a lot more than one thing. (Oh, yeah there actually exist scenarios where it makes sense, bulk PC programming isn't one of them though.)

Quote:

Original post by Kris_A Well, it doesn't. If I wanted to use STL then I would. If I wanted someone to tell me what to do, I would be asking a question not answering one. If Skute doesn't want to do it the same way, that's fine by me...

Don't get defensive. You're just a bad software developer is all. You really shouldn't be dispensing advice, given the apparently poor quality of the software development decisions you make (at least in this case).

Quote:

Original post by Skute Hi, im wondering whether it will pay to write my own list template class, or to use the one in the stl?

If your goal is to learn to write a linked list - write one.
If your code happens to need a linked list, use the one in the library - it works, is standard, feature-reach and integrates with the rest of the library.
If you can demonstrate std::list is unsuitable to your needs - consider writing a custom allocator: that's often the customization people really need.
If an allocator still doesn't cut it - go back to writing your own, but try to conform to the STL's container interfaces and concepts, for familiarity (which, at that level, you would have) and integration purposes.

Quote:

Im writing my EntityManager class, so need to keep a list of entities. Not sure whether to write my own list class or not....

Then don't. You've got more important things to do, don't you?

Quote:

Well, it doesn't. If I wanted to use STL then I would. If I wanted someone to tell me what to do, I would be asking a question not answering one. If Skute doesn't want to do it the same way, that's fine by me...

You hadn't justified the validity of your approach, making your personal opinion of little help to Skute and leaving you wide open to a refutation. There is no need to take personally the fact that ToohrVyk explained the downsides of your solution, for Skute's benefit if not for yours.

Writing your own linked list class is not very hard to do. If you feel like doing it, go ahead and do it for the learning. Don't be afraid of making "silly mistakes", and don't be afraid of pointers. If you do it right, it will work and will most likely be as fast as the STL linked list in practice.

Its just not as practical as having a standard templated linked list class that is compatible with all the other functionalities of the STL.

Quote:

Original post by Jolle Use the one in stl.

x2

Quote:

Original post by Skute Hi, im wondering whether it will pay to write my own list template class, or to use the one in the stl?

Yes :-).

Using the one in the SC++L (previously named the STL) will pay by allowing you to get on to writing more interesting things, gain experience with an industry standard, and making your code more easily interoperate with other code using said list.

Writing your own will (well, may - depends on how much you allready know, and how many features you add) pay by being a learning experience.

If your question is if you should USE the one in the SC++L or use a hand written one, chances are you should use the first one.

If you want to write a list, then do it.

If you want to write your game, then do that.

Writing your own list class won't necessarily help you, nor will it necessarily hurt you. It can of course do those things, but I personally feel you'll be able to fully understand lists without ever writing one, just using one. But that is most definately an argument for another time. [smile]

@Kris_A: You had every right to get defensive as you were rudely insulted (heh, and then again for defending yourself).

However, what you suggested honestly isn't good practice. It probably works OK for small hobbyist projects, but it really would break down with huge professional projects.

Of course, if you're not doing those huge professional projects, no worries. [smile]

But Oluseyi is partially right. Your methods in this case really aren't any good. This isn't an insult, merely a notification.[smile]

IMHO, I'd say writing your own is a good learning experience, so if that's worth it and you're just programming to learn, write your own. But if you're looking for a solid well tested implementation, STL list is the way to go.

My thoughts on this:
It's very unlikely that you'll be able to write a more performant list than the std::list that ships with your compiler without sacrificing functionality.

Even if you can, your gains are going to be so tiny that it simply wouldn't be worth the effort.

Just go ahead and write your game. Once it's done, profile your code. If it turns out that std::list is your bottleneck, consider using a more appropriate container or allocator.

In short: No, writing your own linked list will not pay.

Extra:
If you feel the burning desire to write a container, then write something not already in the standard library.

Quote:

Original post by nilkn You had every right to get defensive as you were rudely insulted

I didn't realize I was being rude and insulting in my answer. If I was, then I apologize as it was not my intention in the first place. I still want to know what I said that was aimed at him in particular, and not at the things he said.

It was actually a "staff" member who insulted him.

Quote:

Original post by Oluseyi Quote: Original post by Kris_A Well, it doesn't. If I wanted to use STL then I would. If I wanted someone to tell me what to do, I would be asking a question not answering one. If Skute doesn't want to do it the same way, that's fine by me... Don't get defensive. You're just a bad software developer is all. You really shouldn't be dispensing advice, given the apparently poor quality of the software development decisions you make (at least in this case).

Not the best representation of a GDnet "staff" member.

FWIW if this is just a home project and a game for your own fun, then go ahead and write your own list module. It will help you understand pointers and lists and is always a tool teachers use to teach students about lists and pointers.

If you already know tons about pointers, lists, etc, then use std lists...unless of course you're writing on a C compiler. That's another story (but not a bad one IMO).

The simple answer is just use the STL. It will probably do everything you want, will be relatively simple to use, and perform similarly to any decent effort you put forth.

With that being said, I find it amusing that on this site that people get all worked up anytime anyone asks/suggest/proposes using a home-grown array(vector) or list class. C'mon people! These are THE simplest containers you can possibly create. Do any of you seriously think that the person who writes their own version feel any measurable impact in speed or debugging time from writing their own? What will it take? 1/2 a day to debug some corner cases they run into? Who cares?

Before you reply about all of the "power" that you'll miss out on if you roll your own, consider this. You don't normally NEED all of the options the STL provides you with. For example, someone mentioned not having the power to provide your own custom allocator, like the STL allows you to do. Guess what, if you're writing your own specific list class for a single thing in your game, you can choose allocate your memory however you want. Furthermore, you can do so much more easily. You don't have to write an "allocator". You don't have to worry about conforming to any standards. You don't have to worry about any of the gotchas of writing an allocator. You just inline it. Done. Again, I ask, who cares.

Don't get me wrong, the STL is nice. It does a lot of things. It does most of them well(I personally hate many of their naming conventions). And, in many cases, it makes much more sense to use it versus rolling your own. But to get all worked up over people rolling their own containers for simple things is just plain silly.

-John

Quote:

Original post by BeerNutts Not the best representation of a GDnet "staff" member.

Nothing wrong with being bluntly honest. I consider that a completely fine representation of a GDnet staff member. ToohrVyk posted an excellent weighing of the tradeoff involved in rewriting a linked list each time you want to use one compared to reusing the code found in std::list and the numerous algorithms of the STL. Then Kris_A wrote off this advice, "Well, it dosn't [add up to 500 lines to reach the level of functionality of the SC++L]", and then disparaged him for even posting such a comparison - a very valid and important one to weigh in mind, no less. Such a rude, counterproductive, and invalid response obviously deserves a reply or rebuttle. I honestly cannot think of a better such response than the blunt and honest one posted by Oluseyi. Dislike it all you care to, but it was merited and called for.

Quote:

FWIW if this is just a home project and a game for your own fun, then go ahead and write your own list module.

...if you want to (key words your missing there). See above post noting the potential learning experience by myself. If you'd rather work on getting your actual game mechanics working, ignore this exercise for the moment, use std::list, and get said game mechanics working. If you later decide you want to implement a list, you can do so at that time.

Edit: For the record, to provide merit to ToohrVyk's "2 days" figure, I'd like to point out this thread (warning: uses [ code ] tags for huge things belonging in [ source ] tags): Single Link List help......plz!....its killin me., which was posted quite recently:

Quote:

The original poster Yo dude ur 100% right ;)...thankz..lol, been stuck trying 2 do that [MM: remove an element from a singly linked list] 4 abour 7 hours.....lol....i have very little hair left.

7 hours on one of the more basic features of a linked list. Your mileage will vary. Although this poster may not have learned how to spell yet, he has learned how to remove an element from a singly linked list, and what's involved with that. Was it worth it? You'd have to ask him - it varies by individual. This also means that just because it was/wasn't for him dosn't mean it will/will not be for you.

[Edited by - MaulingMonkey on August 4, 2005 7:32:42 AM]

Quote:

Original post by Kris_A I don't use STL, but I don't write an entire class or template either. I just add simple linked-list capability to things that need it. It's about 5-10 lines each for add, remove and rearrange.

... You've heard of inheritance and composition, right?

As for the OP's question, I would only write my own list class if I needed a singly linked list (which STL doesn't provide (excluding non-standard extensions)), otherwise there usually isn't a reason to reinvent the list.

Quote:

Original post by Max_Payne Writing your own linked list class is not very hard to do. If you feel like doing it, go ahead and do it for the learning. Don't be afraid of making "silly mistakes", and don't be afraid of pointers. If you do it right, it will work and will most likely be as fast as the STL linked list in practice. Its just not as practical as having a standard templated linked list class that is compatible with all the other functionalities of the STL.

A very simple linked list IS easy to write, but the STL version has extra functionality. For instance you'll have to write code to remember where multiple iterators are in the list.

Professional game & non-game developers use STL. Unless you're interested in how they work don't bother, especially since it seems your need for a linked list is very simple.