« Multi-Tasking Considered Helpful | Main | LOL »

August 17, 2005



So, you find it faster to code custom search functions, sort functions, replace_if functions, unique functions, etc., by hand, each time you use them? Interesting. Or, do you mean that you have coded your own reusable template functions that do the same thing? (And if so, how are they different from the ones in ?)

Why do you have so much trouble getting these "damn algorithms" to work? What causes these "dozens of failures"?

BTW I think you mean "algorithm functions", not algorithm classes.

As for telling the fool's gold from the real gold: one man's trash is another man's treasure.


Hm... strange. Myself, I find STL algorithm stuff ("it just works") more useful than the container stuff ("I need custom allocators!", "no hash containers in the standard?" etc.)...


STL algorithms become a bit more useful if you use boost::bind. (And presumably boost::lambda, but even bind is a bit too scary for most developers, let alone lambda.)


The algorithms I've found most useful are sort, nth_element, and the set stuff (set_difference, set_intersection, etc). The set stuff can be very useful for situations in tools where you're trying to propagate what changed in a list of objects, and minimize the computation done -- i.e. I want to find the set of objects added to a list, and the set of objects removed from the list, so I only have to process those objects.

Things like for_each and find_if seem useful at first but most of the time it'd be cleaner code to just write an iterator loop yourself. remove_if combined with erase can be very handy.

Stable_sort would be great but most implementations allocate memory under the hood, which can be really bad in game code (I wish, as well as having big-O performance garuantees, that the algorithms had memory-allocation garuantees).

I agree that even if I'm forced to use non-STL containers I'll often find myself reaching for the STL algorithms, though. You just need to get past the point of trying to use them as a hammer for every nail and just use them when you they really give you benefit.


I can't believe I forgot to mention lower_bound and upper_bound. I've replaced many a std::map/std::set with a sorted array and binary search due to the better memory usage pattern.


Yeah, vince makes some good observations...sometimes algorithm stuff is even more useful than STL containers since you can use it on fixed arrays or on custom containers you might have, if you have or are willing to make iterators that follow some STL standards for them.

I agree that for_each and find_if can be hard to use productively sometimes, even though they seem like the most "obvious" algorithms; for a long time they were really difficult because microsoft's mem_fun wouldn't work because of a lack of template support (I forget the specific issue). However even without mem_fun each is still useful if you tend to make more functions that are not class members; sometimes C++ developers think that because they are programming in C++ every function has to be a member function of a class, and if you get away from that, you can easily use things like for_each more often. Or you can use mem_fun, you should be able to say things like

for_each(objects.begin(), objects.end(), mem_fun(&Type::Draw));

which is fairly simple - simpler than writing a loop yourself, especially if the container is not a vector and you have to use iterators anyway.

It's true that you will still have some cases where making a functor for for_each or find_if will net complicate the code; but I have also found that often it's a good way of helping you to break up your code so that you tend to have shorter functions, which helps with readability and maintenance. Code tends to grow in complexity, and when it does I have often been glad that I already had some logical divisions like the ones imposed by using functors and for_each.

Dan Olson

Ah... now imagine how much more productive you'd be if your link times weren't so long because of template overuse.

STL containers are banned at my workplace. I found this a little odd at first, but I see the advantages every time I hear someone whining about their link times. And, when you go without them for a few months, it turns out that you don't really miss them at all. I've seen heavy use of templates in codebases before, and I'd trade any of their codebases for ours in a heartbeat.

Of course it depends on the kind of work you're doing. I did ACM contests in college and for those a good knowledge of STL containers and algorithms gave you a significant advantage. Similarly it would be sensible to use them in a toolchain when the situation suggested it.

I still find the occasional case where an STL container or algorithm would be handy, but given their potential for misuse, overuse, and obfuscation, I think that banning their use in engine and game code is a sensible option for many companies. Oddly enough, it's probably an option they'd never consider.

Oh, and like some other commenters, I find your conclusions about STL containers versus algorithms to be the exact opposite of what I would expect.

zachary j. gamedesigner

If you look closely, you may notice that Dan Olson isn't actually asian.

John Connors

I'm a bit scizoid about the whole issue here: I've used STL containers and found them useful, but not particularly well implemented for games (no control of run time allocation profiles), and found the algorithims useful once I'd absorbed a new set of idioms - looking for idioms is a good way to get a handle on getting over that hump.

However, what's gained in one area tends to be lost in another. It's more of a cost/benefit thing. The power of STL tends to come with a cost in the length of compile time: it's not a problem in small projects, but (with visual c/c++) at least, you can visibly see the difference in the compile time of hello_world.c and hello_world.cpp. When you have 100s of files in your project, the massive inlining all adds up and kills you.

Plus, there are few good source navigation/analaysis tools that can parse and refactor gnarly STL templates. C has problems, but it also has mature tools for tackling those problems such as DevPartner and Electric Fence, and a faster compile - edit - link cycle..It just takes discipline not to abuse things and code C++ in C..c.f http://www.w3.org/Library/User/Style/Cpp.html

However, right now, I'm an ultra-optimist. I'm learning Common Lisp to see what the rewards of a language that lets you completly re-define syntax are..which has it's own, completely intimidating set of costs.

Emmanuel Deloget

My own problem with the CSL algorithm are in fact problems with something I consider as a core issue of the language itself: the inability to use classes with no linkage in conjunction with templates. Due to this, you often need to implement your functors in either anonymous namespaces or elsewhere, while a local declaration (in the function that use them) would add a lot to readability.

However, I tend to find them very useful - more than the container library.

The comments to this entry are closed.

Jamie's Bragging Rights

  • Spider-Man 2
    The best superhero games of all time Game Informer
    Top five games of all time Yahtzee Croshaw
    Top five superhero games of all time MSNBC
    Top 100 PS2 games of all time Official Playstation 2 Magazine
    1001 Games You Must Play Before You Die Nomination for Excellence in Gameplay Engineering Academy of Interactive Arts & Sciences
  • Schizoid
    Penny Arcade PAX 10 Award
    Nominated for XBLA Best Original Game
    Nominated for XBLA Best Co-Op Game