How much is STL used in game programming?

I can't tell you for sure how much stl is used in commercial games. I can tell you that id rolled their own container classes for Doom 3.

FWIT, though, my advice is to use stl where applicable. In most cases, it's highly unlikely that it will become a bottleneck.

It's often said that any experienced programmer should be able to write a linked list, array, stack, binary tree, or whatever. But the fact remains that there are a lot of subtleties to implementing these basic data structures efficiently and robustly. Not to mention that programming and testing such a library yourself could take tens (or even hundreds) of hours.

The stl was designed for efficiency and is extremely robust due to its prevalent use. (There's an article in GPG 1 that addresses some of the issues with using stl in games that might interest you.)

One last thing. If your goal is to be a professional (non-game) programmer or software developer, writing these classes yourself would probably be a good exercise. But if your goal is to complete a game successfully, using the stl will save you countless hours and many debugging headaches.

All IMHO.

If you want the best(fastest and smallest), definately go with custom structures. Use of custom structures slightly decreases reusability because it adds another dependancy. It also slightly decreases readability to other programmers because they have to learn your library. However, this shouldn't be a big deal if you use standard sort of names like push_back, remove, etc. The main disadvantage of using your own structures is of course the time it takes to write them and debug them. In my project, I felt that the gain of writing my own justified the cost, but you may not. Weigh these advantages and disadvantages and see what's best for you.

I should also add that should you choose to use stl, there are steps you can take to maximize its efficiency (such as choosing the most appropriate data structures, reserving memory in advance, supplying a custom allocator, using appropriate stl algorithms, etc.). Developing a good understanding of the stl will help you to use it in the most efficient way possible.

Quote:

Original post by gcsaba2 Since games have to be optimized as fast as they can be, I was wondering if STL structures work at the required speed, or do experienced programmers use their own lists, hash tables etc?

So long as you know how to use them you'll do fine.

Quote:

I'm only at the planning phase of my game, and I need to decide whether I should use char* or string, my own list or STL's etc. What do you recomment?

Go with the STL. If at some later point you realize it's a bottleneck, you can always swap it with your own implementation.

Quote:

Btw. is there a circular list in STL where I can just go to the next item forever, or do I have to simulate it with the regular list, like if (item == list.end()) item = list.begin(); ?

There isn't. But writing an iterator adaptor to do it shouldn't be too difficult (and it'd work with any container).

I was also suspicious of STL at first, but now I'm not. I still haven't run into any situation where I have regretted that I've used them.

Ouch, I got critisized by an AP :(
If you're too afraid to show yourself, then STFU.

I'm not sure what you mean by "better" but if you mean more optmized, then yes, I *can* write them, easily. STL uses the right algorithms, but the implementation isn't exactly optimized for speed in case you haven't noticed.

Quote:

Original post by Melekor the implementation isn't exactly optimized for speed in case you haven't noticed.

Which specific implementation are you talking about?
Can you give more details as to where exactly the performance bottlenecks are and what can be done to improve the library?

We all stand to learn something from anything you might tell us, so please do speak up.

Quote:

Original post by Melekor but the implementation isn't exactly optimized for speed in case you haven't noticed.

On modern & good implementations of STL algorithms, techniques such as type traits are used that detect the type at compile-time then do a dispatch on type (at compile-time) to the most optimized method to perform the operation depending on the type, for example std::copy when used with POD-types can select to use memcpy at compile time this all inlined out too usually done on nearly all modern vendors.

@ALL:

In general STL containers aswell as algorithms are implementated with alot of very advance C++ techniques & optimizations some of which are described in the book "Modern C++ Design: Generic Programming and Design Patterns Applied" some of which are not described there e.g. EBO, EDO, EMO etc.

If a compiler vendor implements the standard c++ library them-selfs they already know about all of these, they know or should know the C++ standard like the back of there hand and they certainly know there own compiler operates inside-out so they can take advantage of that.

So i have to ask how in the hell are going to compete with that? (answer is very diffcult if the implementation is rock solid) if your concerned with compiler's implementation look into the headers, if you find problems or see something not wright report to them they should sort it out.

Don't forget you can customise STL to certain degree so your not completely restricted, you can provide custom allocator types to STL containers, your allowed to do template specializations for your own types etc.

[Edited by - snk_kid on February 10, 2005 7:21:00 PM]

On second thought, maybe I should have posted anonymously too; Looks like anyone who ever says anything negative about STL gets bashed + rated down.

STL is about making life easier for the programmer. It's higher level, more abstract and generic. It's great because it's standard and it saves you a lot of work reinveting the wheel. I'm not disputing those things. What I am saying is that if you want the *fastest* data structures, you get them by tailoring them specifically to their use and working at a lower level of abstraction. I don't think you can really argue with this, it's quite a general concept in computer programming.

really depends on the complexity of your game, SDL means less coding and the speed is a little slower but usally not a big deal, howerver when you get into serius sprite magment you hit a point where you really need something more customized to your needs

Quote:

Original post by Melekor On second thought, maybe I should have posted anonymously too; Looks like anyone who ever says anything negative about STL gets bashed + rated down.

I'm not bashing anybody - I'm genuinely interested in any actual insight you are willing to share with us.

Quote:

What I am saying is that if you want the *fastest* data structures, you get them by tailoring them specifically to their use and working at a lower level of abstraction.

What data structures do you have in mind. I'll happily grant you that things like winged-edge data structures have nothing to do in a library of generic data structures. Yet, even in a game, things like that do not make up the bulk of your code.
So it ain't really a STL vs. custom data structures dichotomy - rather, which custom data structures commonly show up in game programming that aren't already provided by the STL.

By all means, do share your experience, instead of being so negative.

Quote:

Original post by jyk I can't tell you for sure how much stl is used in commercial games. I can tell you that id rolled their own container classes for Doom 3.

Theres probably a good reason for that and probably related to compiler tech around at the time of writing the code (i'm 99% sure it was started when VC6 was about) and less todo with the performance issues.

Ofcourse, I could be wrong, they might well have benchmarked things and in their case found the STL to be too heavy.

I'm not the authority on the matter, but if it means anything, i've never had a time where i regretted using STL.

If you are not sure of the speed of STL, i dare anyone to do this: make your own container and make the equivilent STL container, add 100,000 elements, and race 'em.

Quote:

Original post by Fruny By all means, do share your experience, instead of being so negative.

For example, some code I've been working with uses a lot of list operations. Because my list is not so generic(it doesn't have to work with every data type) I required that it can only use classes with a prev and next member, which lets nodes remove themselves instead of having to search the whole list before removal(like std::list does). If I was being negative, I appologize, but getting rated down will do that to a person.

Quote:

Original post by leiavoia I'm not the authority on the matter, but if it means anything, i've never had a time where i regretted using STL. If you are not sure of the speed of STL, i dare anyone to do this: make your own container and make the equivilent STL container, add 100,000 elements, and race 'em.

Agreed! I know that STL is saving me lots for my Audio Library. I know I will have to do something different when it comes time to cross platform it, but maybe I can use STLPort or something.

- Drew

Quote:

Original post by Melekor I required that it can only use classes with a prev and next member, which lets nodes remove themselves instead of having to search the whole list before removal(like std::list does). If I was being negative, I appologize, but getting rated down will do that to a person.

std::list does not require the entire list to be searched in order to remove an element. Removal is guaranteed to be performed in constant time given that you have an iterator to your object.

Quote:

Original post by _the_phantom_ Quote: Original post by jyk I can't tell you for sure how much stl is used in commercial games. I can tell you that id rolled their own container classes for Doom 3. Theres probably a good reason for that and probably related to compiler tech around at the time of writing the code (i'm 99% sure it was started when VC6 was about) and less todo with the performance issues.

i have doom 3 sdk 2, the project is in VC++ 7.0, i'm sure it has to do with more of portability than anything else because each implementation of STL will be slightly different on different compiler vendors that can be abit unsettling.

I've looked into ID's container library and in terms of C++ its pretty mediocre and use of templates is very minimal, no separation of de/allocation de/construction that the STL allocator concept do an important thing to do (although they have custom memory managers). Compared to some of the implementations of STL i've seen its nothing.

Quote:

Original post by _the_phantom_ Ofcourse, I could be wrong, they might well have benchmarked things and in their case found the STL to be too heavy.

Maybe i should do some profiling over the weekend and post some results if i'm not bussy [smile].

Quote:

Original post by Polymorphic OOP std::list does not require the entire list to be searched in order to remove an element. Removal is guaranteed to be performed in constant time given that you have an iterator to your object.

Hm, I must have missed something, what function does that? As far as I can see in the Docs there is only one overload of the list::remove function and it takes a const T&, not an iterator.

Quote:

Original post by Melekor For example, some code I've been working with uses a lot of list operations. Because my list is not so generic(it doesn't have to work with every data type) I required that it can only use classes with a prev and next member, which lets nodes remove themselves instead of having to search the whole list before removal(like std::list does).

OK. So the assumption is that an object can only belong to one list at a time. In such a case, my approach would probably be to stick a list iterator in the element instead of rewriting the whole list class itself. But I can see where you're coming from.

Quote:

If I was being negative, I appologize, but getting rated down will do that to a person.

I just don't like it when people "cry XYZ sucks" - which doesn't help us, rather than telling us "doing FOO with BAR will give you better results than a plain XYZ" - which takes longer to type, but actually teaches us something. Aren't those forums intended for us to share experiences?