Sign in to follow this  
Skute

Home grown or save your time?

Recommended Posts

Skute    134
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....

Share this post


Link to post
Share on other sites
Kris_A    182
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.

Share this post


Link to post
Share on other sites
ToohrVyk    1595
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.

Share this post


Link to post
Share on other sites
Kris_A    182
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...

Share this post


Link to post
Share on other sites
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.)

Share this post


Link to post
Share on other sites
Oluseyi    2103
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).

Share this post


Link to post
Share on other sites
Fruny    1658
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.

Share this post


Link to post
Share on other sites
Max_Payne    757
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.

Share this post


Link to post
Share on other sites
MaulingMonkey    1728
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.

Share this post


Link to post
Share on other sites
nilkn    960
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]

Share this post


Link to post
Share on other sites
perfectly_dark    253
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.

Share this post


Link to post
Share on other sites
Nitage    1107
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.

Share this post


Link to post
Share on other sites
ToohrVyk    1595
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.

Share this post


Link to post
Share on other sites
BeerNutts    4400
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).

Share this post


Link to post
Share on other sites
Teknofreek    331
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

Share this post


Link to post
Share on other sites
MaulingMonkey    1728
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]

Share this post


Link to post
Share on other sites
Roboguy    794
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.

Share this post


Link to post
Share on other sites
d000hg    1199
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.

Share this post


Link to post
Share on other sites
ToohrVyk    1595
Quote:
Original post by Roboguy
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.


I once had to reimplement a list when I required serializable list iterators. I spent a week and 1200 lines of code and documentation on it (not counting the unit tests). Not something I enjoy.

Also, at the place I'm working at right now, if I was to reimplement an object that is already implemented (dynamic arrays, hash tables, identifier maps, associative structures, network management, scripting...) in the huge company code library without having a very good reason for it, I would most probably be dragged out in a back alley and shot. Twice. In the groin. These are the kind of things that teach you what is counter-productive. [grin]

Share this post


Link to post
Share on other sites
BeerNutts    4400
Quote:
Original post by MaulingMonkey
Nothing wrong with being bluntly honest.


Mauling Monkey, I don't know you in real life, but lets say I did. And lets say you were over-weight, ugly, and socially inadept. If I were to then walk up to you and say, "Man, I get sick just looking at you, your so dang ugly!" or some other bluntly honest statement, I guess you'd just reply, "Nothing wrong with being bluntly honest."

Obviously, there is something wrong with being bluntly honest. Please, if your girlfriend (assuming you can get one) ever asks you, "Do I look fat in this?" don't say, "Yes...nothing wrong with being bluntly honest."

(side note: Isn't part of being on the GDnet forums to help other people? I don't think telling someone they're a bad software developer is much help. I consider it a bit harsh, ESPECIALLY from a "staff" member).

Share this post


Link to post
Share on other sites
Daniel Miller    218
It's very different telling someone something over the internet than telling them in person. But even if there was no difference, if someone is acting snobby or is giving false advice, it's fine to be "bluntly honest" and call them out; there is no need to pretty up your words.


edit: Your tone was rude to him in your post, why didn't you tone it down?

Share this post


Link to post
Share on other sites
Fruny    1658
Quote:
Original post by BeerNutts
(side note: Isn't part of being on the GDnet forums to help other people? I don't think telling someone they're a bad software developer is much help. I consider it a bit harsh, ESPECIALLY from a "staff" member).


Yes, helping other people is part of what being on the GDNet forums is about. But regardless of his original intent, Kris_A was not helpful. His advice was horrible, and his reaction to honest criticism was graceless. Making sure the advice you give is correct is fundamental in For Beginners - beginners generally can't recognize good from bad technical advice: that's why they're beginners. They aren't set in their ways, so you wouldn't want to "ruin" them by imposing on them your own unproductive idiosyncrasies.

I rank that on the same level as telling someone that "format C:" will fix their computer. Or maybe worse.

Telling someone to integrate linked-list code into each and every component that requires such functionality might be legitimate advice in some other language. In C++ it's just plain stupid. Creating your own linked-list class is useful for learning purposes. But when your goal is to actually complete a project, you really should use the standard list class.

Otherwise, why would the C++ committee and C++ library writers bother providing one?

Calling out Kris_A the way he was was entirely appropriate. Was it helpful? To those who read this thread, certainly. It's not just a question of having an abstract difference in opinion and shouldn't have been treated as one. Especially not in For Beginners.

If you can't give quality advice, we'd rather not have you give advice at all in here. I myself certainly rarely post in the Java, .NET or DirectX forums.

Share this post


Link to post
Share on other sites
Daniel Miller    218
Quote:
Saying Kris_A is a bad software developer does no good to him -- he's a beginner.


A beginner should not be giving unqualified advice, and certainly shouldn't snap at the criticism of that advice.

Umm... you do realize that he isn't the OP, right?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this