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.
partial_sum
and adjacent_difference
should mention requirementsSection: 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)
orbinary_op(*i, *(i+1))
shall meet the requirements ofCopyConstructible
(20.1.3) andAssignable
(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) andAssignable
(23.1) types. The result of*i + *(i+1)
orbinary_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 ofCopyConstructible
(20.1.3) andAssignable
(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 theinput_iterator
'svalue_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>::typeThis 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:
Change 27.10.7 [partial.sum]/1 as indicated:
Effects: Let
VT
beInputIterator
's value type. For a nonempty range, initializes an accumulatoracc
of typeVT
with*first
and performs*result = acc
. For every iteratori
in[first + 1, last)
in order,acc
is then modified byacc = acc + *i
oracc = binary_op(acc, *i)
and is assigned to*(result + (i - first))
.Assigns to every element referred to by iteratori
in the range[result,result + (last - first))
a value correspondingly equal to((...(*first + *(first + 1)) + ...) + *(first + (i - result)))
orbinary_op(binary_op(..., binary_op(*first, *(first + 1)),...), *(first + (i - result)))
Change 27.10.7 [partial.sum]/3 as indicated:
Complexity: Exactly
max((last - first) - 1, 0)
applications ofthe binary operation.
binary_op
Change 27.10.7 [partial.sum]/4 as indicated:
Requires:
VT
shall be constructible from the type of*first
, the result ofacc + *i
orbinary_op(acc, *i)
shall be implicitly convertible toVT
, and the result of the expressionacc
shall be writable to theresult
output iterator. In the ranges[first,last]
and[result,result + (last - first)]
[..]
Change 27.10.12 [adjacent.difference]/1 as indicated:
Effects: Let
VT
beInputIterator
's value type. For a nonempty range, initializes an accumulatoracc
of typeVT
with*first
and performs*result = acc
. For every iteratori
in[first + 1, last)
in order, initializes a valueval
of typeVT
with*i
, assigns the result ofval - acc
orbinary_op(val, acc)
to*(result + (i - first))
and modifiesacc = std::move(val)
.Assigns to every element referred to by iteratori
in the range[result + 1, result + (last - first))
a value correspondingly equal to*(first + (i - result)) - *(first + (i - result) - 1)
orbinary_op(*(first + (i - result)), *(first + (i - result) - 1)).
result gets the value of *first.
Change 27.10.12 [adjacent.difference]/2 as indicated:
Requires:
VT
shall beMoveAssignable
([moveassignable]) and shall be constructible from the type of*first
. The result of the expressionacc
and the result of the expressionval - acc
orbinary_op(val, acc)
shall be writable to theresult
output iterator. In the ranges[first,last]
[..]
Change 27.10.12 [adjacent.difference]/5 as indicated:
Complexity: Exactly
max((last - first) - 1, 0)
applications ofthe binary operation.binary_op