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

### 2687. `{inclusive,exclusive}_scan` misspecified

Section: 27.10.8 [exclusive.scan], 27.10.9 [inclusive.scan], 27.10.10 [transform.exclusive.scan], 27.10.11 [transform.inclusive.scan] Status: C++17 Submitter: Tim Song Opened: 2016-03-21 Last modified: 2017-07-30

Priority: 1

View all other issues in [exclusive.scan].

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 27.10.9 [inclusive.scan]/2 says of `inclusive_scan`:

> Effects: Assigns through each iterator `i` in `[result, result + (last - first))` the value of

> - `GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, init, *j, ...)` for every `j` in `[first, first + (i - result))` if `init` is provided, or

> - `GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, *j, ...)` for every `j` in `[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 `init` is provided, or `GENERALIZED_NONCOMMUTATIVE_SUM(binary_op)` otherwise, which doesn't seem "inclusive" — and isn't even defined in the second case.

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.

1. Edit 27.10.8 [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 `GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, init)`, which is `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 of `GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, init, *j, ...)` for every `j` in `[first, first + (i - result))`.

   > > - `init`, if `i` is `result`, otherwise

   > > - `GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, init, *j, ...)` for every `j` in `[first, first + (i - result) - 1)`.

2. Edit 27.10.9 [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 of

   > > - `GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, init, *j, ...)` for every `j` in `[first, first + (i - result + 1))` if `init` is provided, or

   > > - `GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, *j, ...)` for every `j` in `[first, first + (i - result + 1))` otherwise.

3. Edit 27.10.10 [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 of `GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, init, unary_op(*j), ...)` for every `j` in `[first, first + (i - result))`.

   > > - `init`, if `i` is `result`, otherwise

   > > - `GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, init, unary_op(*j), ...)` for every `j` in `[first, first + (i - result) - 1)`.

4. Edit 27.10.11 [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 of

   > > - `GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, init, unary_op(*j), ...)` for every `j` in `[first, first + (i - result + 1))` if `init` is provided, or

   > > - `GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, unary_op(*j), ...)` for every `j` in `[first, first + (i - result + 1))` otherwise.