1. Overview
For over a decade, the C++ standard library algorithms in the <numeric>
header have had insufficient or unclear type requirements. This paper
identifies some of the issues and proposes potential solutions.
This chart provides an
overview of the current state of the type requirements of the <numeric>
algorithms.
This proposal is not intended to change the existing design, specify any
previous unspecified behavior which major implementations do not already
conform to, or remove functionality. It simply clarifies and improves the
specification of the <numeric>
algorithms.
1.1. Kinds of Algorithms in <numeric>
There are three kinds of algorithms in <numeric>
:

accumulate
,inner_product
,partial_sum
andadjacent_difference
have "inorderaccumulator" style wording. 
exclusive_scan
,inclusive_scan
,transform_exclusive_scan
,transform_inclusive_scan
are specified usingGENERALIZED_NONCOMMUTATIVE_SUM
. 
reduce
,transform_reduce
are specified viaGENERALIZED_SUM
.
1.2. InOrderAccumulator Algorithms
The wording for all of these algorithms fits the following pattern:

Create an
acc
object which is initialized withinit
if the algorithm signature contains an initial value parameter and*first
otherwise. 
For (the) iterator(s) in the range(s) in order, modify
acc
by applying a binary update operation which takesacc
and the dereferenced value(s) of the iterator(s) as arguments: e.g.acc = binary_op(acc, *i)
.
The ordering requirement is necessary to ensure that these algorithms are welldefined for nonassociative and/or noncommutative operations, such as floatingpoint addition and multiplication (nonassociative and commutative), and subtraction (nonassociative and noncommutative).
Currently, the wording forces each iteration to depend on the prior iteration to ensure the correct ordering of accumulation. This introduces a loopcarried dependency that makes it impossible to parallelize.
1.3. GENERALIZED_NONCOMMUTATIVE_SUM
and GENERALIZED_SUM
Algorithms
To parallelize these operations, we need to be able to reorder applications of the operations, partition the workload into subtasks and then combine the results of the subtasks together using the operator.
This, however, would give a nondeterministic result for nonassociative or noncommutative operations; for example, floating point arithmetic.
In addition to adding entirely new <numeric>
algorithms, the
Parallelism TS introduced new algorithms which perform the same operations as accumulate
, inner_product
and partial_sum
, but have weaker constraints
that allow parallelization:

