Sign in to follow this  
Gink

Useful STL algorithms?

Recommended Posts

I was wondering what are the most useful algorithms in the STL? It seems that alot of algorithms are slower than just coding it manually (for_each,transform, etc), and the book im reading doesnt say why I would want to use these algorithms over manually coding so i'm not sure what they are part of the STL for. I thought the STL was optimized to be fast / effecient? Also, is it good coding practice to copy output from containers to an ostream iterator and input to an istream iterator? They do seem nicer than manually doing it but doesn't including all those header files cause program bloat / should it be avoided?

Share this post


Link to post
Share on other sites
for_each can prevent some subtles bugs, and it forces you to factor the code into sub-functions. Same with using copy & the input/output iterators.

sort, lower_bound, etc... produce very efficent run-time code, it's not that they are necessarily easier to code, but they should be. Sorting can get quite complicated, and it's easy to code an off-by-one error with lower_bound.

And you don't have to use just the standard algorithms, you can write your own too. I have a write_csv "algorithm" that dumps comma-seperated-values to a ostream, and properly handles the first and last item.

If you start writing very generic code those algorithms can come in handy, since writing your own generic version would be tedious at best.

Share this post


Link to post
Share on other sites
What do you mean forces to factor the code into sub functions? heres how I was using copy

copy(vec.begin(),vec.end(),ostream_iterator<type>(cout,"\n"))
Is that better than using for_each with a print functor?

How useful is transform? I wanted to double each value in a vector(i tried this as a simple example). Anyway, I used transform and it was slower, and I guess its expected. When doing something like that would it be better to use for_each and send a reference to the vector? Would that be the fastest way to do something like doubling the value of everything in a vector or is there some other way?

Share this post


Link to post
Share on other sites
Quote:
Original post by Gink
the book im reading doesnt say why I would want to use these algorithms over manually coding so i'm not sure what they are part of the STL for.


The reasons why you should prefer using the generic algorithms over explicit loop code (where possible):


  • Some algorithms can take advantage of iterator categories and the type contained to use a much more efficent method (at compile time) than the generic version, usually something you would have never thought of.

    For example most implementations of std::copy when given a random accessible iterators and the type contained is a POD-type it will dispatch (at compile-time) to use memmove (not memcpy, because the input and output ranges are permitted to overlap).

    if it is random accessible iterator but the type contained is a NON POD-type then it will dispatch (at compile time) to use a more efficent method of iteration which is candidate for compiler optimizations such as loop unrolling. The "itr != end" idiom makes it almost impossible to be unrolled.

    if it is none of these then it will dispatch to use the generic copy. These things you would never have thought about is taken care of for you and its still efficient as template meta-programming techniques are used to not compenstate efficiency, it cost nothing.

  • They can make your code less prone to bugs, explicit loops can be tedious and error-prone.

  • They can make code clear & concise (with some help with boost libraries it can make it more so)



Quote:
Original post by Gink
I thought the STL was optimized to be fast / effecient?


They are implementated as efficienctly as possiable as i described above, prefer specialized algorithms over overly general algorithms such as for_each as those are the ones most likely to to be more optimal for the operation.

Quote:
Original post by Gink
Also, is it good coding practice to copy output from containers to an ostream iterator and input to an istream iterator?


As far as i'm aware there is nothing that says so however logic should tell you that its a good idea, there are somethings you just can't do without a stream iterator, for example:


typedef std::istream_iterator<foo> isfoo_itr;

std::vector<foo> v((isfoo_itr(in_stream)), isfoo_itr());


Quote:
Original post by Gink
They do seem nicer than manually doing it but doesn't including all those header files cause program bloat / should it be avoided?


It depends on the compiler and platform, there ways to reduce the size of a program for those that do produce bloat, for example MinGW can bloat ridiculiously but if you go to there site they have info to tell you how to reduce it. In anycase do you really care for a slightly larger program over the functionality your given? i would say don't avoid it just because of that.

Quote:
Original post by Gink
copy(vec.begin(),vec.end(),ostream_iterator<type>(cout,"\n"))
Is that better than using for_each with a print functor?


Only because it saves you from writing the functor, if you use boost lambda library you can even get rid of having to write one-off functors/functions:


for_each(a.begin(), a.end(), std::cout << _1 << '\n');



Quote:
Original post by Gink
How useful is transform? I wanted to double each value in a vector(i tried this as a simple example). Anyway, I used transform and it was slower, and I guess its expected. When doing something like that would it be better to use for_each and send a reference to the vector? Would that be the fastest way to do something like doubling the value of everything in a vector or is there some other way?


How did you do it?, i'll assume something like so:


#include <algorithm> // transform
#include <functional> // multiplies
#include <vector>

//....
std::vector<double> a;
//.....
std::transform(a.begin(), a.end(), a.begin(),
a.begin(), std::multiplies<double>());


[Edited by - snk_kid on June 24, 2005 5:17:28 AM]

Share this post


Link to post
Share on other sites
In case you don't know, performance of STL mainly depends on compiler. For example, on GCC3 cout is slower than printf, but on GCC4 speed of both is the same (I tested it).

Share this post


Link to post
Share on other sites
Yeah, the standard containers can be slow if you don't use a decent optimising compiler.

That's no reason not to use them though - the VC2003 optimising compiler is free.

Share this post


Link to post
Share on other sites
Yeah I doubled each value like that
transform(a.begin(), a.end(), a.begin(),bind2nd(multiplies<double>(),2));

It was 2-3 seconds slower than a loop each run where I used 2(i think) million elements, probably because of all the method calls.

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