for_each() algorithm

[silverburgh.meryl]

I have a function which calculate standard deviation. I am trying to
re-write it using STL algorithm.
I am thinking of using for_each() algorithm, but that will require my
function passing in to have state (e.g. the value of standard deviation
sum). I read some online article that having state is not a good
idea. So is there a better solution?

Thank you.

/**
Calculate the standard deviation, given the mean of the numbers
*/
double sd( const vector<int>& v,
const double mean )
{
double stdDev = 0.0;
int N = v.size();
const double mean_ = mean;

// calculate the standard deviation sum
double stdDevSum = 0;
double x;
for (int i = 0; i < N; i++) {
x = v - mean_;
stdDevSum = stdDevSum + (x * x);
}
double variance = stdDevSum / static_cast<double>(N-1);
stdDev = sqrt( variance );
return stdDev;
} // sd

 

[Thomas Tutone]

I have a function which calculate standard deviation. I am trying to
re-write it using STL algorithm.
I am thinking of using for_each() algorithm, but that will require my
function passing in to have state (e.g. the value of standard deviation
sum). I read some online article that having state is not a good
idea. So is there a better solution?

std::for_each() is an exception to the general rule: Function objects
used with that algorithm may have state, and that is the reason that
algorithm returns the function object.

Best regards,

Tom

 

[Neelesh Bodas]

I have a function which calculate standard deviation. I am trying to
re-write it using STL algorithm.
I am thinking of using for_each() algorithm, but that will require my
function passing in to have state (e.g. the value of standard deviation
sum). I read some online article that having state is not a good
idea. So is there a better solution?

Function Objects. Declare a class StdDeviation with operator() so that
an object of this class can be passed as third parameter to for_each.
stdDevSum will be a data member of such a class, initialized to zero
via no-arg constructor.

 

[Michiel.Salters]

I have a function which calculate standard deviation. I am trying to
re-write it using STL algorithm.
I am thinking of using for_each() algorithm, but that will require my
function passing in to have state (e.g. the value of standard deviation
sum). I read some online article that having state is not a good
idea. So is there a better solution?

Yes. Take the algorithm you have, and replace just the for-loop with
the appropriate algorithm. In this case, you're summing
(x-xavg)*(x-xavg).
Now, summing a number of values is best done by std::accumulate.

HTH,
Michiel Salters

 

[Ben Pope]

I have a function which calculate standard deviation. I am trying to
re-write it using STL algorithm.
I am thinking of using for_each() algorithm, but that will require my
function passing in to have state (e.g. the value of standard deviation
sum). I read some online article that having state is not a good
idea. So is there a better solution?

You are not calculating the standard deviation "for each" element, so
don't use for_each.

Use a free-standing templated function that takes a start iterator and
an end iterator and returns the result of templated type.

Just look at the other STL algorithms and see what they do, accumulate
would be a good start. In fact, why not just wrap std::accumulate and
then divide by (end - begin)?

Ben Pope

 

[Ben Pope]

In fact, why not just wrap std::accumulate and
then divide by (end - begin)?

....because that would be mean, not standard deviation. Anyway, you get
the idea.

Ben Pope

 

[roberts.noah]

I have a function which calculate standard deviation. I am trying to
re-write it using STL algorithm.
I am thinking of using for_each() algorithm, but that will require my
function passing in to have state (e.g. the value of standard deviation
sum). I read some online article that having state is not a good
idea. So is there a better solution?

I would be interested in the article that stated that. I often use
for_each with algorithms that require "state". Why else even have such
a construct as functors? Hell, the std::accumulator that others are
mentioning has state as it has an accumulator. So I would really need
to read that argument against such constructs to be at all
convinced...and it would be a hard sale.

 

[silverburgh.meryl]

Here is what I did, but I get a compile error "stddev.cpp:69:
instantiated from here.

Any idea why it won't compile?

template<class T> class do_sd : public binary_function<T, T, T>
{
public:
do_sd(T mean): _mean(mean) { }

T operator() (T initial, T element) {
T x = element - _mean;
initial = initial + (x * x);
return initial;
}
private:
T _mean;
};

double stdDevSum = accumulate (v.begin(), v.end(), 0,
do_sd<double>(mean) );

 

[Ben Pope]

Here is what I did, but I get a compile error "stddev.cpp:69:
instantiated from here.

Any idea why it won't compile?

If you want to know why it won't compile, please post a complete
program. There is no main, no description of "v", etc.

Ben Pope

 

[roberts.noah]

mentioning has state as it has an accumulator.

Please disregard the above stupidity...it's still early.

 

[Alan Johnson]

I would be interested in the article that stated that. I often use
for_each with algorithms that require "state". Why else even have such
a construct as functors? Hell, the std::accumulator that others are
mentioning has state as it has an accumulator. So I would really need
to read that argument against such constructs to be at all
convinced...and it would be a hard sale.

This is likely the article:
http://www.informit.com/articles/article.asp?p=25142&seqNum=4&rl=1

Came up in a discussion in this group a few days ago.

-Alan

 

