|
I continuously see people asking questions about code they have written that involves loops for things such as pulling in input, displaying output, transforming data in a collection, etc. All of which can be done using STL algorithms using much less code, but instead is done using (usually) complex code written by the programmer asking the question.
Why is it that so many people don't use the STL algorithms?
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
I'd say because they don't know they are there, or don't know how to use them.
Which is why I am often a voice in the wilderness when people ask MFC container questions - because the day will come that they wish their CArray was a vector, so they could just call random_shuffle.
Christian Graus - Microsoft MVP - C++
Metal Musings - Rex and my new metal blog
|
|
|
|
|
Hmmmm - given that STL algorithms are parameterised on iterator type, you probably can use them on a CArray by exploiting raw pointers to the data...like this, possibly?
CArray<int> blah;
std::random_shuffle(blah.GetData(), blah.GetData() + blah.GetSize());
Not that that's a good reason for using MFC containers - I don't think there is one, is there?
|
|
|
|
|
See, that amazes me. Mostly because so many of these questions are largely homework related. I know when I was in college working for my CS degree, we were actually marked off if we didn't use the STL algorithms for certain required classes. And this was less than a couple years after the standard was finalized.
The nice thing about many of the STL algorithms is their flexibility. You can still use CArray in most of them without too many problems (albeit, it doesn't look quite as pretty as using a STL container).
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
I can tell you why I don't use the algorithms too much
* The VC 6 STL docs blow so I haven't read them much and don't know what algorithm functions exist
* The STL naming scheme sucks so it's hard to figure out what some functions are for from just their name (and the docs aren't much help, see 1. I mean, seriously, WTF does "bind2nd" do??)
* Most of the time when I do use algorithms, it involves writing a special-case functor for just that usage, which is workable but just feels sloppy. I know about mem_fun_ref and the like, but I haven't taken the time to figure out how they work.
* Instead of fighting with the docs, I'll just write a for loop and be done with it
|
|
|
|
|
I agree with some but not all of your critisims.
Michael Dunn wrote: The VC 6 STL docs blow so I haven't read them much and don't know what algorithm functions exist
I think in general MS documentation sucks. But STL is part of C++ and you shouldn't look to MS to teach you C++; the same applies to STL.
Michael Dunn wrote: The STL naming scheme sucks so it's hard to figure out what some functions are for from just their name (and the docs aren't much help, see 1. I mean, seriously, WTF does "bind2nd" do??)
I'm not sure about this one. I admit STL has a price of admission but I've got nothing against the naming scheme. I mean, what does EnterCriticalSection do just from the name? Names should be descriptive but the names can be scoped by the general topic to which they apply - in this case synchronization primitives.
Michael Dunn wrote: Most of the time when I do use algorithms, it involves writing a special-case functor for just that usage, which is workable but just feels sloppy
I agree this can be a pain. Most times the work involved in writing a functor is not a problem as it can be reused multiple times. There are times however when you find yourself writing a one off functor which just complicates the code. The addition of Lambda functions to C++ would help here. The Boost.Lamda library is also interesting.
Michael Dunn wrote: Instead of fighting with the docs, I'll just write a for loop and be done with it
This only works for the simplest of the algoritms like copy or for_each. What about things such as binary_search and random_shuffle?
Steve
|
|
|
|
|
Michael Dunn wrote: The VC 6 STL docs blow
Along with VC6 STL and the VC6 compiler (where templates are concerned) - which is why I like VC2003 so much. I do 'raw' C++, command line tools rather than GUI tools, so any MFC failings aren't too important for me.
Michael Dunn wrote: t involves writing a special-case functor for just that usage
And that's why Boost.Lambda[^] is a library I use a lot...
Ok, OK, I admit it, I'm just an STL fanboy 
|
|
|
|
|
Michael Dunn wrote: The VC 6 STL docs blow so I haven't read them much and don't know what algorithm functions exist
See, this kind of comment is the kind that surprises me. My undergraduate textbook for my Data Structures and Algorithms class went over all that very well ... and Bjarne's book covers them fairly well, also. Seems to me those would be required reading for any C++ programmer (just like Petzold and Prosise are generally considered to be required reading for doing Windows programming in C++).
Michael Dunn wrote: The STL naming scheme sucks so it's hard to figure out what some functions are for from just their name (and the docs aren't much help, see 1. I mean, seriously, WTF does "bind2nd" do??)
It does exactly what it says it does: binds the second argument to what you pass in to bind2nd. Namely, when passing a binary function/functor into an algorithm that is expecting a unary function/functor, it allows you to bind the second value of the function call to something outside the algorithm. The syntax is a bit tough to get the hang of at first, but it makes sense once you get use to it.
Michael Dunn wrote: Most of the time when I do use algorithms, it involves writing a special-case functor for just that usage, which is workable but just feels sloppy. I know about mem_fun_ref and the like, but I haven't taken the time to figure out how they work.
There are some things where functors are useful (a general case Deleter functor, for example), but most of the time, I just write a simple function that isn't a member function to do whatever operation I was intending to do in the loop, and then use for_each or transform. It doesn't have to be a functor to be passed into an algorithm.
Michael Dunn wrote: Instead of fighting with the docs, I'll just write a for loop and be done with it
So, what you are saying is that you basically ignore principles of good software engineering practices with regard to code reuse because you are too lazy to learn to use the standard library's power?
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
Michael Dunn wrote: The VC 6 STL docs blow so I haven't read them much and don't know what algorithm functions exist
Perhaps. But I found them good enough to get going quite far with STL. I had used STL for some time before buying a book on it.
Kevin
|
|
|
|
|
This makes much more sense to me (but I'm old school):
vector<whatever> vec;
for (int i = 0; i < vec.size(); i++)
{
}
than
vector<whatever> vec;
vector<whatever>::iterator it;
for (it = vec.begin(); it != vec.end(); it++)
{
}
I don't think a lot of people think in terms of iterators, but I've learned to adapt.
- S
50 cups of coffee and you know it's on!
|
|
|
|
|
This is how I'd do it:
typedef std::vector<whatever> collection_t;
collection_t coll;
for (collection_t::iterator i=vec.begin(); i!=vec.end(); ++i)
{
}
Now you can change the type of the collection by altering one line. For example to use a list instead:
typedef std::list<whatever> collection_t;
This is an expression of the general design principle that one design decision should be expressed in only one place, if possible. In this case the choice of collection type only requires a change in one location and not scattered places throughout the code. STL and iterators don't make this happen automatically but they provide the abstractions to make this sort of thing possible.
In your first example you'd have to make changes in multiple places including inside the loop as lists don't support indexing.
Steve
|
|
|
|
|
Stephen Hewitt wrote: typedef std::vector<whatever> collection_t;
collection_t coll;
// Fill 'coll' here...
for (collection_t::iterator i=vec.begin(); i!=vec.end(); ++i)
{
// Do stuff here...
}
That still doesn't use STL's algorithms. Granted, it is reimplementing a for_each or a transform (depending on what you do in the loop), but the fact is it is still reimplementing it needlessly.
Stephen Hewitt wrote: This is an expression of the general design principle that one design decision should be expressed in only one place, if possible. In this case the choice of collection type only requires a change in one location and not scattered places throughout the code. STL and iterators don't make this happen automatically but they provide the abstractions to make this sort of thing possible.
Take a look at Scott Meyer's "Effective STL" for why this isn't really true.
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
Zac Howland wrote: That still doesn't use STL's algorithms. Granted, it is reimplementing a for_each or a transform (depending on what you do in the loop), but the fact is it is still reimplementing it needlessly.
No this loop doesn't use algorithms, just iterators. I could have used the for_each algorithm but this would have been, depending on what I'm doing inside the loop, an example of Michael Dunn's objection to STL: having to write a "one off" functor. If what you're doing in the loop is simple or unique it is often better to use a hand written loop instead of using for_each. This is the exact reason why suggestions to include lambda functions in C++ and libraries like Boost.Lambda were written. The point I was trying to get at was that using iterators in preference to direct indexing increases you ability to make alterations to the code.
For example is this really necessary or "good form":
template <typename T>
struct square_plus_one : std::unary_function<T, T>
{
T operator()(const T &v) const
{
return (v*v)+1;
}
};
int main(int argc, char* argv[])
{
typedef std::vector<int> collection_t;
collection_t coll;
std::for_each(coll.begin(), coll.end(), square_plus_one<collection_t::value_type>());
return 0;
}
I would argue the following is better and the price we pay (re-implementing the loop) is of no real consequence in this case:
typedef std::vector<int> collection_t;
collection_t coll;
for (collection_t::iterator i=vec.begin(); i!=vec.end(); ++i)
{
*i = ((*i)*(*1))+1;
}
Zac Howland wrote: Take a look at Scott Meyer's "Effective STL" for why this isn't really true.
What's not true? If I want to see if I get better performance or use less memory using a std::list I simply change one line - this is a fact. Not many people will think it's better to have to make multiple scattered changes and run the risk of introducing an error somewhere along the way. If you've got a specific point make it here as opposed to referring to a book but giving no clue to what to mean.
Steve
|
|
|
|
|
Stephen Hewitt wrote: Michael Dunn's objection to STL: having to write a "one off" functor.
You don't have to write a functor to use for_each, nor most of the other algorithms. Using your own example (and by the way, your for_each example actually does nothing but waste CPU cycles as written), the following works perfectly fine:
template<class T> T square_plus_one(const T& i)
{
return (i * i + 1);
}
int main()
{
vector<int> intVec;
transform(intVec.begin(), intVec.end(), intVec.begin(), square_plus_one<int> ) ;
return 0;
}
Granted, the Lamda library makes this even easier, and I fully support the use of it. However, for most common loops, this really isn't that complex.
Stephen Hewitt wrote: What's not true? If I want to see if I get better performance or use less memory using a std::list I simply change one line - this is a fact. Not many people will think it's better to have to make multiple scattered changes and run the risk of introducing an error somewhere along the way. If you've got a specific point make it here as opposed to referring to a book but giving no clue to what to mean.
What I meant is that the containers are not completely interchangible. For some simple things such as iterating through them, they are designed to be the same to make use of the algorithms. However, things like insertion, deletion, allocation of space, etc ... many of them are different (have different function names, don't have certain functions, etc). I directed you to the book because he gives a much better explanation that I could hope to offer on this forum (at least without plaugerizing the book).
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
Zac Howland wrote: You don't have to write a functor to use for_each, nor most of the other algorithms. Using your own example (and by the way, your for_each example actually does nothing but waste CPU cycles as written), the following works perfectly fine:
Firstly in your example you've written a "one off" function instead of a "one off" functor, the same objection applies in this case.
Secondly, your code doesn't seem to work. Try compiling this:
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
template <typename T>
T square_plus_one(const T& i)
{
return (i * i + 1);
}
int main()
{
using namespace std;
vector<int> intVec;
for (int i=1; i<=10; ++i)
{
intVec.push_back(i);
}
transform(intVec.begin(), intVec.end(), intVec.begin(), square_plus_one<int> );
copy(intVec.begin(), intVec.end(), ostream_iterator<int>(cout, " "));
cout << endl;
return 0;
}
I get the following error:
"CommandLine.obj : error LNK2001: unresolved external symbol "int __cdecl square_plus_one(int const &)" (?square_plus_one@@YAHABH@Z)"
I'm not sure if this is a compiler bug or what (MSVC6) but regardless it's a problem.
As to the “wasted cycles” I concede that I made a mistake in that the results of my calculations are never used (oops). Functors are no less efficient in general however, consider the following. I've altered the code as follows:
inline int square_plus_one(int i)
{
return (i * i + 1);
}
struct functor_square_plus_one : std::unary_function<int, int>
{
int operator()(int i) const
{
return (i * i + 1);
}
};
transform(intVec.begin(), intVec.end(), intVec.begin(), square_plus_one) ;
transform(intVec.begin(), intVec.end(), intVec.begin(), functor_square_plus_one()) ;
Below I show the machine code generated in a release build using MSVC6 for each call to 'transform':
004010DF mov ecx,dword ptr [esp+14h]
004010E3 mov edx,dword ptr [esp+18h]
004010E7 mov eax,ecx
004010E9 push edi
004010EA cmp eax,edx
004010EC mov esi,edx
004010EE je main+89h (00401109)
004010F0 mov edx,dword ptr [eax]
004010F2 add eax,4
004010F5 mov edi,edx
004010F7 add ecx,4
004010FA imul edi,edx
004010FD inc edi
004010FE cmp eax,esi
00401100 mov dword ptr [ecx-4],edi
00401103 jne main+70h (004010f0)
00401105 mov edx,dword ptr [esp+1Ch]
00401109
004010DF mov ecx,dword ptr [esp+14h]
004010E3 mov edx,dword ptr [esp+18h]
004010E7 mov eax,ecx
004010E9 push edi
004010EA cmp eax,edx
004010EC mov esi,edx
004010EE je main+89h (00401109)
004010F0 mov edx,dword ptr [eax]
004010F2 add eax,4
004010F5 mov edi,edx
004010F7 add ecx,4
004010FA imul edi,edx
004010FD inc edi
004010FE cmp eax,esi
00401100 mov dword ptr [ecx-4],edi
00401103 jne main+70h (004010f0)
00401105 mov edx,dword ptr [esp+1Ch]
00401109
NOTE: I actually compiled both methods with the other commented out to avoid any possibility of the compiler using using cached values from the one before. That's why both versions start at the same address.
There is no waste of "cycles" or space. The code is byte for byte identical. From what I hear from experts there are cases in which the functor version is actually more efficient as many compilers find it easier to inline a functor then code via a function pointer.
Zac Howland wrote: What I meant is that the containers are not completely interchangible
Of course not. That doesn't negate the general principle.
Steve
|
|
|
|
|
Stephen Hewitt wrote: Firstly in your example you've written a "one off" function instead of a "one off" functor, the same objection applies in this case.
Most people's main objection to writing "one off" functors is that they are several extra lines of code (e.g. declare the structure/class, declare the operator, etc.) A function doesn't really add that much to the lines of code, and generally makes the loop easier to read. In this example, it wouldn't matter much, since the loop is fairly easy to follow to begin with; however, I have seen some fairly complex loops in some code I worked on at my last job that simplified greatly using that technique.
Stephen Hewitt wrote: Secondly, your code doesn't seem to work. Try compiling this: ... I'm not sure if this is a compiler bug or what (MSVC6) but regardless it's a problem.
This is one of the areas where VC6 was not fully compliant with the standard. Passing function templates to the algorithms doesn't quite work with that compiler. I compiled the example (almost identical to what you wrote, by the way) using VS2003.
Stephen Hewitt wrote: As to the “wasted cycles” I concede that I made a mistake in that the results of my calculations are never used (oops). Functors are no less efficient in general however, consider the following. I've altered the code as follows:
What I was getting at was that the results were never used. I didn't mean to imply that functors are less efficient, because that isn't the case. Most people's main objection to them is the fact that they are creating a separate object that will never be reused. Writing a function for this makes things a bit less "overkill" (at least in my opinion).
Stephen Hewitt wrote: inline int square_plus_one(int i)
{
return (i * i + 1);
}
Just an FYI, when you pass the function to an algorithm, the compiler immediately ignores the inline request.
Stephen Hewitt wrote: From what I hear from experts there are cases in which the functor version is actually more efficient as many compilers find it easier to inline a functor then code via a function pointer.
I haven't heard that one, but I do know that when you pass a function via function pointer, the compiler cannot inline it (you can't pass the address of something that doesn't exist).
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
Zac Howland wrote: Just an FYI, when you pass the function to an algorithm, the compiler immediately ignores the inline request.
An inspection of the machine code I posted for both examples, the function and the functor, shows that in both cases the code was inlined. And this was with MSVC6, newer compilers may do even better.
Steve
|
|
|
|
|
If it does, great ... just know that the compiler documentation says otherwise:
MSDN[^]
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
Well it seems to be a mistake or an oversimplification. From the code I posted here[^] it can be seen that:
1. Both the function and functor versions produce exactly the same code.
2. Both versions have no call instructions.
3. The add and imul instructions which do the actual math can be seen in place.
I often find it enlightening to look at the code generated by the compiler. One surprise I had recently was when I was evaluating the Boost BOOST_FOREACH macro. Although when you look at the source there is a fair bit of code behind it, when I actually looked at the code generated in a release build it was actually smaller and more efficient then a hand written loop.
Steve
|
|
|
|
|
Steve Echols wrote: This makes much more sense to me (but I'm old school):
vector<whatever> vec;
for (int i = 0; i < vec.size(); i++)
{
}
than
vector<whatever> vec;
vector<whatever>::iterator it;
for (it = vec.begin(); it != vec.end(); it++)
{
}
See, but neither is "correct". Assume you are calling DoSomething(const whatever& w) for each iteration of the loop. The entire loop can be written as follows:
vector<whatever> vec;
for_each(vec.begin(), vec.end(), DoSomething);
Using iterators in place of the index doesn't buy you anything in terms of taking advantage of the pre-made algorithms STL gives you.
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
Zac Howland wrote: Why is it that so many people don't use the STL algorithms?
When I first started using STL for some time I just used the basic containers and looped over them. The VC++ 6 docs were good enough to get going with this kind of thing. Algorithms and function objects seemed rather mysterious. But once I found out what they were about then I started using them. The trigger for me was having to maintain code that used STL heavily. Then I was forced to understand it. I also bought Stroustup 3rd ed and Josuttis.
I didn't do CS at college. My background is in civil engineering. I guess there are probably some old school C/C++ devs who cannot see any reason to move beyond what they consider to be tried-and-tested. This basically means when you maintain their code you are typically met with a mixture of error-prone C and old-style C++.
Kevin
|
|
|
|
|
Kevin McFarlane wrote: I guess there are probably some old school C/C++ devs who cannot see any reason to move beyond what they consider to be tried-and-tested. This basically means when you maintain their code you are typically met with a mixture of error-prone C and old-style C++.
I can understand that (even though I disagree with the reasoning, "I've always done it this way ..." -- that isn't a reason in my opinion), but many of the questions I've seen are coming from either those that are still in college or those that are fresh out of college. I can almost understand seeing it from someone still in college if they are a first or second year CS or CPE major. But 3rd year+?
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
Zac Howland wrote: I can understand that (even though I disagree with the reasoning, "I've always done it this way ..." -- that isn't a reason in my opinion)
I fully agree. I was just reporting how these guys think.
Zac Howland wrote: many of the questions I've seen are coming from either those that are still in college or those that are fresh out of college.
Doesn't say much for the state of CS courses does it?
Kevin
|
|
|
|
|
Kevin McFarlane wrote: Doesn't say much for the state of CS courses does it?
No, actually, it scares me. These guys are making my degree less valuable 
Of course, then there are the colleges that stopped teaching C/C++ as the primary language for CS majors and switch over to Java. I have yet to meet one of them that understands basic (language-independent) design principles because Java doesn't force you to learn them.
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
Another interesting library is Boost.Foreach. See details here[^]
This enables you to write code like this:
foreach (int i, vecInts)
{
cout << i;
}
This assumes the following:
#include <boost/foreach.hpp>
#define foreach BOOST_FOREACH
Steve
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
