May second template argument in std::accumulate be a reference?

[Vlad from Moscow]

Consider the following demonstrative program

#include <iostream>
#include <algorithm>
#include <numeric>
#include <iterator>

int main()
{
 int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

 for ( int x : a ) std::cout << x << ' ';
 std::cout << std::endl;

 long long int acc = 0;
 std::cout << std::accumulate<decltype( std::begin( a ) ), long long int &>
  ( std::begin( a ), std::end( a ), acc ) << std::endl;

 std::cout << acc << std::endl;

 return 0;
}

Take into account that second argument of the std::accumulate is set like long long int & that is it is a reference.

This code compiles successfully at www.ideone.com. However the on-line MS VC++ compiler issues an error.

So the question is whether it is a bug of the MS VC++ compiler and all implementations of std::accumulate shall accept the second template argument set as a refernce or the C++ Standard guaranttees nothing in this case.

[Vlad from Moscow]

In my opinion it is a bug of the MS VC++ compiler and I submitted a bug report. However maybe here are other opinions

[Vlad from Moscow]

It seems that the Standard has a defect relative to the description of algorithm std::accumulate.

In the requirements for the algorithm there is written that

T shall meet the requirements of CopyConstructible (Table 21)

The notion of CopyConstructable means that expression

T u = v;

shall be valid.

However if type T has an explicit copy constructor then it does not satisfy the requirement.

I do not see any reason why a type with explicit copy constructor may not be used in the algorithm std::accumulate. The accumulator of std::accumulate could be directly initialized by init.

Also it seems that the second template argument may not be a reference. This is also a disadvantage.

[David Krauss]

On 2015–02–01, at 2:44 PM, Vlad from Moscow <vlad....@mail.ru> wrote:

I do not see any reason why a type with explicit copy constructor may not be used in the algorithm std::accumulate.

Explicit copy constructors are somewhat pathological. Such a type can never be passed by value.

The accumulator of std::accumulate could be directly initialized by init.

How do you propose to pass init in the first place?

Also it seems that the second template argument may not be a reference. This is also a disadvantage.

If you combine these two problems, they cancel out. You are allowed to pass an object with an explicit move/copy constructor, as long as you specify an [rvalue] reference type as an explicit template argument, causing it to be passed by reference.

Since you mention it, reference-to-iterator types satisfy the requirements for iterators as well…

[Vlad from Moscow]

Oh, I thought only about initialization of the accumulator inside the algorithm.:)

[Vlad from Moscow]

But in this case when the second template argument can be specified explicitly like a reference should there be specified that

typename std::remove_reference<T>::type  shall meet the requirements of CopyConstructible (Table 21) and CopyAssignable

instead of

T shall meet the requirements of CopyConstructible (Table 21) and CopyAssignable

in the algorithm description?

On Sunday, February 1, 2015 at 10:00:48 AM UTC+3, David Krauss wrote:

[David Krauss]

On 2015–02–01, at 4:49 PM, Vlad from Moscow <vlad....@mail.ru> wrote:

But in this case when the second template argument can be specified explicitly like a reference

What could go wrong? Reading your example program, it looks like you asked for reference semantics, and that’s exactly what you got.

should there be specified that 

typename std::remove_reference<T>::type  shall meet the requirements of CopyConstructible (Table 21) and CopyAssignable

CopyConstructible is only required for passing the init parameter by value as far as I can tell, and passing to the BinaryOperation if that’s being used. But if init is passed by reference, and the BinaryOperation doesn’t pass by T value, there’s no need for CopyConstructible.

If T is CopyAssignable, then T& will be as well, with the same semantics. So I don’t see a potential issue there. True, the RHS of the operations it mentions won’t be references, but…

The CopyAssignable requirement appears to be trying to ensure that acc = acc + * i or acc = binary_op( acc, * i ) operations will be well-formed, with the tacit and unsafe assumption that the return type of binary_op or operator+ will be T. I think CopyAssignable should be dropped from the requirements, and it should simply require that the given operations are valid. (Also, I think that operator+= would be much more sensible than operator+, but that’s not likely to change.)

[Vlad from Moscow]

As for me then the description of the algorithm is confusing. It is not clear whether init has to be passed only by value or it may be passed by reference.

[Vlad from Moscow]

