std::transform_inclusive_scan() algorithm

od C++20

// (1)
template< class InputIt, class OutputIt, class BinaryOperation, class UnaryOperation >
constexpr OutputIt transform_inclusive_scan( InputIt first, InputIt last, OutputIt d_first, BinaryOperation binary_op,
                                             UnaryOperation unary_op );

// (2) (3)
template< class InputIt, class OutputIt, class BinaryOperation, class UnaryOperation, class T >
constexpr OutputIt transform_inclusive_scan( InputIt first, InputIt last, OutputIt d_first, BinaryOperation binary_op,
                                             UnaryOperation unary_op, T init );

// (3) (2)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryOperation, class UnaryOperation >
ForwardIt2 transform_inclusive_scan( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first,
                                     BinaryOperation binary_op, UnaryOperation unary_op );

// (4)
template<
  class ExecutionPolicy,
  class ForwardIt1,
  class ForwardIt2,
  class BinaryOperation,
  class UnaryOperation,
  class T
>
ForwardIt2 transform_inclusive_scan( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first,
                                     BinaryOperation binary_op, UnaryOperation unary_op, T init );

od C++17

// (1)
template< class InputIt, class OutputIt, class BinaryOperation, class UnaryOperation >
OutputIt transform_inclusive_scan( InputIt first, InputIt last, OutputIt d_first, BinaryOperation binary_op,
                                   UnaryOperation unary_op );

// (2) (3)
template< class InputIt, class OutputIt, class BinaryOperation, class UnaryOperation, class T >
OutputIt transform_inclusive_scan( InputIt first, InputIt last, OutputIt d_first, BinaryOperation binary_op,
                                   UnaryOperation unary_op, T init );

// (3) (2)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryOperation, class UnaryOperation >
ForwardIt2 transform_inclusive_scan( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first,
                                     BinaryOperation binary_op, UnaryOperation unary_op );

// (4)
template<
  class ExecutionPolicy,
  class ForwardIt1,
  class ForwardIt2,
  class BinaryOperation,
  class UnaryOperation,
  class T
>
ForwardIt2 transform_inclusive_scan( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first,
                                     BinaryOperation binary_op, UnaryOperation unary_op, T init );

Transforms each element in the range [first; last) with unary_op, then computes an inclusive prefix sum operation using binary_op over the resulting range, optionally with init as the initial value, and writes the results to the range beginning at d_first.

"inclusive" means that the ith input element is included in the ith sum.

In other words, the summation operations may be performed in arbitrary order, and the behavior is nondeterministic if binary_op is not associative.

Formally, assigns through each iterator i in [d_first; d_first + (last - first)) the value of the generalized noncommutative sum of:

• (1, 3) unary_op(*j)... for every j in [first; first + (i - d_first + 1)) over binary_op,
• (2, 4) init, unary_op(*j)... for every j in [first; first + (i - d_first + 1)) over binary_op,

The generalized sum GSUM(op, a1, ..., aN) is defined as follows:

• If N = 1, a1

• If N > 1, op(GSUM(op, a1, ..., aK), GSUM(op, aM, ..., aN)) for any K where 1 < K + 1 = M ≤ N

• (4 - 6) Same as (1 - 3), but executed according to policy.

  Overload Resolution

  These overloads participate in overload resolution only if std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> is true.  (do C++20) std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> is true.  (od C++20)

Undefined Behaviour

The behavior is undefined

if unary_op and binary_op invalidate iterators (including the end iterators) or subranges, or modify elements in the ranges [first; last) or [d_first; d_first + (last - first)).

Parameters

first last	The range of elements to apply the algorithm to.
d_first	The beginning of the destination range, may be equal to first.
init	The initial value of the generalized sum.
policy	The execution policy to use. See execution policy for details.
inclusive_scan	Unary FunctionObject that will be applied to each element of the input range. The return type must be acceptable as input to binary_op.
transform	Binary FunctionObject that will be applied in to the result of unary_op, the results of other binary_op, and init.

Type requirements

InputIt	LegacyInputIterator
OutputIt	LegacyOutputIterator
ForwardIt1 ForwardIt2	LegacyForwardIterator
T	MoveConstructible

• If init is not provided, decltype(first)'s value type must be MoveConstructible. The following expressions must be convertible to decltype(first)'s value type:

  • binary_op(unary_op(*first), unary_op(*first))

• T (if init is provided) must meet the requirements of MoveConstructible. The following expressions must be convertible to decltype(T):

  • binary_op(init, unary_op(*first))
  • binary_op(init, init)
  • binary_op(unary_op(*first), unary_op(*first))

Return value

Iterator to the element past the last element written.

Complexity

O(last - first) applications of each of binary_op and unary_op.

Exceptions

The overloads with a template parameter named ExecutionPolicy report errors as follows:

• If execution of a function invoked as part of the algorithm throws an exception and ExecutionPolicy is one of the standard policies, std::terminate is called. For any other ExecutionPolicy, the behavior is implementation-defined.
• If the algorithm fails to allocate memory, std::bad_alloc is thrown.

Notes

unary_op is not applied to init.

The parameter init appears last, differing from std::transform_exclusive_scan, because it is optional for this function.

Examples

Main.cpp

#include <functional>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>

int main()
{
  std::vector data {3, 1, 4, 1, 5, 9, 2, 6};

  auto times_10 = [](int x) { return x * 10; };

  std::cout << "10 times exclusive sum: ";
  std::transform_exclusive_scan(data.begin(), data.end(),
				std::ostream_iterator<int>(std::cout, " "),
				0, std::plus<int>{}, times_10);
  std::cout << "\n10 times inclusive sum: ";
  std::transform_inclusive_scan(data.begin(), data.end(),
				std::ostream_iterator<int>(std::cout, " "),
				std::plus<int>{}, times_10);
}

Possible output

10 times inclusive sum: 0 30 40 80 90 140 230 250 
10 times inclusive sum: 30 40 80 90 140 230 250 310