std::for_each and associate containers

[geoyar]

Hi,

If you pass the function MyFn(MyClass myClass) and std::vector<MyClass>::iteratos to std::for_each algoritm all is working just fine:

std::for_each(myVector.begin, ..., MyFn);
But for std::map you will get a compiler error, because now the value_type of the map is std::pair<Key, MyClass>. The error message is "Can't convert std::pair<Key, MyClass> to MyClass."

How make the std::map work with the std::map? Should I change the signature of MyFn to MyFn(std::pair<Key, MyClass> val)?

Thank you

[drkybelk]

create a wrapper (function of functor) for your function that takes a pair as parameter and use that instead

[geoyar]

Yes, I can do it.
But it seems to me that life is not so simple.
First, writing a wrapper I should explicitly assume that the container's iterator points to std::pair. And I do not like it.

Second, the functor I pass to std::for_each is using the member function of some class. This class is a second in the map::value_type. I am passing it to the functor via std::mem_fun, as described by Zhaohui Xing (Joey) in the article "How to use STL helper template function mem_fun in sophisticated algorithms" (www.codeproject.com, posted 4 Mar 2004). Mem_fun hides the 'this' parameter of the member function somewhere in mem_fun code. The functor looks like

CDblSumFunctor fSum(std::mem_fun<ResType, MyClass> (&MyClass::mfun), 0.0);

Because MyClass now is hiden in std::pair<Key, MyClass>,
operator () (std::pair<Key, MyClass>)can't use syntax
double res = fSum;

In my opinion two hacks are possible:
first, convert std::map to sequential container (e.g. list or vector), and enjoy std::for_each or
seconf: forget about for_each and write a regular loop.

I profiled version for_each for vector and a regular for loop for the same vector, and the regular loop on my computer was 15% faster in debug and release versions of my app.

By a way, I meet a problem with bind1st, bind2nd; they only accept functors with operator () (Param1, Param2) const.

[vijayan]

> writing a wrapper I should explicitly assume that the container's iterator points to std::pair. And I do not like it.

there is no reason not to like it. that the value_type of a map is std::pair< const Key, T > is guaranteed by the IS.

> Second, the functor I pass to std::for_each is using the member function of some class
> ...
> In my opinion two hacks are possible
> ...

There is a simpler way - just write an appropriate for_each algorithm of your own:

template < typename ITERATOR, typename FUNCTION > inline
void for_each_key( ITERATOR begin, ITERATOR end, FUNCTION fn )
{ for( ; begin != end ; ++begin ) fn( begin->first ) ; }

template < typename ITERATOR, typename FUNCTION > inline
void for_each_value( ITERATOR begin, ITERATOR end, FUNCTION fn )
{ for( ; begin != end ; ++begin ) fn( begin->second ) ; }

for example,

#include <map>
#include <cctype>
#include <functional>

struct A
{
  int i ;
  void foo() { i += 5 ; }
  int bar( int arg ) { return i += arg ; }
};

int main()
{
  std::map< char, A > m ;
  for_each_key( m.begin(), m.end(), &::toupper ) ;
  for_each_value( m.begin(), m.end(), std::mem_fun_ref( &A::foo ) ) ;
  for_each_value( m.begin(), m.end(),
                            std::bind2nd( std::mem_fun_ref( &A::bar ), 12345 ) ) ;
}

> I profiled version for_each for vector and a regular for loop for the same vector, and the regular loop on my computer
> was 15% faster in debug and release versions of my app.

this is not the case with the current versions of most compilers (IIRC, the microsoft compiler is the only exception to this); in the release build with appropriate switches, both would give equivalent performance. The hand written loop would be much faster with debug builds as inlining and other optimizations are disabled.

> I meet a problem with bind1st, bind2nd; they only accept functors with operator () (Param1, Param2) const.

This is by intent. as per the IS, both std::bind1st and std::bind2nd should accept const functors as the first argument. ie the function object itself should be immutable.

