STL Algorithms

[Zac Howland]

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 :sigh: 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

[Stephen Hewitt]

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;     // Fill 'coll' here...     std::for_each(coll.begin(), coll.end(), square_plus_one());       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; // Fill 'coll' here... 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

[Zac Howland]

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;
	// fill vector here
	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

[Stephen Hewitt]

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() {     // For notational convenience.     using namespace std;       vector<int> intVec;       // Fill vector.     for (int i=1; i<=10; ++i)     {        intVec.push_back(i);     }       // Transform the data.     transform(intVec.begin(), intVec.end(), intVec.begin(), square_plus_one<int> );       // Output the results.     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: // Changed function so we compile and made inline. inline int square_plus_one(int i) {     return (i * i + 1); }   // Added a functor version for comparison: struct functor_square_plus_one : std::unary_function<int, int> {     int operator()(int i) const     {        return (i * i + 1);     } };   // Altered transform: transform(intVec.begin(), intVec.end(), intVec.begin(), square_plus_one) ;   // Added call to functor ver

[Stephen Hewitt]

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

[Lost User]

he he. Java-stylee! One of my favourite helper templates comes straight from Bjorn Karlsson, author of "Beyond the C++ Standard Library: An Introduction to Boost":

template <typename T, typename O> void for_all(T& t, O o)
{
std::for_each(t.begin(), t.end(), o);
}

e.g.:

vector<int> vec;
...
for_all(vec, func);

I use this everywhere. I am also investigating boost::lambda, but it seems to get more complicated when using containers of smart pointers. Early days, but I am head over heels in love with Boost! :-O

[Stuart Dootson]

Robert Edward Caldecott wrote:

I am also investigating boost::lambda, but it seems to get more complicated when using containers of smart pointers

It does. If you're just using bind, then use boost::bind - it can cope with smart pointers (the boost ones at least!). Otherwise, I've defined macros to do bind the smart pointers get method, as below

#define VALUE(PTR) bind(&Symbols::ValuePtr::get, PTR)

   std::sort(allValues.begin(), allValues.end(), 
             bind(&Value::Address, VALUE(_1)) < bind(&Value::Address, VALUE(_2)));

I suspect Boost.Lambda won't change to cope with smart pointers (I don't know how active its main developer Jaako Jarvi is?). However, Joel de Guzman's developed somethng very similar for Boost.Spirit (it's called Phoenix) and I'm sure I've heard talk of that being merged with lambda...or something. Best place to ask is on the Boost developers list, I guess...

[Zac Howland]

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

[Zac Howland]

Stuart Dootson wrote:

I suspect Boost.Lambda won't change to cope with smart pointers (I don't know how active its main developer Jaako Jarvi is?). However, Joel de Guzman's developed somethng very similar for Boost.Spirit (it's called Phoenix) and I'm sure I've heard talk of that being merged with lambda...or something.

Several of the Boost libraries are being considered as additions to the next standard. Many of them are already in tr1 (an std extension until the next standard is finalized). I know the smart pointers are already in there (I make use of them fairly heavily), and I think lambda is, but I'm not sure ... something I'll have to double check.

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

[Stephen Hewitt]

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

[Zac Howland]

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

[Stephen Hewitt]

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

[Nemanja Trifunovic]

Zac Howland wrote:

Many of them are already in tr1 (an std extension until the next standard is finalized). I know the smart pointers are already in there (I make use of them fairly heavily), and I think lambda is, but I'm not sure

Nope, lambdas are going to be included as a language feature, not a library. See here[^]

Programming Blog utf8-cpp

[Zac Howland]

Nemanja Trifunovic wrote:

Nope, lambdas are going to be included as a language feature, not a library.

Looks like that is still a proposal. I'm not sure how I feel about that syntax ... the Boost lambda syntax is very easy to read, but that syntax seems to make it harder to read than writing a function or functor.

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

[Stuart Dootson]

Mmmm - shame they don't combine type inference and lambda - then you could get rid of the type annotations, like with Haskell - but I guess you can't, 'cause you could end up with polymorphic functions, like this in Haskell:

(\x y -> 2*x + y)

will have a type of

(Num a) => a -> a -> a

, or, in pseudo-C++, a (a x, a y) where a is some numeric type.

[Lost User]

BTW, I am using Boost 1.33.1 and don't seem to have BOOST_FOREACH - is this included with the 1.34 RC version?

[Stephen Hewitt]

No, it's not in 1.33.1. It's only one file however and can be downloaded from here[^]. As you can see it will be "shipped" with 1.34. I use 1.33 but added this file manually.

Steve

[Lost User]

Thanks Steve. Having problems using BOOST_FOREACH with a std::map though. For example, this won't compile:

std::map<int, int> m;
BOOST_FOREACH(std::pair<int, int> p, m)
{
}

This does work however:

std::map<int, int> m;
std::pair<int, int> p;
BOOST_FOREACH(p, m)
{
}

Is there a way to avoid declaring the pair before the FOREACH loop?

[Stephen Hewitt]

This is because BOOST_FOREACH is a macro. See here[^]. There are many ways to fix this including a typedef or an extra pair of brackets, but in this case the best is the following: typedef std::map<int, int> collection_t; collection_t m; BOOST_FOREACH(collection_t::value_type p, m) { } In general, with of without using BOOST_FOREACH, it's best to use a typedef to define an alias to the collection type, here collection_t. This allows us to change the type of collection used in one place. Once this is done we use the value_type typedef which is in every STL collection. I'd probably use a reference, const if possible, like this: typedef std::map<int, int> collection_t; collection_t m; BOOST_FOREACH(const collection_t::value_type &p, m) { } In both these examples the actual type name of the collection is only mentioned in one place and so can be easily changed. When for hash maps are added to STL, for example, this would mean that you can switch between a hash map or binary tree by changing only one line.

Steve

[Lost User]

Steve, thanks again for another informative post! The value_type typedef is something I shall be using a lot more of in future.