STL for_each with multiple return values and/or virtual base class functor

I trying to conv开发者_如何学JAVAert some loops in my code to use the for_each functionality of the STL. Currently, I calculate and accumulate two separate values over the same set of data, requiring me to loop over the data twice. In the interest of speed, I want to loop once and accumulate both values. Using for_each was suggested as it apparently can be worked into a multithreaded or multiprocessor implementation fairly easily (I haven't learned how to do that yet.)

Creating a function that only loops over the data once and calculates both values is easy, but I need to return both. To use with for_each, I need to return both calculated values at each iteration so STL can sum them. From my understanding, this isn't possible as for_each expects a single value returned.

The goal with using for_each, besides cleaner code (arguably?) is to eventually move to a multithreaded or multiprocessor implementation so that the loop over the data can be done in parallel so things run faster.

It was suggested to me that I look at using a functor instead of a function. However, that raises two issues.

1. How will using a functor instead allow the return accumulation of two values?
2. I have two methods of applying this algorithm. The current code has a virtual base class and then two classes that inherit and implement the actual working code. I can't figure out how to have a "virtual functor" so that each method class can implement its own version.

Thanks!

Here is an example of using a functor to perform two accumulations in parallel.

struct MyFunctor
{
    // Initialise accumulators to zero
    MyFunctor() : acc_A(0), acc_B(0) {}

    // for_each calls operator() for each container element
    void operator() (const T &x)
    {
        acc_A += x.foo();
        acc_B += x.bar();
    }

    int acc_A;
    int acc_B;
};


// Invoke for_each, and capture the result
MyFunctor func = std::for_each(container.begin(), container.end(), MyFunctor());

[Note that you could also consider using std::accumulate(), with an appropriate overload for operator+.]

As for virtual functors, you cannot do these directly, as STL functions take functors by value, not by reference (so you'd get a slicing problem). You'd need to implement a sort of "proxy" functor that in turn contains a reference to your virtual functor.^* Along the lines of:

struct AbstractFunctor
{
    virtual void operator() (const T &x) = 0;
};

struct MyFunctor : AbstractFunctor
{
    virtual void operator() (const T &x) { ... }
};

struct Proxy
{
    Proxy(AbstractFunctor &f) : f(f) {}
    void operator() (const T &x) { f(x); }
    AbstractFunctor &f;
};

MyFunctor func;
std::for_each(container.begin(), container.end(), Proxy(func));

_{* Scott Meyers gives a good example of this technique in Item 38 of his excellent Effective STL.}

Three (main) approaches

Ok, I ended up doing three (main) implementations (with minor variations). I did a simple benchmark to see whether there were any efficiency differenes. Check the benchmarks section at the bottom

1. std::for_each with c++0x lambda

Taking some c++0x shortcuts: see http://ideone.com/TvJZd

#include <vector>
#include <algorithm>
#include <iostream>

int main()
{
    std::vector<int> a = { 1,2,3,4,5,6,7 };

    int sum=0, product=1;

    std::for_each(a.begin(), a.end(), [&] (int i) { sum+=i; product*=i; });

    std::cout << "sum: " << sum << ", product: " << product << std::endl;

    return 0;
}

Prints

sum: 28, product: 5040

As mentioned by others, you'd normally prefer a normal loop:

for (int i: a)
{ sum+=i; product*=i; }

Which is both

• shorter,
• more legible,
• less unexpected (ref capturing) and
• likely more optimizable by the compiler

Also, very close in non-c++11/0x:

for (std::vector<int>::const_iterator it=a.begin(); it!=a.end(); ++it)
{ sum+=*it; product*=*it; }

2. std::accumulate with handwritten accumulator object

Added one based on std::accumulate: see http://ideone.com/gfi2C

struct accu_t
{
    int sum, product;
    static accu_t& handle(accu_t& a, int i)
    {
        a.sum+=i;
        a.product*=i;
        return a;
    }
} accum = { 0, 1 };

accum = std::accumulate(a.begin(), a.end(), accum, &accu_t::handle);

3. std::accumulate with std::tuple

Ok I couldn't resist. Here is one with accumulate but operating on a std::tuple (removing the need for the functor type): see http://ideone.com/zHbUh

template <typename Tuple, typename T>
    Tuple handle(Tuple t, T v)
{
    std::get<0>(t) += v;
    std::get<1>(t) *= v;
    return t;
}

int main()
{
    std::vector<int> a = { 1,2,3,4,5,6,7 };

    for (auto i=1ul << 31; i;)
    {
        auto accum = std::make_tuple(0,1);
        accum = std::accumulate(a.begin(), a.end(), accum, handle<decltype(accum), int>);

        if (!--i)
            std::cout << "sum: " << std::get<0>(accum) << ", product: " << std::get<1>(accum) << std::endl;
    }

    return 0;
}

Benchmarks:

Measured by doing the accumulation 2<<31 times (see snippet for the std::tuple based variant). Tested with -O2 and -O3 only:

• there is no measurable difference between any of the approaches shown (0.760s):

  • the for_each with a lambda
  • handcoded iterator loop or even the c++11 for (int i:a)
  • the handcoded accu_t struct (0.760s)
  • using std::tuple

• all variants exhibit a speed up of more than 18x going from -O2 to -O3 (13.8s to 0.760s), again regardless of the implementation chosen

• The tuple/accumulate the performance stays exactly the same with Tuple& handle(Tuple& t, T v) (by reference).