accumulate with copy

[Ralf Goertz]

Hi,

I wondered why there is no std::accumulate function or at least
something that allows me to do that easily using <algorithm> (or is
there?). Of course I can just iterate myself but that's not the point.
So I tried to write a templated class inheriting from
iterator<output_iterator_tag, T> and defined all increment and decrement
operators to do nothing. (It turned out I only needed one of them so I
left out the others in the code below.) Within the iterator class I
defined a helper class that allows me to change "=" to be "+=". Then I
use std::copy() to do the job. It seems to work principle as the outout
shows but all those copies flying around I end up with nothing. Which I
don't understand since I defined all copy and assignment constructors
for both the iterator class and it's helper class to always copy my
value around. So what is the problem?

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

using namespace std;

template<typename T> struct Accum:public iterator<output_iterator_tag, T> {
struct Val {
T s;
explicit Val(const T & s_) :s(s_){
cerr<<this<<" Val(cons T&) right: "<<s_<<endl;
}
explicit Val(const Val& v) : s(v.s) {
cerr<<this<<" Val(const Val&) right: "<<&v<<endl;
}
Val & operator=(const Val& v) {
s=v.s;cerr<<this<<" Val operator=(const Val&) right: "<<&v<<endl;
}
Val & operator=(const T& t) {
s+=t;
cerr<<this<<" Val & operator=(const T&) "<<t<<" result "<<s<<endl;
return *this;
}
operator T() const {cerr<<this<<" operator T(): "<<s<<endl;return s;}
} n;
Accum():n(0) {
cerr<<this<<" Accum() "<<n<<endl;
}
Accum(const Accum &r) : n(r.n) {
cerr<<this<<" Accum(const Accum&) right: "<<&r.n<<endl;
}
Accum& operator=(const Accum &r) { //doesn't get called
n=r.n;
cerr<<this<<" operator=(const Accum&) right: "<<&r.n<<" result"
<<n.s<<endl;
}
Accum& operator++() {
cerr<<"++ called"<<endl;
return *this;
}
Val & operator*() {
cerr<<this<<" * called n="<<n.s<<endl;
return n;
}
};


int main() {
vector<int> v{{6,2,3}};
Accum<int> a;
copy(v.begin(),v.end(),a);
cout<<*a<<endl;
return 0;
}

output:

0x7ffd3d549320 Val(cons T&) right: 0
0x7ffd3d549320 operator T(): 0
0x7ffd3d549320 Accum() 0
0x7ffd3d549330 Val(const Val&) right: 0x7ffd3d549320
0x7ffd3d549330 Accum(const Accum&) right: 0x7ffd3d549320
0x7ffd3d549350 Val(const Val&) right: 0x7ffd3d549330
0x7ffd3d549350 Accum(const Accum&) right: 0x7ffd3d549330
0x7ffd3d549370 Val(const Val&) right: 0x7ffd3d549350
0x7ffd3d549370 Accum(const Accum&) right: 0x7ffd3d549350
0x7ffd3d549380 Val(const Val&) right: 0x7ffd3d549370
0x7ffd3d549380 Accum(const Accum&) right: 0x7ffd3d549370
0x7ffd3d549360 Val(const Val&) right: 0x7ffd3d549380
0x7ffd3d549360 Accum(const Accum&) right: 0x7ffd3d549380
0x7ffd3d549360 * called n=0
0x7ffd3d549360 Val & operator=(const T&) 6 result 6
++ called
0x7ffd3d549360 * called n=6
0x7ffd3d549360 Val & operator=(const T&) 2 result 8
++ called
0x7ffd3d549360 * called n=8
0x7ffd3d549360 Val & operator=(const T&) 3 result 11
++ called
0x7ffd3d549340 Val(const Val&) right: 0x7ffd3d549360
0x7ffd3d549340 Accum(const Accum&) right: 0x7ffd3d549360
0x7ffd3d549320 * called n=0
0x7ffd3d549320 operator T(): 0
0

[James R. Kuyper]

On 03/08/2018 04:03 AM, Ralf Goertz wrote:
> Hi,
>
> I wondered why there is no std::accumulate function

There is: it's in <numeric> and defined in section 29.8.2 of the standard:

> template <class InputIterator, class T>
> T accumulate(InputIterator first, InputIterator last, T init);
> template <class InputIterator, class T, class BinaryOperation>
> T accumulate(InputIterator first, InputIterator last, T init,
> BinaryOperation binary_op);
> 1 Requires: T shall meet the requirements of CopyConstructible > (Table 24) and CopyAssignable (Table 26) types. In the range [first,
> last], binary_op shall neither modify elements nor invalidate
> iterators or subranges. 281
> 2 Effects: Computes its result by initializing the accumulator
> acc with the initial value init and then modifies it with
> acc = acc +*i or acc = binary_op(acc, *i) for every iterator i in
> the range [first, last) in order. 282
~/testprog(115) cat accumulate.cpp
#include <iostream>
#include <numeric>
#include <vector>

int main(void) {
std::vector<int> v{{6,2,3}};
std::cout << std::accumulate(v.begin(), v.end(), 0L) << std::endl;
return 0;
}
~/testprog(116) g++ -std=c++1y -pedantic -Wall -Wpointer-arith
-Wcast-align -ffor-scope -fno-gnu-keywords -fno-nonansi-builtins
-Wctor-dtor-privacy -Wnon-virtual-dtor -Wold-style-cast
-Woverloaded-virtual -Wsign-promo accumulate.cpp -o accumulate
~/testprog(117) ./accumulate
11

...

The fundamental problem here is that a gets passed to std::copy<>() by
value. In other words, the third parameter of std::copy() is a separate
instance of Accum<int>, initialized with a copy of the values stored in
a. All that accumulation occurs inside the copies of that object which
std::copy<>() creates. The value of a itself remains completely unchanged.

