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.
{inclusive,exclusive}_scan
misspecifiedSection: 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 everyj
in[first, first + (i - result))
ifinit
is provided, or
GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, *j, ...)
for everyj
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.
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 27.10.8 [exclusive.scan]/2 as indicated:
[Drafting note: when
i
isresult
,[first, first + (i - result))
is an empty range, so the value to be assigned reduces toGENERALIZED_NONCOMMUTATIVE_SUM(binary_op, init)
, which isinit
, 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 ofGENERALIZED_NONCOMMUTATIVE_SUM(binary_op, init, *j, ...)
for everyj
in[first, first + (i - result))
.
init
, ifi
isresult
, otherwise
GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, init, *j, ...)
for everyj
in[first, first + (i - result) - 1)
.
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 everyj
in[first, first + (i - result + 1))
ifinit
is provided, or
GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, *j, ...)
for everyj
in[first, first + (i - result + 1))
otherwise.
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 ofGENERALIZED_NONCOMMUTATIVE_SUM(binary_op, init, unary_op(*j), ...)
for everyj
in[first, first + (i - result))
.
init
, ifi
isresult
, otherwise
GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, init, unary_op(*j), ...)
for everyj
in[first, first + (i - result) - 1)
.
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 everyj
in[first, first + (i - result + 1))
ifinit
is provided, or
GENERALIZED_NONCOMMUTATIVE_SUM(binary_op, unary_op(*j), ...)
for everyj
in[first, first + (i - result + 1))
otherwise.