You might want to look at the much easier syntax for function objects and binders available in TR1. or in the interim use the function and bind libraries provided by boost.
http://www.boost.org/doc/libs/1_37_0...html#id2902673
http://www.boost.org/doc/libs/1_37_0...d.html#Purpose

[geoyar]

thank you for reply. I did it.
It works, but it is slower than the 'for' loop.
In Release version the 'for_each' for a map with _DEBUG_RANGE, _DEBUG_VECTOR, and _CHECKED_BASE_TYPE is 28% slower; without it (for (it..){it->second.MyFn}) it is 15% slower.
What are right compiler and linker options?

[vijayan]

What are right compiler and linker options?

I do not work (except occasionally) with the microsoft compiler. I seem to remember that this is a problem with the microsoft compiler - the compiler does not seem do aggressive inlining of functions. In the past, I have had some limited success by using these pragma directives in the code:

#pragma inline_depth(255)
#pragma inline_recursion(on)
#pragma auto_inline(on)

along with the /Ox (Full Optimization) compiler switch

see: http://msdn.microsoft.com/en-us/libr...8VS.71%29.aspx
http://msdn.microsoft.com/en-us/libr...8VS.71%29.aspx

[Danny]

The problem can also be attributed to the Standard Library implementation you're using. Older implementations were slower. Try to get the most updated release of that library.

[geoyar]

I am using VS2008 Standard and VC2008 C++ Express. I assume this is the last implemantation of C++ runtime lib before VS2010.
It seems Joe Coder should think twice before using std::algorithms on associative containers.
Look: you have to write your own versions of algorithms like for_each or transform; wrap your functions into functors, think about references to references, etc. Plain 'for' or 'while' loops look not so cool, but they work, and they are marginally faster on some compilers.
For the sequential containers std::algorithms are better if it is easy to provide them with the right functions.

[vijayan]

> I am using VS2008 Standard and VC2008 C++ Express.
> I assume this is the last implemantation of C++ runtime lib before VS2010.

Yes, if you are using the latest VS service pack, these are the current microsoft implementations.
STLPort http://www.stlport.org/product.html is reported to give a performance improvement over the STL implementation supplied by microsoft.

> For the sequential containers std::algorithms are better if it is easy to provide them with the right functions.

That is to be expected, isn't it? Algorithms work best on iterators which iterate over a sequence of values. The value_type in a std::map is a std::pair<>, so an operation on a member of the value_type needs extra work. Also, algorithms which modify the sequence do not make any sense for a std::map<>. Associative containers are designed to primarily support fast key-based insertions and look-up, in practice, iterating over key-data pairs is not a very common requirement.

> Plain 'for' or 'while' loops look not so cool, but they work,
> and they are marginally faster on some compilers.

I don't know, but to me there is nothing 'uncool' about 'for' or 'while' loops. I would say, use them if that is what meets your requirements best - a good programmer is, over and above everything else, a pragmatic programmer.

[drkybelk]

I don't know, but to me there is nothing 'uncool' about 'for' or 'while' loops. I would say, use them if that is what meets your requirements best - a good programmer is, over and above everything else, a pragmatic programmer.

I like that vijayan! People get over-political on certain issues (I just want to mention OO vs procedural programming, or "if" vs "switch", etc). In the end of the day you got to look at the problem at hand and use which ever means is best fit for the purpose. The worst thing that can happen is that you write "write-only-code" and you come back in six months time and you don't understand what you've written. C++ gives you a host of tools and is very flexible: you as a programmer should strive to learn what those tools are and, more importantly, how and when to use which of them.

[Danny]

I see nothing wrong with for and while loops, or switch blocks for that matter. Sometimes, these are the fastest, cleanest and easiest to teach constructs. I really am not fond of the "replace every for-loop with a for_each algorithm call". In fact, I still haven't figured out the difference between tranform() and for_each (in other words, one of the two is superfluous)