By the way the same bug of MS VC++ exists for std::inner_product. That is this program

#include <iostream>
#include <numeric>
#include <iterator>

int main()
{
 int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

 int b[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };

 for ( int x : a ) std::cout << x << ' ';
 std::cout << std::endl;

 for ( int x : b ) std::cout << x << ' ';
 std::cout << std::endl;

 std::cout << std::endl;
 
 long long int acc = 0;

 std::cout << std::inner_product<decltype( std::begin( a ) ),
                                 decltype( std::begin( b ) ),
                                 long long int &>
   ( std::begin( a ), std::end( a ), std::begin( b ), acc ) << std::endl;

 std::cout << acc << std::endl;
 
 return 0;
}

will not compile while GCC and clang compile the program successfully and output

0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0

120
120

On Saturday, January 31, 2015 at 1:47:45 PM UTC+3, Vlad from Moscow wrote:

[T. C.]

Note that the standard never specified the type of the accumulator (acc) for inner_product or accumulate; it says that it is initialized with init, not that its type is T.

[Vlad from Moscow]

It is a good remark. Though it is implied that the type of the accumulator is T because otherwise the behaviour of the algorithm is undefined (consider the situation when the initializer is specified as having type double byte withing the algorithm the type of the accumulator is int) nevertheless this should be said explicitly.

Of course the same problem exists for algorithm std::accumulate.

It seems that it is a standard defect. I wcould write a corresponding proposal.

[David Krauss]

> On 2015–02–11, at 3:41 AM, Vlad from Moscow <vlad....@mail.ru> wrote:
>
> It is a good remark. Though it is implied that the type of the accumulator is T because otherwise the behaviour of the algorithm is undefined (consider the situation when the initializer is specified as having type double byte withing the algorithm the type of the accumulator is int) nevertheless this should be said explicitly.
>
> Of course the same problem exists for algorithm std::accumulate.
>
> It seems that it is a standard defect. I wcould write a corresponding proposal.

Just send a brief defect report to Daniel Krügler.

[Vlad from Moscow]

I think that it will be important also to point out that the accumulator shall be defined exactly like

T acc = init;

It may not be defined like

auto acc = init;

because the behaviour will be different compared with the first declaration.

[David Rodríguez Ibeas]

I am not sure where we want to get to from here...  The standard has allowed for a quite some time to make copies of inputs and forward from one algorithm to another.  For example, a common implementation of 'remove_copy_if' would start with a call to 'find_if' to skip over the initial part of the input sequence.  For that implementations have often depended on type deduction, exactly the same that goes into the declaration 'auto acc = init;'  

Do you mean to forbid type deduction on algorithms? Should algorithms, if they forward, forward the exact types that were passed in?  Or just special case some algorithms as "special"?  This could become complicated easy enough, consider for example that the user explicitly called for an rvalue-reference, should the algorithm accommodate for this? How could it in the general case where it might be passing the inputs to a helper in the middle of processing?

    David

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussio...@isocpp.org.
To post to this group, send email to std-dis...@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-discussion/.

[Vlad from Moscow]

You have reminded me about std::iota. I forgot to include it in the standard proposal.:)

First of all if you want to forward the result from one algorithm to another algorithm then you should take into account that for example my proposal to declare std::iota such a way that it would return the accumulated value was rejected by the C++ Standards Committee without any reason.:)

I believe that three algorithms, std::accumulate, std::inner_product, and std::iota, should acccept initializer by reference and accordingly process it. That is I suggest that for example this program

#include <iostream>
#include <numeric>
#include <iterator>

int main()
{
 const size_t N = 10;
 int a[N];
 int value = 0;
       
 std::iota<decltype( std::begin( a ) ), int &>
 ( std::begin( a ), std::end( a ), value );

       
 for ( int x : a ) std::cout << x << ' ';
 std::cout << std::endl;
 

 std::cout << "value = " << value << std::endl;
       
 return 0;
}

would yield result

0 1 2 3 4 5 6 7 8 9

value = 10

However in any case std::iota shall return value as I proposed independing on whether it is passed by reference.

The program above has different output if to compile it with the on-line MS VC++ compiler that is second line of the output is

value = 0

The possibility to have the second template argument as reference enlarges the functionality of algorithms.

[Scott Prager]

