This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of C++11 status.

### 539. `partial_sum` and `adjacent_difference` should mention requirements

Section: 27.10.7 [partial.sum] Status: C++11 Submitter: Marc Schoolderman Opened: 2006-02-06 Last modified: 2016-01-28

Priority: Not Prioritized

View all issues with C++11 status.

Discussion:

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."

[ Berlin: Giving output iterator's value_types very controversial. Suggestion of adding signatures to allow user to specify "accumulator". ]

[ Bellevue: ]

> The intent of the algorithms is to perform their calculations using the type of the input iterator. Proposed wording provided.

[ Sophia Antipolis: ]

> We did not agree that the proposed resolution was correct. For example, when the arguments are types `(float*, float*, double*)`, the highest-quality solution would use double as the type of the accumulator. If the intent of the wording is to require that the type of the accumulator must be the `input_iterator`'s `value_type`, the wording should specify it.

[ 2009-05-09 Alisdair adds: ]

> Now that we have the facility, the 'best' accumulator type could probably be deduced as:

> >     std::common_type<InIter::value_type, OutIter::reference>::type

> This type would then have additional requirements of constructability and incrementability/assignability.

> If this extracting an accumulator type from a pair/set of iterators (with additional requirements on that type) is a problem for multiple functions, it might be worth extracting into a SharedAccumulator concept or similar.

> I'll go no further in writing up wording now, until the group gives a clearer indication of preferred direction.

[ 2009-07 Frankfurt ]

> The proposed resolution isn't quite right. For example, "the type of `*first`" should be changed to "`iterator::value_type`" or similar. Daniel volunteered to correct the wording.

[ 2009-07-29 Daniel corrected wording. ]

[ 2009-10 Santa Cruz: ]

> Move to Ready.

Proposed resolution:

1. Change 27.10.7 [partial.sum]/1 as indicated:

   > Effects: Let `VT` be `InputIterator`'s value type. For a nonempty range, initializes an accumulator `acc` of type `VT` with `*first` and performs `*result = acc`. For every iterator `i` in `[first + 1, last)` in order, `acc` is then modified by `acc = acc + *i` or `acc = binary_op(acc, *i)` and is assigned to `*(result + (i - first))`. 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)))

   > or

   > >     binary_op(binary_op(...,
   > >        binary_op(*first, *(first + 1)),...), *(first + (i - result)))

2. Change 27.10.7 [partial.sum]/3 as indicated:

   > Complexity: Exactly `max((last - first) - 1, 0)` applications of `binary_op` the binary operation.

3. Change 27.10.7 [partial.sum]/4 as indicated:

   > Requires: `VT` shall be constructible from the type of `*first`, the result of `acc + *i` or `binary_op(acc, *i)` shall be implicitly convertible to `VT`, and the result of the expression `acc` shall be writable to the `result` output iterator. In the ranges `[first,last]` and `[result,result + (last - first)]` [..]

4. Change 27.10.12 [adjacent.difference]/1 as indicated:

   > Effects: Let `VT` be `InputIterator`'s value type. For a nonempty range, initializes an accumulator `acc` of type `VT` with `*first` and performs `*result = acc`. For every iterator `i` in `[first + 1, last)` in order, initializes a value `val` of type `VT` with `*i`, assigns the result of `val - acc` or `binary_op(val, acc)` to `*(result + (i - first))` and modifies `acc = std::move(val)`. Assigns to every element referred to by iterator `i` in the range `[result + 1, result + (last - first))` a value correspondingly equal to

   > >     *(first + (i - result)) - *(first + (i - result) - 1)

   > or

   > >     binary_op(*(first + (i - result)), *(first + (i - result) - 1)).

   > result gets the value of *first.

5. Change 27.10.12 [adjacent.difference]/2 as indicated:

   > Requires: `VT` shall be `MoveAssignable` ([moveassignable]) and shall be constructible from the type of `*first`. The result of the expression `acc` and the result of the expression `val - acc` or `binary_op(val, acc)` shall be writable to the `result` output iterator. In the ranges `[first,last]` [..]

6. Change 27.10.12 [adjacent.difference]/5 as indicated:

   > Complexity: Exactly `max((last - first) - 1, 0)` applications of `binary_op` the binary operation.