> cout<<*a<<endl;

And therefore, it does not reflect the accumulation that has occurred.
In order to do what you want done, 'n' should exist outside of the
iterator. Initialize your iterator from a pointer or reference to that
object, and have copy/assignment of your iterator produce a new iterator
that points/refers to the same external object as the original. Then
your code should work (unless it has some other flaw I haven't noticed yet).

[Ralf Goertz]

Am Thu, 8 Mar 2018 09:33:51 -0500
schrieb "James R. Kuyper" <james...@verizon.net>:

> On 03/08/2018 04:03 AM, Ralf Goertz wrote:
>
> >
> > int main() {
> > vector<int> v{{6,2,3}};
> > Accum<int> a;
> > copy(v.begin(),v.end(),a);
>
> The fundamental problem here is that a gets passed to std::copy<>()
> by value. In other words, the third parameter of std::copy() is a
> separate instance of Accum<int>, initialized with a copy of the
> values stored in a. All that accumulation occurs inside the copies of
> that object which std::copy<>() creates. The value of a itself
> remains completely unchanged.
>
> > cout<<*a<<endl;

Of course, it's passed by value! How blind of me. I didn't think that I
would ever be caught in that beginner's trap again. Thanks for proving
me wrong. ;-) And thanks for pointing me to <numeric> of whose content I
have been ignorant up to now.

[Richard]

[Please do not mail me a copy of your followup]

Ralf Goertz <m...@myprovider.invalid> spake the secret code
<20180308161...@delli.fritz.box> thusly:

>[...] And thanks for pointing me to <numeric> of whose content I

>have been ignorant up to now.

A good way to discover stuff like this is to search cppreference.com :)
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Terminals Wiki <http://terminals-wiki.org>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>

[Ralf Goertz]

Am Thu, 8 Mar 2018 18:59:58 +0000 (UTC)
schrieb legaliz...@mail.xmission.com (Richard):

> [Please do not mail me a copy of your followup]
>
> Ralf Goertz <m...@myprovider.invalid> spake the secret code
> <20180308161...@delli.fritz.box> thusly:
>
> >[...] And thanks for pointing me to <numeric> of whose content I
> >have been ignorant up to now.
>
> A good way to discover stuff like this is to search
> cppreference.com :)

I know that. As I said, I knew *of* <numeric> but thought it's *content*
were boring for me (e.g. numerical limits, but they are in <limits>, or
special functions like error function).

[Ben Bacarisse]

It's certainly and odd place for std::accumulate to be because it's not
inherently numeric but it is a generic algorithm. Maybe <numeric>
pre-dates <algorithm>...

--
Ben.

[Ralf Goertz]

Am Thu, 8 Mar 2018 16:19:12 +0100
schrieb Ralf Goertz <m...@myprovider.invalid>:

> Am Thu, 8 Mar 2018 09:33:51 -0500
> schrieb "James R. Kuyper" <james...@verizon.net>:
>
> > On 03/08/2018 04:03 AM, Ralf Goertz wrote:
> >
> > >
> > > int main() {
> > > vector<int> v{{6,2,3}};
> > > Accum<int> a;
> > > copy(v.begin(),v.end(),a);
> >
> > The fundamental problem here is that a gets passed to std::copy<>()
> > by value. In other words, the third parameter of std::copy() is a
> > separate instance of Accum<int>, initialized with a copy of the
> > values stored in a. All that accumulation occurs inside the copies
> > of that object which std::copy<>() creates. The value of a itself
> > remains completely unchanged.
> >
> > > cout<<*a<<endl;
>
> Of course, it's passed by value! How blind of me. I didn't think that
> I would ever be caught in that beginner's trap again.

There are two main reasons I stumbled into the trap. Firstly, in my
imagination iterators are smart pointers and for pointers it usually
doesn't matter whether they are used by copy or by reference. But, as
the "pointed to" object was part of my iterator class, in this case it
did matter. Secondly, I was confused by the number of copies of a (seven
if I counted correctly). If there had been only two, I might have
spotted the problem myself. By the way why are there so many copies? It
seems as if std::copy makes them. ;-) But not for every element. Even
with an empty vector there are seven.

[James Kuyper]

The oldest version of the STL that I could easily find
<http://stepanovpapers.com/butler.hpl.hp/stl/stl.zip> has accumulate
defined inside ALGO.H, and the accompanying documentation organizes the
generalized numeric operations (what is now <numeric>) in section 10.4,
underneath section 10, "Algorithms".

[Chris Vine]

I agree it is odd to put a generic 'fold' function in the <numeric>
header, but once you have separate <algorithm> and <numeric> headers[1]
I guess it is difficult to know where to draw the line. What about
std::inner_product(), which carries out a fold over two sequences?
(Although std::inner_product, unlike most common implementations of
multi-sequence folds, does not take one combining function receiving an
element from each sequence and the accumulated value: instead
std::inner_product() takes two binary callable objects, the first of
which receives an element from each sequence, and the second receives
the result of that application together with the result of the previous
application, the accumulator; so it can also be used to perform a kind
of map-reduce.)

Then there is std::partial_sum(), which is a variant of
std::accumulate() which stores intermediate results. Although it can
be used to fold over any type which is copyable/movable to provide
partial results, it is in essence an integration function, the opposite
of std::adjacent_difference()'s differentiation.

Anyway the C++ standard committee have stuck to their guns - C++17 adds
generic std::reduce() and std::transform_reduce() algorithms to the
<numeric> header. Having a separate <numeric> header may have been a
mistake, but they no doubt feel they now have to stick with it.

Chris

[1] There is also a third header, <memory> which contains the
uninitialized_copy() algorithms and cognate operations.