On Monday, February 23, 2015 at 9:21:20 AM UTC-5, Vlad from Moscow wrote:

You have reminded me about std::iota. I forgot to include it in the standard proposal.:)

First of all if you want to forward the result from one algorithm to another algorithm then you should take into account that for example my proposal to declare std::iota such a way that it would return the accumulated value was rejected by the C++ Standards Committee without any reason.:)

I believe that three algorithms, std::accumulate, std::inner_product, and std::iota, should acccept initializer by reference and accordingly process it. That is I suggest that for example this program

#include <iostream>
#include <numeric>
#include <iterator>

int main()
{
 const size_t N = 10;
 int a[N];
 int value = 0;
       
 std::iota<decltype( std::begin( a ) ), int &>
 ( std::begin( a ), std::end( a ), value );
       
 for ( int x : a ) std::cout << x << ' ';
 std::cout << std::endl;
 
 std::cout << "value = " << value << std::endl;
       
 return 0;
}

would yield result

0 1 2 3 4 5 6 7 8 9
value = 10

However in any case std::iota shall return value as I proposed independing on whether it is passed by reference.

The program above has different output if to compile it with the on-line MS VC++ compiler that is second line of the output is

value = 0

The possibility to have the second template argument as reference enlarges the functionality of algorithms.

Although, this can already be accomplished with `std::ref`.

And I hope it will produce the same result on all compilers.

#include <iostream>
#include <numeric>
#include <iterator>

#include <functional>

int main()
{
 const size_t N = 10;
 int a[N];
 int value = 0;

       
 std::iota(std::begin(a), std::end(a), std::ref(value));

       
 for ( int x : a ) std::cout << x << ' ';
 std::cout << std::endl;
 
 std::cout << "value = " << value << std::endl;
       
 return 0;
}

On Monday, February 23, 2015 at 4:19:24 PM UTC+3, David Rodríguez Ibeas wrote:

[Vlad from Moscow]

This code

 int value = 0;

 std::accumulate( std::begin( a ), std::end( a ), std::ref( value ) );

will not be compiled.

[Casey Carter]

On Monday, February 23, 2015 at 10:04:56 AM UTC-6, Vlad from Moscow wrote:

This code

 int value = 0;

 std::accumulate( std::begin( a ), std::end( a ), std::ref( value ) );

will not be compiled.

If it doesn't compile, your implementation is non-conforming. The requirements of std::iota:

template <class ForwardIterator, class T>
void iota(ForwardIterator first, ForwardIterator last, T value); 

1 Requires: T shall be convertible to ForwardIterator’s value type. The expression ++val, where val
has type T, shall be well formed.

std::reference_wrapper<int> is convertible to int via its member conversion operator T& () const. Similarly, ++val when val has type std::reference_wrapper<int> resolves to ++val.operator int&() per [over.match.oper].

[Vlad from Moscow]

In the code snippet I showed there is used std::accumulate.

I would like that these three algorithms I referred in my preceeding post have the similar behaviour and interface.

[Vlad from Moscow]

I think that in the Standard the description of the algorithm should corresponds either to this its implementation as shown in the demonstrative program below

#include <iostream>
#include <iterator>

template <typename InputIterator, typename T>
T accumulate( InputIterator first, InputIterator last, T init )
{
    decltype( auto ) acc = init;
   
    for ( ; first != last; ++first ) acc = acc + *first;
   
    return init;
}


int main()

{
    int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int sum = 0;
   
    accumulate<int *, int &>( std::begin( a ), std::end( a ), sum );
   
    std::cout << "sum = " << sum << std::endl;
}

or to this its implementation shown in this demonstrative program

#include <iostream>
#include <iterator>


template <typename InputIterator, typename T>
T accumulate( InputIterator first, InputIterator last, T init )
{
    for ( ; first != last; ++first ) init = init + *first;
   
    return init;
}


int main()
{
    int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int sum = 0;
   
    accumulate<int *, int &>( std::begin( a ), std::end( a ), sum );
   
    std::cout << "sum = " << sum << std::endl;
}

In this case there is no problem with a referenced type of the second template parameter.

суббота, 31 января 2015 г., 13:47:45 UTC+3 пользователь Vlad from Moscow написал:

[Vlad from Moscow]

