Jump to content
  • Advertisement
Sign in to follow this  
godmodder

Algorithms vs loops

This topic is 3584 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello, this is an issue I regularly bump into when coding larger projects: do I need to prefer (STL) algorithms or manual loops for very small code fragments? I understand that for medium-large loops, algorithms should almost always be preferred, because they're more efficient, more correct and better maintainable. (Effective STL seems to confirm this) However, in order to use for_each for example, I have to write appropriate functor objects for each task I want to perform. This really looks ugly and makes my code unreadable! Is there a way to avoid this bloat? BTW: I cannot use boost for this. I understand it's benefits, but for this I'm not allowed to use it. Jeroen

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by godmodder
Hello,

this is an issue I regularly bump into when coding larger projects: do I need to prefer (STL) algorithms or manual loops for very small code fragments?
I understand that for medium-large loops, algorithms should almost always be preferred, because they're more efficient, more correct and better maintainable. (Effective STL seems to confirm this)
However, in order to use for_each for example, I have to write appropriate functor objects for each task I want to perform. This really looks ugly and makes my code unreadable!
Is there a way to avoid this bloat?

BTW: I cannot use boost for this. I understand it's benefits, but for this I'm not allowed to use it.

Jeroen


Even with boost, std::for_each can sometimes be much uglier, longer, complicated and a PITA to maintain. Especially when you make up an 11-lines-long lambda expression to fit the last argument of for_each

Myself, I just use whichever one is shorter and makes more sense to me. There are times when one-line std::something solution is much nicer than a for loop typed out full; other times, I just stuff a simple three-line loop in there (including the brackets) and I'm done with it.

So it boils down to the usual: use your common sense.

Share this post


Link to post
Share on other sites
Sometimes one has no choice such as Intel's TBB.

I would go with STL as much as possible, with well documented classes to make the code more readable.

Share this post


Link to post
Share on other sites
When C++0x comes into common use, complete with lambdas, the std library algorithms should become much more useful. Until that time, they are a PITA for the majority of situations, so I would tend to advocate using them only where they yield a noticeable increase in readability or performance.

Share this post


Link to post
Share on other sites
I tend to use stl algortihms whenever it makes sense for the functor to be a seperate reuseable component. This is very often the case with predicates for find_if, for example. If you need to find an item in a collection in a certain way in one place, chances are sometime soon you'll need to find an item in that way somewhere else.

It could be argued that wrapping the loop and/or predicate in a simple function findFooByBar (or even more simply bool checkThisFoosBar) is more readable and equally reuseable.

Share this post


Link to post
Share on other sites
Quote:
Original post by godmodder
this is an issue I regularly bump into when coding larger projects: do I need to prefer (STL) algorithms or manual loops for very small code fragments?
I understand that for medium-large loops, algorithms should almost always be preferred, because they're more efficient, more correct and better maintainable. (Effective STL seems to confirm this)
However, in order to use for_each for example, I have to write appropriate functor objects for each task I want to perform. This really looks ugly and makes my code unreadable!
Is there a way to avoid this bloat?
std::for_each versus a simple for loop over all items isn't really about efficiency (both are O(n)), it's about correctness and clarity. It's easier to get a manually written loop wrong. Also, though it should be clearer in some cases, if it isn't clearer for you in a given instance, then simply don't use it there.

C++ standard library algorithms become very important when doing things like set intersection. To do that naievely involves writing nested loops, making the algorithm you implement O(m * n) whereas the standard library implementation is more like O(m + n). It's things like that which mean you really need to use the standard library algorithms to get it to work very well at all.

Share this post


Link to post
Share on other sites
Quote:
Original post by TheUnbeliever
Quote:
Is there a way to avoid this bloat?


BOOST_FOREACH


Quote:

BTW: I cannot use boost for this. I understand it's benefits, but for this I'm not allowed to use it.


!fail [grin]

While you're at it, Boost.Lambda would be an even better solution for in-place bloat-removal.

Share this post


Link to post
Share on other sites
Aside: using standard library algorithms (please don't say "STL") often results in encouraging refactorings (i.e. extracting the loop body into a function) that turn out to be useful (i.e. the function can be used other places in the code) and that you might otherwise never have thought of doing.

Also, consider that some tasks can be simplified by writing a smarter iterator and then proceeding to use the algorithms.

Share this post


Link to post
Share on other sites
Quote:
So it boils down to the usual: use your common sense.


I was kind of fearing that would be the answer ;)

Quote:
Aside: using standard library algorithms (please don't say "STL") often results in encouraging refactorings (i.e. extracting the loop body into a function) that turn out to be useful (i.e. the function can be used other places in the code) and that you might otherwise never have thought of doing.


I agree with you: there have been a number of cases where I could reuse the code in the body of the loop and algorithms worked very elegant. But most loops that I have to write involve 1-5 lines of code that are very specific and won't ever be reused. To mention a specific example: I have a list of rooms in a level editor and I need to add their ID's to a QT listwidget so the user can visually see it as a list. I thus need to iterate over every room and extract the ID. Then I add it to the listwidget. This amounts to 2 lines of code that aren't very reusable. Writing a functor makes the code very long and it separates the logic of the operation from the place where it get's used. What would you do in this kind of scenario?

Jeroen

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!