Getting Out of the Local Minima

I'm so lazy I'll work really hard to make my life easier.

In one way, I'm an optimist.  When somebody tells me that learning such-and-such will give me big productivity gains, I tend to buy into it.  I work to get over that hump to the promised land.  Sure, refactoring that code will take some time now, but in the long run it'll be worth it!  Sure, the tools are broken and annoying now, but once we've gotten them solid, we'll be working faster than ever before!  Sure, STL is hard to learn, but once you know it, it lets you do things much quicker than before!

A lot of the time I'm right.  And things do go faster once I get over that hump. Sometimes I'm wrong...for example, although STL's container templates helped my productivity shoot way up, STL's algorithm templates weren't much help.  Boy, did I want to believe in those algorithm classes.  Hell, I thought I'd never have to write code
again.  I'd just hook up algorithms.  For loops would be a thing of the past.  It took me dozens of failures, dozens of times saying, "This is a perfect opportunity for an STL algorithm!", dozens of times realizing the time I spent trying to get the STL algorithm to work was an order of magnitude more than it would have been if I just coded the
damn algorithm myself, that I finally gave up.

Is there any way to tell the fool's gold from the real gold?  The STL algorithm templates from the STL container templates?

Comments

[eh]

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.

[NeARAZ]

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.)...

[Ivan-Assen]

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.)

[vince]

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.

[vince]

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.

[eh]

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.