There is a typo in the previous post. I meant

template <typename InputIterator, typename T>
T accumulate( InputIterator first, InputIterator last, T init )
{
    decltype( auto ) acc = init;
   
    for ( ; first != last; ++first ) acc = acc + *first;

   
    return acc;
}

четверг, 7 июня 2018 г., 17:23:38 UTC+3 пользователь Vlad from Moscow написал:

[Richard Hodges]

On Thu, 7 Jun 2018 at 15:29, 'Vlad from Moscow' via ISO C++ Standard - Discussion <std-dis...@isocpp.org> wrote:

There is a typo in the previous post. I meant

Surely if it's to be fixed, it should be properly fixed?

template <typename FirstInputIterator, typename LastInputIterator, typename T, typename BinaryFunction = std::plus<>>

constexpr auto accumulate( FirstInputIterator first, LastInputIterator last, T init, BinaryFunction func = BinaryFunction() )

noexcept(noexcept(std::declval<BinaryFunction>()(init, *first)))

-> decltype(std::declval<BinaryFunction>()(std::declval<std::common_type_t<T, decltype(*first)>>(), *first))

{

  for ( ; first != last; ++first )

    init = func(init, *first);

  return init;

}

 

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-discussio...@isocpp.org.
To post to this group, send email to std-dis...@isocpp.org.

Visit this group at https://groups.google.com/a/isocpp.org/group/std-discussion/.

[Richard Hodges]

On Thu, 7 Jun 2018 at 15:56, Richard Hodges <hodg...@gmail.com> wrote:

On Thu, 7 Jun 2018 at 15:29, 'Vlad from Moscow' via ISO C++ Standard - Discussion <std-dis...@isocpp.org> wrote:

There is a typo in the previous post. I meant

Surely if it's to be fixed, it should be properly fixed?

Uh oh... I'm falling down a rabbit hole...

template <typename FirstInputIterator, typename LastInputIterator, typename T, typename BinaryFunction = std::plus<>>

constexpr auto accumulate( FirstInputIterator first, LastInputIterator last, T init, BinaryFunction func = BinaryFunction() )

noexcept(noexcept(std::declval<BinaryFunction>()(init, *first)))

-> decltype(std::declval<BinaryFunction>()(std::declval<std::common_type_t<T, decltype(*first)>>(), *first))

{

  decltype(std::declval<BinaryFunction>()(std::declval<std::common_type_t<T, decltype(*first)>>(), *first)) accum = init;

  for ( ; first != last; ++first )

    accum = func(init, *first);

  return accum;

}

 

[Hyman Rosen]

On Thu, Jun 7, 2018 at 11:06 AM Richard Hodges <hodg...@gmail.com> wrote:

Uh oh... I'm falling down a rabbit hole...

template <typename FirstInputIterator, typename LastInputIterator, typename T, typename BinaryFunction = std::plus<>>

constexpr auto accumulate( FirstInputIterator first, LastInputIterator last, T init, BinaryFunction func = BinaryFunction() )

noexcept(noexcept(std::declval<BinaryFunction>()(init, *first)))

-> decltype(std::declval<BinaryFunction>()(std::declval<std::common_type_t<T, decltype(*first)>>(), *first))

{

  decltype(std::declval<BinaryFunction>()(std::declval<std::common_type_t<T, decltype(*first)>>(), *first)) accum = init;

  for ( ; first != last; ++first )

    accum = func(init, *first);

  return accum;

}

Aside from the whole thing being hideous, it's wrong.
First of all, the code inside the loop should be  accum = func(accum, *first);
Second, your noexcept specification is incorrect, as the following demonstrates:

struct I { };

struct X { X() { } X(const I&) { throw 0; } };

struct F {

    template <typename A, typename B>

    X operator()(const A&, const B&) noexcept { return X(); }

};

int main() {

    try { accumulate((X *)0, (X *)0, I(), F()); }

    catch (int) { }

}

If your noexcept specification is removed, the program runs successfully.
If it's left in place, the program crashes with a call to terminate().  I have
not violated any requirements of accumulate; the type T (which here is I), is
copy constructible and copy assignable, and my operator does not modify or
invalidate elements of the range.

[Richard Hodges]

Fantastic demonstration that the road to Hell is paved with good intentions. 

:)