**Section:** 29.8.7 [exclusive.scan], 29.8.8 [inclusive.scan], 29.8.9 [transform.exclusive.scan], 29.8.10 [transform.inclusive.scan] **Status:** C++17
**Submitter:** Tim Song **Opened:** 2016-03-21 **Last modified:** 2017-07-30

**Priority: **1

**View all issues with** C++17 status.

**Discussion:**

When P0024R2 changed the description of `{inclusive,exclusive}_scan` (and the `transform_` version),
it seems to have introduced an off-by-one error. Consider what N4582 29.8.8 [inclusive.scan]/2 says of
`inclusive_scan`:

Effects: Assigns through each iterator

iin[result, result + (last - first))the value of

for everyGENERALIZED_NONCOMMUTATIVE_SUM(binary_op, init, *j, ...)jin[first, first + (i - result))ifinitis provided, or

for everyGENERALIZED_NONCOMMUTATIVE_SUM(binary_op, *j, ...)jin[first, first + (i - result))otherwise.

When `i == result`, `i - result = 0`, so the range `[first, first + (i - result))` is
`[first, first)` — which is empty. Thus according to the specification, we should assign
` GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, init)` if

The parallelism TS's version uses ` GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, *first, ..., *(first + (i - result)))` —
which is a closed range, not a half-open one.

Similar issues affect `exclusive_scan`, `transform_inclusive_scan`, and `transform_exclusive_scan`.

*[2016-06 Oulu]*

Voted to Ready 11-0 Tuesday evening in Oulu

**Proposed resolution:**

This wording is relative to N4582.

Edit 29.8.7 [exclusive.scan]/2 as indicated:

[

*Drafting note*: when`i`is`result`,`[first, first + (i - result))`is an empty range, so the value to be assigned reduces to, which is*GENERALIZED_NONCOMMUTATIVE_SUM*(binary_op, init)`init`, so there's no need to special case this.]template<class InputIterator, class OutputIterator, class T, class BinaryOperation> OutputIterator exclusive_scan(InputIterator first, InputIterator last, OutputIterator result, T init, BinaryOperation binary_op);

-2-

*Effects*: Assigns through each iterator`i`in`[result, result + (last - first))`the value offor every*GENERALIZED_NONCOMMUTATIVE_SUM*(binary_op, init, *j, ...)`j`in`[first, first + (i - result))`.`init`, if`i`is`result`, otherwisefor every*GENERALIZED_NONCOMMUTATIVE_SUM*(binary_op, init, *j, ...)`j`in`[first, first + (i - result) - 1)`.

Edit 29.8.8 [inclusive.scan]/2 as indicated:

template<class InputIterator, class OutputIterator, class BinaryOperation> OutputIterator inclusive_scan(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op); template<class InputIterator, class OutputIterator, class BinaryOperation> OutputIterator inclusive_scan(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op, T init);

-2-

*Effects*: Assigns through each iterator`i`in`[result, result + (last - first))`the value offor every*GENERALIZED_NONCOMMUTATIVE_SUM*(binary_op, init, *j, ...)`j`in`[first, first + (i - result + 1))`if`init`is provided, orfor every*GENERALIZED_NONCOMMUTATIVE_SUM*(binary_op, *j, ...)`j`in`[first, first + (i - result + 1))`otherwise.

Edit 29.8.9 [transform.exclusive.scan]/1 as indicated:

template<class InputIterator, class OutputIterator, class UnaryOperation, class T, class BinaryOperation> OutputIterator transform_exclusive_scan(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation unary_op, T init, BinaryOperation binary_op);

-1-

*Effects*: Assigns through each iterator`i`in`[result, result + (last - first))`the value offor every*GENERALIZED_NONCOMMUTATIVE_SUM*(binary_op, init, unary_op(*j), ...)`j`in`[first, first + (i - result))`.`init`, if`i`is`result`, otherwisefor every*GENERALIZED_NONCOMMUTATIVE_SUM*(binary_op, init, unary_op(*j), ...)`j`in`[first, first + (i - result) - 1)`.

Edit 29.8.10 [transform.inclusive.scan]/1 as indicated:

template<class InputIterator, class OutputIterator, class UnaryOperation, class BinaryOperation> OutputIterator transform_inclusive_scan(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation unary_op, BinaryOperation binary_op); template<class InputIterator, class OutputIterator, class UnaryOperation, class BinaryOperation, class T> OutputIterator transform_inclusive_scan(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation unary_op, BinaryOperation binary_op, T init);

-1-

*Effects*: Assigns through each iterator`i`in`[result, result + (last - first))`the value offor every*GENERALIZED_NONCOMMUTATIVE_SUM*(binary_op, init, unary_op(*j), ...)`j`in`[first, first + (i - result + 1))`if`init`is provided, orfor every*GENERALIZED_NONCOMMUTATIVE_SUM*(binary_op, unary_op(*j), ...)`j`in`[first, first + (i - result + 1))`otherwise.