[roberts.noah]

This is likely the article:
http://www.informit.com/articles/article.asp?p=25142&seqNum=4&rl=1

Came up in a discussion in this group a few days ago.

Well, that seems to talk about predicates only and about algorithms
such as remove_if. I see some of the points made. However, for_each
and transform are quite a bit different.

 

[Earl Purple]

Here is what I did, but I get a compile error "stddev.cpp:69:
instantiated from here.

Any idea why it won't compile?

template<class T> class do_sd : public binary_function<T, T, T>
{
public:
do_sd(T mean): _mean(mean) { }

T operator() (T initial, T element) {
T x = element - _mean;
initial = initial + (x * x);
return initial;
}
private:
T _mean;
};

double stdDevSum = accumulate (v.begin(), v.end(), 0,
do_sd<double>(mean) );

Not sure you've quite got this right anyway.

Now using accumulate this works:

class StatCalc
{
double m_Total;
double m_SqTotal;
size_t m_n;

public:
StatCalc() : m_Total( 0.0 ), m_SqTotal( 0.0 ), m_n( 0 )
{
}

StatCalc& operator+= ( double d )
{
m_Total += d;
m_SqTotal += d*d;
++m_n;
return *this;
}

double mean() const // m_n must be non-zero
{
return m_Total / m_n;
}

double variance() const
{
return (m_SqTotal - m_Total * m_Total / m_n) / m_n;
}

double sd() const
{
return std::sqrt( variance() );
}
};

inline StatCalc operator+( const StatCalc & lhs, double rhs )
{
StatCalc res( lhs );
return res += rhs;
}

const StatCalc& result = std::accumulate( v.begin(), v.end(),
StatCalc() );
double sd = result.sd();

If you want to use for_each instead just replace operator+= with
operator(). Note you can also optimize for_each by specifying StatCalc
as a reference, i.e.

StatCalc calc;
typedef std::vector<double>::const_iterator iter_type;
std::for_each< iter_type, iter_type, StatCalc& >( v.begin(), v.end(),
calc );
double sd = calc.sd(); // should work, assuming you've changed += into
()

 

[silverburgh.meryl]

Thanks.

Can you please tell me what is this for? When/what will call this?
inline StatCalc operator+( const StatCalc & lhs, double rhs )
{
StatCalc res( lhs );
return res += rhs;

}
And why we overload 'operator+=' instead of 'operator()'?

thank you.

 

[Earl Purple]

Thanks.

Can you please tell me what is this for? When/what will call this?
inline StatCalc operator+( const StatCalc & lhs, double rhs )
{
StatCalc res( lhs );
return res += rhs;

}
And why we overload 'operator+=' instead of 'operator()'?

thank you.

std::accumulate uses operator+ (unfortunately not += like it should).
But I have implemented + in terms of +=.

If you want to use std::for_each then use operator() like I suggested.
There might be a performance gain in doing so, but accumulate looks a
more natural algorithm to use because you are adding in values.

std::transform can also be implemented using std::for_each if you
really want. (Even the version that takes 2 inputs).

 

[Daniel T.]

Now using accumulate this works:

class StatCalc
{
double m_Total;
double m_SqTotal;
size_t m_n;

public:
StatCalc() : m_Total( 0.0 ), m_SqTotal( 0.0 ), m_n( 0 )
{
}

StatCalc& operator+= ( double d )
{
m_Total += d;
m_SqTotal += d*d;
++m_n;
return *this;
}

double mean() const // m_n must be non-zero
{
return m_Total / m_n;
}

double variance() const
{
return (m_SqTotal - m_Total * m_Total / m_n) / m_n;
}

double sd() const
{
return std::sqrt( variance() );
}
};


const StatCalc& result = std::accumulate( v.begin(), v.end(),
StatCalc() );
double sd = result.sd();

If you want to use for_each instead just replace operator+= with
operator(). Note you can also optimize for_each by specifying StatCalc
as a reference, i.e.

StatCalc calc;
typedef std::vector<double>::const_iterator iter_type;
std::for_each< iter_type, iter_type, StatCalc& >( v.begin(), v.end(),
calc );
double sd = calc.sd(); // should work, assuming you've changed += into
()

My solution turned out much like yours, however I think your operator+
is off:

inline StatCalc operator+( const StatCalc & lhs, double rhs )
{
StatCalc res( lhs );
return res += rhs;
}

I don't think you can "return res += rhs"

 

[Earl Purple]

My solution turned out much like yours, however I think your operator+
is off:


I don't think you can "return res += rhs"

Why not? My += operator returns StatCalc& which is converted to a
StatCalc by the copy-constructor. It also has a RHS of double.

Of course RVO should ensure that only one copy-constructor is called
(although in my mind that is still one copy-constructor too many).

 

[Daniel T.]

Why not? My += operator returns StatCalc& which is converted to a
StatCalc by the copy-constructor. It also has a RHS of double.

Of course RVO should ensure that only one copy-constructor is called
(although in my mind that is still one copy-constructor too many).

My mistake, I wrote my op+= wrong...