reduce
is a parallelizable variant ofaccumulate
andtransform_reduce
is a parallelizable variantinner_product
. They may produce nondeterministic results for nonassociative or noncommutative operations. 
inclusive_scan
is a parallelizable variant ofpartial_sum
. It may produce nondeterministic results for nonassociative operations, but is fine for noncommutative operations.
These <numeric>
algorithms are specified in [numerics.defns] using GENERALIZED_NONCOMMUTATIVE_SUM
and GENERALIZED_SUM
:
24.2 Definitions [numerics.defns]DefineGENERALIZED_NONCOMMUTATIVE_SUM(op, a1, ..., aN)
as follows:
a1
whenN
is1
, otherwise eitherop(GENERALIZED_NONCOMMUTATIVE_SUM(op, a1, ..., aK), GENERALIZED_NONCOMMUTATIVE_SUM
for anyK
where1 < K + 1 = M ≤ N
, orDefineGENERALIZED_SUM(op, b1, ..., bN)
whereb1, ..., bN
may be any permutation ofa1, ..., aN
.
This definition allows:

Arbitrary, nested partitioning of input elements for both
GENERALIZED_NONCOMMUTATIVE_SUM
andGENERALIZED_SUM
. 
Arbitrary reordering of input elements for
GENERALIZED_SUM
.
2. What Should the Intermediate Type Be?
During computation of the final result, a <numeric>
algorithm needs to store the result of accumulation thus far in temporary
objects. The intermediate type is the type of these objects. Importantly,
these temporary objects are passed as the first argument to the binary
operator. For the accumulatorstyle <numeric>
algorithms
(accumulate
, inner_product
, partial_sum
, adjacent_difference
), the
intermediate type is the type of the accumulator object acc
.
The intermediate type is only clearly specified for 2 of the 10 <numeric>
algorithms. Determining and specifiying the
intermediate type for these algorithms is our first step because the type
requirements all revolve around the intermediate type.
2.1. Intermediate Type for Ordered <numeric>
Algorithms with Initial Value Parameters
accumulate
and inner_product
are described by the standard in [accumulate] and [inner.product]. Today, the
definitions don’t make it clear what the intermediate type is.
Both algorithms have a requirement that the type of the initial value
parameter (T
) be CopyConstructible
and CopyAssignable
, implying that the
accumulator object is intended to be of type T
. Both libc++ and libstdc++
use T
as the type of the accumulator object for these 2 algorithms.
Using T
both has upsides:
vector<int> i{INT_MAX, INT_MAX}; big_int bi = accumulate(d.begin(), d.end(), big_int(0)); // big_int is an arbitraryprecision integer class which uses dynamic storage. // bi == 2 * INT_MAX.
and downsides:
vector<double> d{0.5, 0.5}; double r = accumulate(d.begin(), d.end(), 0); // r == 0, not 1. The accumulator’s type was int, since the type of the literal // 0 is int.
Alternative choices for the intermediate type are:

Determine some common type between
T
,InputIterator
's value type, and the result ofbinary_op
(or the relevant operator) and use that as the intermediate type. As discussed in §2.2 Intermediate Type for Ordered <numeric> Algorithms without Initial Value Parameters, it may be difficult to do this if binary_op is overloaded in a certain manner and it may make it harder for users to determine what the intermediate type will be. 
Use the
InputIterator
's value type as the intermediate type. This would make the example of accumulating avector<double>
produce a result that might be closer to what the user intended, but it would also remove the functionality desired by the user in thebig_int
example.
Switching to either of these alternatives would force implementations to make breaking changes, and neither option seems particular attractive.
I suggest adopting the following design. It is simple and clear to both users and implementators:
<numeric>
algorithms which take an initial value parameter
and initial value type template parameter will use the initial value type as
the intermediate type.
2.2. Intermediate Type for Ordered <numeric>
Algorithms without Initial Value Parameters
As we mentioned earlier, the type of the accumulator object (the intermediate
type) is explicitly specified for only 2 of the 10 <numeric>
algorithms: partial_sum
, which is specified in [partial.sum],
and adjacent_difference
, which is specified in [adjacent.difference]..
The only alternative to using InputIterator
's value type for the intermediate
type that I could think of was computing the common type of the InputIterator
's value type and the result of the righthand side of the
repeated assignment to acc, e.g.
using it_value_type = typename iterator_traits<InputIterator>::value_type; // The accumulator type, determined via common_type. using acc_common_type = common_type_t< it_value_type , decltype(binary_op(it_value_type{}, *i)) // Or acc + *i, or acc  *i, etc. >
If the InputIterator
's value type is convertible to the result of the binary
operator, but the result of the binary operator is not convertible to the InputIterator
's value type, then the binary operator signature we tested with decltype
cannot be called with acc_common_type
as its first argument:
struct A { }; struct B { operator A(); }; struct binary_op_type { A operator() (B, B); }; binary_op_type binary_op; using it_value_type = B; using acc_common_type = common_type_t< it_value_type , decltype(binary_op(it_value_type{}, it_value_type{})) >; int main() { binary_op(acc_common_type{}, it_value_type{}); // COMPILE FAIL. }
Even worse, we could have a binary_op
like this:
struct binary_op_type { A operator() (B, B); int operator() (A, B); };
The above binary_op
can now be called with acc_common_type
as the first
argument, however that overload returns a different type which we did not
include in our common type computation. Nor could we have, as an iterative
TMP search for a common type would be dangerous in the face of potential
cycles:
struct binary_op_type { A operator() (B, B); // New expression binary_op(A{}, B{}) to check... B operator() (A, B); // New expression binary_op(B{}, B{}) to check... };
This might be viable if we constrain binary_op
in some fashion, but it is not
clear to me how that could be done. More importantly, determining a common type
to use for the intermediate type is likely the wrong thing to do because it means
the user does not have a clear answer to the question "What type will you use to
perform the accumulation?".
Since the OutputIterator
has no value type by virture of being an output
iterator, I cannot think of any other options for the intermediate type for the
algorithms without initial value parameters other than the status quo of the InputIterator
's value type.
There is, however, a regretable lack of functionality with the status quo prior to C++17:
vector<float> f{FLT_MAX, FLT_MAX}; vector<double> d; partial_sum(f.begin(), f.end(), back_inserter(d)); // d[1] == inf since the intermediate type is float (the value type of // vector<float>::iterator).
Pre C++17, there is no way for users to specify that partial_sum
should use
a particular type as the intermediate type instead of the InputIterator
's
value type. In C++17, there are two ways this can be done if ordered
is not needed. inclusive_scan
, the unordered counterpart of partial_sum
,
has overloads which take an initial value:
vector<float> f{FLT_MAX, FLT_MAX}; vector<double> d; inclusive_scan(f.begin(), f.end(), back_inserter(d), plus<>{}, double{0.0}); // d[1] == 2 * FLT_MAX
or with transform_inclusive_scan
using a transform function that converts
its argument and returns the desire type:
vector<float> f{FLT_MAX, FLT_MAX}; vector<double> d; transform_inclusive_scan(f.begin(), f.end(), back_inserter(d) , plus<>{} , [](float f) { return double{f}; }); // d[1] == 6e38F.
A possible postC++17 addition of partial_sum
signatures accepting an initial
value parameter would complete this functionality.
I believe the best option is to keep the existing behavior for <numeric>
algorithm which do not take an initial value
parameter. Making any change to the type of the accumulator object would be a
breaking change as parital_sum
and adjacent_difference
are currently
specified to use accumulator objects whose type is the InputIterator
's value
type, and none of the alternatives offer much benefit. The current behavior is
clear and easy to understand.
So, I propose:
<numeric>
algorithms which do not take an initial value
parameter and initial value type template parameter will use the value type of
their input iterator type as the intermediate type.
2.3. Intermediate Type for Unordered <numeric>
Algorithms
Unlike the ordered algorithms, the new unordered algorithms from the
Parallelism TS v1 do not use inorderaccumulator wording. Instead, they are
all specified in terms of GENERALIZED_NONCOMMUTATIVE_SUM
and GENERALIZED_SUM
(§1.3 GENERALIZED_NONCOMMUTATIVE_SUM and GENERALIZED_SUM Algorithms).
As an example of how these definitions are used, let’s take a look at reduce
,
which is defined in [reduce].
This definition does not clearly state what the intermediate type (e.g. the
return type of GENERALIZED_NONCOMMUTATIVE_SUM
and GENERALIZED_SUM
) should
be.
This is particularly scary in the face of the arbitrary reordering and partitioning
that GENERALIZED_NONCOMMUTATIVE_SUM
and GENERALIZED_SUM
allow. Consider:
vector<int> i{INT_MAX, INT_MAX, INT_MAX, INT_MAX}; big_int bi = reduce(d.begin(), d.end(), big_int(0)); // Possible result // GSUM == GENERALIZED_SUM, GNSUM == GENERALIZED_NONCOMMUTATIVE_SUM // // bi = GSUM(operator+, big_int(0), d[0], d[1], d[2], d[3]); // = operator+(GNSUM(operator+, d[0], big_int(0)) // , GNSUM(operator+, d[1], d[2], d[3])); // = operator+( // operator+( // GNSUM(operator+, d[0]), GNSUM(operator+, big_int(0)) // ) // , operator+( // GNSUM(operator+, d[1], d[2]), GNSUM(operator+, d[3]) // ) // ); // = operator+( // operator+(d[0], big_int(0)) // , operator+( // operator+(GNSUM(operator+, d[1]), GNSUM(operator+, d[2])), d[3] // ) // ); // = operator+( // operator+(d[0], big_int(0)) // , operator+(operator+(d[1], d[2]), d[3]) // ); // = ((d[0] + big_int(0)) + ((d[1] + d[2]) + d[3])); // = ((d[0] + big_int(0)) + ((int{INT_MAX} + int{INT_MAX}) + d[3])); // = ((d[0] + big_int(0)) + (int{2} + int{INT_MAX})); // = ((int{INT_MAX} + big_int(0)) + int{INT_MAX  2}); // = (big_int(INT_MAX) + int{INT_MAX  2}); // = big_int(INT_MAX + INT_MAX  2); // // bi = 2 * INT_MAX  2; // Instead of 4*INT_MAX
The above is just one possible result that reduce
could produce in such an
example. Note that in addition to performing some of the calculations with int
as the intermediate type, reduce
also called binary_op
with the
initial value type as the second argument and the element from the sequence
(whose type is the InputIterators
's value type) as the first argument.
The ordered algorithms always pass intermediate objects as the first argmuent
to the binary operator. It seems sensible that we should use the same rules I
suggested for the ordered algorithms (§2.4 Intermediate Type Policy for <numeric> Algorithms). Note that the N == 1
case intentionally does not convert to IntermediateType
,
The question is how should this be done? The first thing I tried was to simply
add a type parameter to GENERALIZED_NONCOMMUTATIVE_SUM
and GENERALIZED_SUM
and
specify that the type parameter is the return type. However, because of the
recursive definition, this approach would force every input element to be
converted to IntermediateType
. Revisiting our example of reducing into a big_int
illustrates the problem:
vector<int> i(N, INT_MAX); // N is divisible by 2. big_int bi = reduce(par, d.begin(), d.end(), big_int(0)); // big_int is an arbitraryprecision integer class which uses dynamic storage.
Suppose we execute this code on a system with two cores and our implementation decides to use two threads. We would want the following to happen:

Partition the work into two chunks  say init (which is
big_int(0)
) andd[0]
throughd[N / 2  1]
in the first chunk, andd[N / 2]
throughd[N  1]
in the second trunk. 
On one thread, sequentially accumulate the first chunk into
init
(passed by value, so we can use it), using the accumulatorinorder semantics. E.g. modifyinit
withinit = binary_op(acc, d[i])
for everyi
in[0, N / 2)
in order. 
On the second thread, create an accumulator object
acc
whose type is the the type of the initial value parameter (T
) and initialize it withd[N / 2]
. Then, modifyacc
withacc = binary_op(acc, d[i])
for everyi
in[N / 2 + 1, N)
in order. Note that we excludeN / 2
since we initializedacc
with the value ofd[N / 2]
.
With the definition of reduce in C++17, we could arguably get this behavior.
Although the current definition of GENERALIZED_NONCOMMUTATIVE_SUM
and GENERALIZED_SUM
are fully recursive down to a single element, the intention
was to allow recursion to be replaced with sequential, inorderaccumulator
style semantics at an implementation’s discretion for chunks of work that will
be done on a single thread, the seq
execution policy, and inputs that an
implementation decides not to parallelize. Under the current wording, it
certainly seems like this would be an allowable asif optimization.
But the new definition I suggested would require every element to be converted
to big_int
, which we have noted is an arbitrary precision type which uses
dynamic storage. These conversions are undesirable, and arguably, unnecessary.
We only want to ensure that any time the implementation uses a temporary object
to accumulate some part of the result, that object’s type is the desired
intermediate type and a conversion happens if necessary (e.g. if the object is
not the init
parameter).
I don’t believe we can specify that behavior without changing the definitions
of GENERALIZED_NONCOMMUTATIVE_SUM
and GENERALIZED_SUM
to explicitly allow
the sequential accumulation of subpartitions at the implementation’s
discretion.
2.4. Intermediate Type Policy for <numeric>
Algorithms
In summary:
The intermediate type is the initial value type if there is an
initial value, and the value type of the InputIterator
otherwise.
3. Type Requirements
Now that we have defined a clear policy for what the intermediate type should
be for each <numeric>
algorithm
(§2.4 Intermediate Type Policy for <numeric> Algorithms), we can describe their requirements:

Operators shall neither modify elements nor invalidate iterators or subranges in the iterator ranges specified by their parameters.

The intermediate type shall be CopyConstructible (inorderaccumulator algorithms that take an initial value), constructible from
*first
(inorderaccumulator algorithms that do not take an initial value), or constructible fromop(GENERALIZED_NONCOMMUTATIVE_SUM(op, a1, ..., aK), GENERALIZED_NONCOMMUTATIVE_SUM(op, aM, ..., aN))
(GENERALIZED_NONCOMMUTATIVE_SUM
andGENERALIZED_SUM
algorithms). This requirement comes from the initialization of the accumulator object (inorder accumulator algorithms) or from the conversion toIntermediateType
(GENERALIZED_NONCOMMUTATIVE_SUM
andGENERALIZED_SUM
algorithms). 
The right hand side of the update expression must be convertible to the intermediate type (all inorderaccumulator algorithms). This requirement comes from the update expression (the right hand side of
acc = binary_op(acc, *i)
). 
The intermediate type must be CopyAssignable (all inorderaccumulator algorithms except adjacent_difference) or MoveAssignable (adjacent_difference). This requirement comes from the update expression (the assignment in
acc = binary_op(acc, *i)
). 
The intermediate type shall be writable to the result output iterator (for algorithms which take an output range). This requirement comes from the write to the output iterator that is performed each iteration in these algorithms.
For the function objects, we’ve already specified the requirements for what the return type of the invocations of binary_op
should be. We just need to require that:

binary_op
,binary_op1
,binary_op2
andunary_op
are function objects. 
binary_op(acc, *i)
(all inorderaccumulator algorithms),acc + *i
(accumulate
,inner_product
andpartial_sum
),acc  *i
(adjacent_difference
),binary_op1(acc, binary_op2(*i1, *i2))
(inner_product
) andacc + (*i1) * (*i2)
are required. 
The function object requirements from the new algorithms are in
GENERALIZED_NONCOMMUTATIVE_SUM
andGENERALIZED_SUM
:
If
a1, ..., aN
are of the same type (e.g. the homogeneous elements of an iterator range), thenop(a1, a1)
is the only signature required byGENERALIZED_NONCOMMUTATIVE_SUM
andGENERALIZED_SUM
. This covers the new algorithms which do not take an initial value type. 
If
a1
is of one type anda2, ..., aN
are of the same type (e.g. an initial valuea1
and the homogeneous elements of an iterator rangea2, ..., aN
), thenop(a2, a1)
,op(a1, a2)
,op(a2, a2)
andop(a1, a1)
are required byGENERALIZED_SUM
andop(a2, a1)
,op(a2, a2)
andop(a1, a1)
are required forGENERALIZED_NONCOMMUTATIVE_SUM
. This covers the new algorithms which do take an initial value type.

While the new algorithms introduced by the Parallelism TS do have the necessary
requirements forbidding modification of iterator ranges, the ranges used are
not fully closed like the rest of the <numeric>
algorithms.
There is one additional outlier case. reduce
has a signature which only takes
two InputIterator
's and is defined as equivalent to return reduce(first, last, typename iterator_traits<InputIterator>::value_type{});
. This requires
that InputIterator
's value type be DefaultConstructible. accumulate
does
not have such a signature (by design, I believe). Ideally, I’d like to remove
this signature, but I think it is too late to do so. I’d like to add the
missing requirement, at least.
4. Wording
Note: The following changes are relative to the postRapperswil 2018 working draft of ISO/IEC 14882, ([N4762]).
Note: The � character is used to denote a placeholder number which shall be selected by the editor.
Modify 24.2 [numerics.defns] as follows:
24.2 Definitions [numerics.defns]LetIntermediateType
be a type. Leta1, ..., aN
andb1, ..., bN
be expressions whose types are implicitly convertible toIntermediateType
.IntermediateType
shall be Cpp17MoveConstructible (Table 25), Cpp17MoveAssignable (Table 27), and constructible froma1
.Letop
is a binary function object (19.14 [function.object]) taking two arguments, the first whose type isIntermediateType
and second whose type is implicitly convertible toIntermediateType
, and returns a value whose type is implicitly convertible toIntermediateType
.Define the expressionGENERALIZED_NONCOMMUTATIVE_SUM<IntermediateType>(op, a1, ..., aN)
as follows:
IntermediateType(a1)
whenN
is1
, otherwise eitherIntermediateType(op(GENERALIZED_NONCOMMUTATIVE_SUM<IntermediateType>(op, a1, ..., aK), GENERALIZED_NONCOMMUTATIVE_SUM<IntermediateType>(op, aM, ..., aN)))
for anyK
where1 < K + 1 = M ≤ N
, or initialize the accumulator
acc
whose type isIntermediateType
with the valuea1
, modify it withacc = op(move(acc), GENERALIZED_NONCOMMUTATIVE_SUM<IntermediateType>(op, aJ, ..., aK))
for every[J, K)
in[2, X), ..., [Y, N)
where2 < X + 1 < ... < Y + 1 ≤ N
in order, and then returnacc
.DefineGENERALIZED_SUM<IntermediateType>(op, a1, ..., aN)
asGENERALIZED_NONCOMMUTATIVE_SUM<IntermediateType>(op, b1, ..., bN)
whereb1, ..., bN
may be any permutation ofa1, ..., aN
.
Modify 23.9.1 [accumulate] as follows:
23.9.1 Accumulate [accumulate]template<class InputIterator, class T> T accumulate(InputIterator first, InputIterator last, T init); template <class InputIterator, class T, class BinaryOperation> T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op);Requires:T
shall satisfy the Cpp17MoveCopyConstructible (Table 2526) and Cpp17MoveCopyAssignable (Table 2728) requirements. The result of the expressionacc + *i
orbinary_op(std::move(acc), *i)
shall be implicitly convertible toT
. In the range[first, last]
,binary_op
shall neither modify elements nor invalidate iterators or subranges.^{240}Effects: Computes its result by initializing the accumulatoracc
, whose type isT
, with the initial valuemove(init)
and then modifies it withacc = std::move(acc) + *i
oracc = binary_op(std::move(acc), *i)
for every iteratori
in the range[first, last)
in order.^{241}^{240)} The use of fully closed ranges is intentional.
^{241)}
accumulate
is similar to the APL reduction operator and Common Lisp reduce function, but it avoids the difficulty of defining the result of reduction on an empty sequence by always requiring an initial value.
Modify 23.9.2 [reduce] as follows:
23.9.2 Reduce [reduce]template<class InputIterator> typename iterator_traits<InputIterator>::value_type reduce(InputIterator first, InputIterator last);Effects: Equivalent to:return reduce(first, last, typename iterator_traits<InputIterator>::value_type{});Requires:iterator_traits<InputIterator>::value_type
shall satisfy the requirements of Cpp17DefaultConstructible (Table 20)template<class ExecutionPolicy, class ForwardIterator> typename iterator_traits<ForwardIterator>::value_type reduce(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last);Effects: Equivalent to:return reduce(std::forward<ExecutionPolicy>(exec), first, last, typename iterator_traits<ForwardIterator>::value_type{});Requires:iterator_traits<ForwardIterator>::value_type
shall satisfy the requirements of Cpp17DefaultConstructible (Table 20)template<class InputIterator, class T> T reduce(InputIterator first, InputIterator last, T init);Effects: Equivalent to:return reduce(first, last, init, plus<>());template<class ExecutionPolicy, class ForwardIterator, class T> T reduce(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, T init);Effects: Equivalent to:return reduce(std::forward<ExecutionPolicy>(exec), first, last, init, plus<>());template<class InputIterator, class T, class BinaryOperation> T reduce(InputIterator first, InputIterator last, T init, BinaryOperation binary_op); template<class ExecutionPolicy, class ForwardIterator, class T, class BinaryOperation> T reduce(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, T init, BinaryOperation binary_op);Requires:binary_op
shall neither invalidate iterators or subranges, nor modify elements in the range[first, last]
.
T
shall be Cpp17MoveConstructible (Table 25). All of
binary_op(init, *first)
,binary_op(*first, init)
,binary_op(init, init)
, andbinary_op(*first, *first)
shall be convertible toT
.binary_op
shall neither invalidate iterators or subranges, nor modify elements in the range[first, last]
.Returns:GENERALIZED_SUM<T>(binary_op, init, *i, ...)
for everyi
in[first, last)
.Complexity:O(last  first)
applications ofbinary_op
.[ Note: The difference betweenreduce
andaccumulate
is thatreduce
appliesbinary_op
in an unspecified order, which yields a nondeterministic result for nonassociative or noncommutativebinary_op
such as floatingpoint addition. – end note ]
Modify 23.9.3 [inner.product] as follows:
23.9.3 Inner product [inner.product]template<class InputIterator1, class InputIterator2, class T> T inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init); template<class InputIterator1, class InputIterator2, class T, class BinaryOperation1, class BinaryOperation2> T inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init, BinaryOperation1 binary_op1, BinaryOperation2 binary_op2);Requires:T
shall satisfy the Cpp17MoveCopyConstructible (Table 2526) and Cpp17MoveCopyAssignable (Table 2728) requirements. The result of the expressionstd::move(acc) + (*i1) * (*i2)
orbinary_op1(std::move(acc), binary_op2(*i1, *i2))
shall be implicitly convertible toT
. In the ranges[first1, last1]
and[first2, first2 + (last1  first1)]
binary_op1
andbinary_op2
shall neither modify elements nor invalidate iterators or subranges.^{242}Effects: Computes its result by initializing the accumulatoracc
, whose type isT
, with the initial valuemove(init)
and then modifying it withacc = std::move(acc) + (*i1) * (*i2)
oracc = binary_op1(std::move(acc), binary_op2(*i1, *i2))
for every iteratori1
in the range[first1, last1)
and iteratori2
in the range[first2, first2 + (last1  first1))
in order.^{242)} The use of fully closed ranges is intentional.
Modify 23.9.4 [transform.reduce] as follows:
23.9.4 Transform reduce [transform.reduce]template<class InputIterator1, class InputIterator2, class T> T transform_reduce(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init);Effects: Equivalent to:return transform_reduce(first1, last1, first2, init, plus<>(), multiplies<>());template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class T> T transform_reduce(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, T init);Effects: Equivalent to:return transform_reduce(std::forward<ExecutionPolicy>(exec), first1, last1, first2, init, plus<>(), multiplies<>());template<class InputIterator1, class InputIterator2, class T, class BinaryOperation1, class BinaryOperation2> T transform_reduce(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init, BinaryOperation1 binary_op1, BinaryOperation2 binary_op2); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class T, class BinaryOperation1, class BinaryOperation2> T transform_reduce(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, T init, BinaryOperation1 binary_op1, BinaryOperation2 binary_op2);Requires: Neitherbinary_op1
norbinary_op2
shall invalidate subranges, or modify elements in the ranges[first1, last1]
and[first2, first2 + (last1  first1)]
.
T
shall be Cpp17MoveConstructible (Table 25). All of
shall be convertible to T.
binary_op1(init, init)
,binary_op1(init, binary_op2(*first1, *first2))
,binary_op1(binary_op2(*first1, *first2), init)
, andbinary_op1(binary_op2(*first1, *first2), binary_op2(*first1, *first2))
 Neither
