[Note: Forwarded to C++ Committee. -sdc ]

There are some problems in the definition of partial_sum and
adjacent_difference in 26.4 [lib.numeric.ops]

Unlike accumulate and inner_product, these functions are not
parametrized on a "type T", instead, 26.4.3 [lib.partial.sum] simply
specifies the effects clause as;

"Assigns to every element referred to by iterator i in the range
[result,result + (last - first)) a value correspondingly equal to

    ((...(* first + *( first + 1)) + ...) + *( first + ( i - result )))"

And similarly for BinaryOperation. Using just this definition, it seems
logical to expect that:

     char i_array[4] = { 100, 100, 100, 100 };
     int  o_array[4];

     std::partial_sum(i_array, i_array+4, o_array);

Is equivalent to

     int o_array[4] = { 100, 100+100, 100+100+100, 100+100+100+100 };

i.e. 100, 200, 300, 400, with addition happening in the 'result type', int.

Yet all implementations I have tested produce 100, -56, 44, -112,
because they are using an accumulator of the InputIterator's value_type,
which in this case is char, not int.

The issue becomes more noticeable when the result of the expression *i +
*(i+1) or binary_op(*i, *i-1) can't be converted to the value_type. In a
contrived example:

     enum not_int { x = 1, y = 2 };
    ...
     not_int e_array[4] = { x, x, y, y };
     std::partial_sum(e_array, e_array+4, o_array);

Is it the intent that the operations happen in the 'input type', or in
the 'result type'?

If the intent is that operations happen in the 'result type', something
like this should be added to the "Requires" clause of 26.4.3/4
[lib.partial.sum]:

      "The type of *i + *(i+1) or binary_op(*i, *(i+1)) shall meet the
requirements of CopyConstructible (20.1.3) and Assignable (23.1) types."

(As also required for 'T' in 26.4.1 [lib.accumulate] and 26.4.2
[lib.inner.product].)

The "auto initializer" feature proposed in N1894 is not required to
implement partial_sum this way. The 'narrowing' behaviour can still be
obtained by using the std::plus<> function object.

If the intent is that operations happen in the 'input type', then
something like this should be added instead;

      "The type of *first shall meet the requirements of
CopyConstructible (20.1.3) and Assignable (23.1) types. The result of *i
+ *(i+1) or binary_op(*i, *(i+1)) shall be convertible to this type."

The 'widening' behaviour can then be obtained by writing a custom proxy
iterator, which is somewhat involved.

In both cases, the semantics should probably be clarified.

26.4.4 [lib.adjacent.difference] is similarly underspecified, although
all implementations seem to perform operations in the 'result' type:

     unsigned char i_array[4] = { 4, 3, 2, 1 };
     int o_array[4];

     std::adjacent_difference(i_array, i_array+4, o_array);

o_array is 4, -1, -1, -1 as expected, not 4, 255, 255, 255.

In any case, adjacent_difference doesn't mention the requirements on the
value_type; it can be brought in line with the rest of 26.4
[lib.numeric.ops] by adding the following to 26.4.4/2
[lib.adjacent.difference]:

     "The type of *first shall meet the requirements of
CopyConstructible (20.1.3) and Assignable (23.1) types."

~Marc


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Marc Schoolderman wrote:
> [Note: Forwarded to C++ Committee. -sdc ]
>
> There are some problems in the definition of partial_sum and
> adjacent_difference in 26.4 [lib.numeric.ops]
>
> Unlike accumulate and inner_product, these functions are not
> parametrized on a "type T", instead, 26.4.3 [lib.partial.sum] simply
> specifies the effects clause as;
>
> "Assigns to every element referred to by iterator i in the range
> [result,result + (last - first)) a value correspondingly equal to
>
>     ((...(* first + *( first + 1)) + ...) + *( first + ( i - result )))"
>
> And similarly for BinaryOperation. Using just this definition, it seems
> logical to expect that:
>
>      char i_array[4] = { 100, 100, 100, 100 };
>      int  o_array[4];
>
>      std::partial_sum(i_array, i_array+4, o_array);
>
> Is equivalent to
>
>      int o_array[4] = { 100, 100+100, 100+100+100, 100+100+100+100 };
>
> i.e. 100, 200, 300, 400, with addition happening in the 'result type', int.
>
> Yet all implementations I have tested produce 100, -56, 44, -112,
> because they are using an accumulator of the InputIterator's value_type,
> which in this case is char, not int.
>
> The issue becomes more noticeable when the result of the expression *i +
> *(i+1) or binary_op(*i, *i-1) can't be converted to the value_type. In a
> contrived example:
>
>      enum not_int { x = 1, y = 2 };
>     ...
>      not_int e_array[4] = { x, x, y, y };
>      std::partial_sum(e_array, e_array+4, o_array);
>
> Is it the intent that the operations happen in the 'input type', or in
> the 'result type'?

The wording, as written, seems to require that it behave as if the
accumulator had the same type as the value returned by *i + *(i+1)
binary_op(*i,*(i-1)). That's not necessarily the same type as  either
the input iterator's value type, or the output iterator's value type.
Without typeof(), I think it would be rather tricky to achieve that. To
make things worse, consider the case where *i+*(i+1) has a different
type than (*i+(*i+1))+*(i+2), or similarly for binary_op(). Thanks to
function and operator overloading, it's quite feasible for that to be
the case. I'm not sure it's actually feasible to correctly implement
partial_sum() for such a class.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]