binary_op1
norbinary_op2
shall invalidate subranges, or modify elements in the ranges[first1, last1]
and[first2, first2 + (last1  first1)]
.Returns:GENERALIZED_SUM<T>(binary_op1, init, binary_op2(*i, *(first2 + (i  first1))), ...)
for every iterator
i
in[first1, last1)
.Complexity:O(last1  first1)
applications each ofbinary_op1
andbinary_op2
.template<class InputIterator, class T, class BinaryOperation, class UnaryOperation> T transform_reduce(InputIterator first, InputIterator last, T init, BinaryOperation binary_op, UnaryOperation unary_op); template<class ExecutionPolicy, class ForwardIterator, class T, class BinaryOperation, class UnaryOperation> T transform_reduce(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, T init, BinaryOperation binary_op, UnaryOperation unary_op);Requires: Neitherunary_op
norbinary_op
shall invalidate subranges, or modify elements in the ranges[first1, last1]
.
T
shall be Cpp17MoveConstructible (Table 25). All of
shall be convertible to T.
binary_op(init, init)
,binary_op(init, unary_op(*first))
,binary_op(unary_op(*first), init)
, andbinary_op(unary_op(*first), unary_op(*first1, *first2))
 Neither
unary_op
norbinary_op
shall invalidate subranges, or modify elements in the ranges[first1, last1]
.Returns:GENERALIZED_SUM<T>(binary_op, init, unary_op(*i), ...)
for every iterator i in [first, last).Complexity: O(last  first) applications each of unary_op and binary_op.[ Note:transform_reduce
does not applyunary_op
toinit
. — end note ]
Modify 23.9.5 [partial.sum] as follows:
23.9.5 Partial sum [partial.sum]template<class InputIterator, class OutputIterator> OutputIterator partial_sum( InputIterator first, InputIterator last, OutputIterator result); template<class InputIterator, class OutputIterator, class BinaryOperation> OutputIterator partial_sum( InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op);Requires:InputIterator
's value type shall be Cpp17CopyConstructible (Table 26) and Cpp17MoveAssignable (Table 27) constructible from the type of*first
. The result of the expressionstd::move(acc) + *i
orbinary_op(std::move(acc), *i)
shall be implicitly convertible toInputIterator
's value type.acc
shall be writable (22.2.1 [iterator.requirements.general]) to theresult
output iterator. In the ranges[first, last]
and[result, result + (last  first)]
binary_op
shall neither modify elements nor invalidate iterators or subranges.^{243}Effects: For a nonempty range, the function creates an accumulatoracc
whose type isInputIterator
's value type, initializes it with*first
, and assigns the result to*result
. For every iteratori
in[first + 1, last)
in order,acc
is then modified byacc = std::move(acc) + *i
oracc = binary_op(std::move(acc), *i)
and the result is assigned to*(result + (i  first))
.Returns:result + (last  first)
.Complexity: Exactly(last  first)  1
applications of the binary operation.Remarks:result
may be equal tofirst
.^{243)} The use of fully closed ranges is intentional.
Modify 23.9.6 [exclusive.scan] as follows:
23.9.6 Exclusive scan [exclusive.scan]template<class InputIterator, class OutputIterator, class T> OutputIterator exclusive_scan(InputIterator first, InputIterator last, OutputIterator result, T init);Effects: Equivalent to:return exclusive_scan(first, last, result, init, plus<>());template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class T> ForwardIterator2 exclusive_scan(ExecutionPolicy&& exec, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result, T init);Effects: Equivalent to:return exclusive_scan(std::forward<ExecutionPolicy>(exec), first, last, result, init, plus<>());template<class InputIterator, class OutputIterator, class T, class BinaryOperation> OutputIterator exclusive_scan(InputIterator first, InputIterator last, OutputIterator result, T init, BinaryOperation binary_op); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class T, class BinaryOperation> ForwardIterator2 exclusive_scan(ExecutionPolicy&& exec, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result, T init, BinaryOperation binary_op);Requires:
T
shall be Cpp17MoveConstructible (Table 25). All of
binary_op(init, init)
,binary_op(init, *first)
, andbinary_op(*first, *first)
shall be convertible toT
.T
shall be writable (22.2.1 [iterator.requirements.general]) to theresult
output iterator.binary_op
shall neither invalidate iterators or subranges, nor modify elements in the range[first, last]
or[result, result + (last  first)]
.Effects: For each integerK
in[0, last  first)
assigns throughresult + K
the value of:GENERALIZED_NONCOMMUTATIVE_SUM<T>( binary_op, init, *(first + 0), *(first + 1), ..., *(first + K  1))
Returns: The end of the resulting range beginning atresult
.Complexity:O(last  first)
applications ofbinary_op
.Remarks:result
may be equal tofirst
.[ Note: The difference betweenexclusive_scan
andinclusive_scan
is thatexclusive_scan
excludes the i^{th} input element from the i^{th} sum. Ifbinary_op
is not mathematically associative, the behavior ofexclusive_scan
may be nondeterministic. — end note ]
Modify 23.9.7 [inclusive.scan] as follows:
23.9.7 Inclusive scan [inclusive.scan]template<class InputIterator, class OutputIterator> OutputIterator inclusive_scan(InputIterator first, InputIterator last, OutputIterator result);Effects: Equivalent to:return inclusive_scan(first, last, result, plus<>());template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> ForwardIterator2 inclusive_scan(ExecutionPolicy&& exec, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result);Effects: Equivalent to:return inclusive_scan(std::forward<ExecutionPolicy>(exec), first, last, result, plus<>());template<class InputIterator, class OutputIterator, class BinaryOperation> OutputIterator inclusive_scan(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class BinaryOperation> ForwardIterator2 inclusive_scan(ExecutionPolicy&& exec, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result, BinaryOperation binary_op); template<class InputIterator, class OutputIterator, class BinaryOperation, class T> OutputIterator inclusive_scan(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op, T init); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class BinaryOperation, class T> ForwardIterator2 inclusive_scan(ExecutionPolicy&& exec, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result, BinaryOperation binary_op, T init);Ifinit
is not provided,T
is the value type ofdecltype(*first)
.Requires:
 If
init
is provided,T
shall be Cpp17MoveConstructible (Table 25); otherwise,ForwardIterator1
's value type shall be Cpp17MoveConstructible. If
init
is provided, all ofbinary_op(init, init)
,binary_op(init, *first)
, andbinary_op(*first, *first)
shall be convertible toT
; otherwise,binary_op(*first, *first)
shall be convertible toForwardIterator1
's value type.T
shall be writable (22.2.1 [iterator.requirements.general]) to theresult
output iterator.binary_op
shall neither invalidate iterators or subranges, nor modify elements in the range[first, last]
or[result, result + (last  first)]
.Effects: For each integerK
in[0, last  first)
assigns throughresult + K
the value of
GENERALIZED_NONCOMMUTATIVE_SUM<T>( binary_op, init, *(first + 0), *(first + 1), ..., *(first + K))
if
init
is provided, orGENERALIZED_NONCOMMUTATIVE_SUM<T>( binary_op, *(first + 0), *(first + 1), ..., *(first + K))
otherwise.
Returns: The end of the resulting range beginning atresult
.Complexity:O(last  first)
applications ofbinary_op
.Remarks:result
may be equal tofirst
.[ Note: The difference betweenexclusive_scan
andinclusive_scan
is thatinclusive_scan
includes the i^{th} input element in the i^{th} sum. Ifbinary_op
is not mathematically associative, the behavior ofinclusive_scan
may be nondeterministic. — end note ]
Modify 23.9.8 [transform.exclusive.scan] as follows:
23.9.8 Transform exclusive scan [transform.exclusive.scan]template<class InputIterator, class OutputIterator, class T, class BinaryOperation, class UnaryOperation> OutputIterator transform_exclusive_scan(InputIterator first, InputIterator last, OutputIterator result, T init, BinaryOperation binary_op,UnaryOperation unary_op); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class T, class BinaryOperation, class UnaryOperation> ForwardIterator2 transform_exclusive_scan(ExecutionPolicy&& exec, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result, T init, BinaryOperation binary_op, UnaryOperation unary_op);Requires:
T
shall be Cpp17MoveConstructible (Table 25). All of
shall be convertible to
binary_op(init, init)
,binary_op(init, unary_op(*first))
, andbinary_op(unary_op(*first), unary_op(*first))
T
.T
shall be writable (22.2.1 [iterator.requirements.general]) to theresult
output iterator. Neither
unary_op
norbinary_op
shall invalidate iterators or subranges, nor modify elements in the range[first, last]
or[result, result + (last  first)]
.Effects: For each integerK
in[0, last  first)
assigns throughresult + K
the value of:GENERALIZED_NONCOMMUTATIVE_SUM<T>( binary_op, init, unary_op(*(first + 0)), unary_op(*(first + 1)), ..., unary_op(*(first + K  1)))
Returns: The end of the resulting range beginning atresult
.Complexity:O(last  first)
applications each ofunary_op
andbinary_op
.Remarks:result
may be equal tofirst
.[ Note: The difference betweentransform_exclusive_scan
andtransform_inclusive_scan
is thattransform_exclusive_scan
excludes the i^{th} input element from the i^{th} sum. Ifbinary_op
is not mathematically associative, the behavior ofexclusive_scan
may be nondeterministic.transform_exclusive_scan
does not applyunary_op
toinit
. — end note ]
Modify 23.9.9 [transform.inclusive.scan] as follows:
23.9.9 Transform inclusive scan [transform.inclusive.scan]template<class InputIterator, class OutputIterator, class BinaryOperation, class UnaryOperation> OutputIterator transform_inclusive_scan(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op, UnaryOperation unary_op); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class BinaryOperation, class UnaryOperation> ForwardIterator2 transform_inclusive_scan(ExecutionPolicy&& exec, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result, BinaryOperation binary_op, UnaryOperation unary_op); template<class InputIterator, class OutputIterator, class BinaryOperation, class UnaryOperation, class T> OutputIterator transform_inclusive_scan(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op, UnaryOperation unary_op, T init); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class BinaryOperation, class UnaryOperation, class T> ForwardIterator2 transform_inclusive_scan(ExecutionPolicy&& exec, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result, BinaryOperation binary_op, UnaryOperation unary_op, T init);Ifinit
is not provided,T
is the value type ofdecltype(*first)
.Requires:
 If
init
is provided,T
shall be Cpp17MoveConstructible (Table 25); otherwise,ForwardIterator1
's value type shall be Cpp17MoveConstructible. If
init
is provided, all ofshall be convertible to
binary_op(init, init)
,binary_op(init, *first)
, andbinary_op(*first, *first)
T
; otherwise,binary_op(unary_op(*first), unary_op(*first))
shall be convertible toForwardIterator1
's value type.T
shall be writable (22.2.1 [iterator.requirements.general]) to theresult
output iterator. Neither
unary_op
norbinary_op
shall invalidate iterators or subranges, nor modify elements in the range[first, last]
or[result, result + (last  first)]
.Effects: For each integerK
in[0, last  first)
assigns throughresult + K
the value of
GENERALIZED_NONCOMMUTATIVE_SUM<T>( binary_op, init, unary_op(*(first + 0)), unary_op(*(first + 1)), ..., unary_op(*(first + K)))
if
init
is provided, orGENERALIZED_NONCOMMUTATIVE_SUM<T>( binary_op, unary_op(*(first + 0)), unary_op(*(first + 1)), ..., unary_op(*(first + K)))
otherwise.
Returns: The end of the resulting range beginning atresult
.Complexity:O(last  first)
applications each ofunary_op
andbinary_op
.Remarks:result
may be equal tofirst
.[ Note: The difference betweentransform_exclusive_scan
andtransform_inclusive_scan
is thattransform_inclusive_scan
includes the i^{th} input element in the i^{th} sum. Ifbinary_op
is not mathematically associative, the behavior ofinclusive_scan
may be nondeterministic.transform_inclusive_scan
does not applyunary_op
toinit
. — end note ]
Modify 23.9.10 [adjacent.difference] as follows:
23.9.10 Adjacent difference [adjacent.difference]template<class InputIterator, class OutputIterator> OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> ForwardIterator2 adjacent_difference(ExecutionPolicy&& exec, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result); template<class InputIterator, class OutputIterator, class BinaryOperation> OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class BinaryOperation> ForwardIterator2 adjacent_difference(ExecutionPolicy&& exec, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result, BinaryOperation binary_op);LetT
be the value type ofdecltype(*first)
. For the overloads that do not take an argumentbinary_op
, letbinary_op
be an lvalue that denotes an object of typeminus<>
.Requires:
 For the overloads with no
ExecutionPolicy
,T
shall be Cpp17MoveAssignable (Table 27) and shall be constructible from the type of*first
.acc
(defined below) shall be writable (22.2.1 [iterator.requirements.general]) to theresult
output iterator. The result of the expression
binary_op(val, std::move(acc))
shall be writable to theresult
output iterator. For the overloads with an
ExecutionPolicy
, the result of the expressionsbinary_op(*first, *first)
and*first
shall be writable toresult
. For all overloads, in the ranges
[first, last]
and[result, result + (last  first)]
,binary_op
shall neither modify elements nor invalidate iterators or subranges.^{244} For the overloads with an
ExecutionPolicy
, the ranges[first, last)
and[result, result + (last  first))
shall not overlap.Effects: For the overloads with noExecutionPolicy
and a nonempty range, the function creates an accumulatoracc
of typeT
, initializes it with*first
, and assigns the result to*result
. For every iteratori
in[first + 1, last)
in order, creates an objectval
whose type isT
, initializes it with*i
, computesbinary_op(val, std::move(acc))
, assigns the result to*(result + (i  first))
, and move assigns fromval
toacc
.For the overloads with anExecutionPolicy
and a nonempty range, performs*result = *first
. Then, for everyd
in[1, last  first  1]
, performs*(result + d) = binary_op(*(first + d), *(first + (d  1)))
.Returns:result + (last  first)
.Complexity: Exactly(last  first)  1
applications of the binary operation.Remarks: For the overloads with noExecutionPolicy
,result
may be equal tofirst
.For the overloads with anExecutionPolicy
, the ranges[first, last)
and[result, result + (last  first))
shall not overlap.^{244)} The use of fully closed ranges is intentional.
4.1. Questions for LWG

Do we
std::
qualify things in library wording, likemove
andforward
? 
Do we prefer to say "
Iterator
's value type" or "typename iterator_traits<Iterator>::value_type
". 
The "use of fully closed ranges is intentional" notes are used inconsistently  should they be everywhere?