29 Numerics library [numerics]

29.8 Generalized numeric operations [numeric.ops]

29.8.1 Header <numeric> synopsis [numeric.ops.overview]

namespace std {
  // [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);

  // [reduce], reduce
  template<class InputIterator>
    typename iterator_traits<InputIterator>::value_type
      reduce(InputIterator first, InputIterator last);
  template<class InputIterator, class T>
    T reduce(InputIterator first, InputIterator last, T init);
  template<class InputIterator, class T, class BinaryOperation>
    T reduce(InputIterator first, InputIterator last, T init,
             BinaryOperation binary_op);
  template<class ExecutionPolicy, class ForwardIterator>
    typename iterator_traits<ForwardIterator>::value_type
      reduce(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
             ForwardIterator first, ForwardIterator last);
  template<class ExecutionPolicy, class ForwardIterator, class T>
    T reduce(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
             ForwardIterator first, ForwardIterator last, T init);
  template<class ExecutionPolicy, class ForwardIterator, class T, class BinaryOperation>
    T reduce(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
             ForwardIterator first, ForwardIterator last, T init,
             BinaryOperation binary_op);

  // [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);

  // [transform.reduce], transform reduce
  template<class InputIterator1, class InputIterator2, class T>
    T transform_reduce(InputIterator1 first1, InputIterator1 last1,
                       InputIterator2 first2,
                       T init);
  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 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 ForwardIterator1, class ForwardIterator2, class T>
    T transform_reduce(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
                       ForwardIterator1 first1, ForwardIterator1 last1,
                       ForwardIterator2 first2,
                       T init);
  template<class ExecutionPolicy,
           class ForwardIterator1, class ForwardIterator2, class T,
           class BinaryOperation1, class BinaryOperation2>
    T transform_reduce(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
                       ForwardIterator1 first1, ForwardIterator1 last1,
                       ForwardIterator2 first2,
                       T init,
                       BinaryOperation1 binary_op1,
                       BinaryOperation2 binary_op2);
  template<class ExecutionPolicy,
           class ForwardIterator, class T,
           class BinaryOperation, class UnaryOperation>
    T transform_reduce(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
                       ForwardIterator first, ForwardIterator last,
                       T init,
                       BinaryOperation binary_op, UnaryOperation unary_op);

  // [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);

  // [exclusive.scan], exclusive scan
  template<class InputIterator, class OutputIterator, class T>
    OutputIterator exclusive_scan(InputIterator first, InputIterator last,
                                  OutputIterator result,
                                  T init);
  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>
    ForwardIterator2 exclusive_scan(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
                                    ForwardIterator1 first, ForwardIterator1 last,
                                    ForwardIterator2 result,
                                    T init);
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class T,
           class BinaryOperation>
    ForwardIterator2 exclusive_scan(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
                                    ForwardIterator1 first, ForwardIterator1 last,
                                    ForwardIterator2 result,
                                    T init, BinaryOperation binary_op);

  // [inclusive.scan], inclusive scan
  template<class InputIterator, class OutputIterator>
    OutputIterator inclusive_scan(InputIterator first, InputIterator last,
                                  OutputIterator result);
  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, class T>
    OutputIterator inclusive_scan(InputIterator first, InputIterator last,
                                  OutputIterator result,
                                  BinaryOperation binary_op, T init);
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
    ForwardIterator2 inclusive_scan(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
                                    ForwardIterator1 first, ForwardIterator1 last,
                                    ForwardIterator2 result);
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
           class BinaryOperation>
    ForwardIterator2 inclusive_scan(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
                                    ForwardIterator1 first, ForwardIterator1 last,
                                    ForwardIterator2 result,
                                    BinaryOperation binary_op);
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
           class BinaryOperation, class T>
    ForwardIterator2 inclusive_scan(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
                                    ForwardIterator1 first, ForwardIterator1 last,
                                    ForwardIterator2 result,
                                    BinaryOperation binary_op, T init);

  // [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, // see [algorithms.parallel.overloads]
                                              ForwardIterator1 first, ForwardIterator1 last,
                                              ForwardIterator2 result,
                                              T init,
                                              BinaryOperation binary_op,
                                              UnaryOperation unary_op);

  // [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 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>
    ForwardIterator2 transform_inclusive_scan(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
                                              ForwardIterator1 first, ForwardIterator1 last,
                                              ForwardIterator2 result,
                                              BinaryOperation binary_op,
                                              UnaryOperation unary_op);
  template<class ExecutionPolicy,
           class ForwardIterator1, class ForwardIterator2,
           class BinaryOperation, class UnaryOperation, class T>
    ForwardIterator2 transform_inclusive_scan(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
                                              ForwardIterator1 first, ForwardIterator1 last,
                                              ForwardIterator2 result,
                                              BinaryOperation binary_op,
                                              UnaryOperation unary_op,
                                              T init);

  // [adjacent.difference], adjacent difference
  template <class InputIterator, class OutputIterator>
    OutputIterator adjacent_difference(InputIterator first,
                                       InputIterator last,
                                       OutputIterator 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>
    ForwardIterator2 adjacent_difference(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
                                         ForwardIterator1 first,
                                         ForwardIterator1 last,
                                         ForwardIterator2 result);
  template <class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
            class BinaryOperation>
    ForwardIterator2 adjacent_difference(ExecutionPolicy&& exec, // see [algorithms.parallel.overloads]
                                         ForwardIterator1 first,
                                         ForwardIterator1 last,
                                         ForwardIterator2 result,
                                         BinaryOperation binary_op);

  // [numeric.iota], iota
  template <class ForwardIterator, class T>
    void iota(ForwardIterator first, ForwardIterator last, T value);

  // [numeric.ops.gcd], greatest common divisor
  template <class M, class N>
    constexpr common_type_t<M,N> gcd(M m, N n);

  // [numeric.ops.lcm], least common multiple
  template <class M, class N>
    constexpr common_type_t<M,N> lcm(M m, N n);
}
1
#

The requirements on the types of algorithms' arguments that are described in the introduction to Clause [algorithms] also apply to the following algorithms.

2
#

Throughout this subclause, the parameters UnaryOperation, BinaryOperation, BinaryOperation1, and BinaryOperation2 are used whenever an algorithm expects a function object ([function.objects]).

3
#

[ Note: The use of closed ranges as well as semi-open ranges to specify requirements throughout this subclause is intentional.  — end note ]

29.8.2 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);

1
#

Requires: T shall meet the requirements of CopyConstructible and CopyAssignable types. In the range [first, last], binary_­op shall neither modify elements nor invalidate iterators or subranges.281

2
#

Effects: Computes its result by initializing the accumulator acc with the initial value init and then modifies it with acc = acc + *i or acc = binary_­op(acc, *i) for every iterator i in the range [first, last) in order.282

281)

The use of fully closed ranges is intentional.

282)

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.

29.8.3 Reduce [reduce]

template<class InputIterator> typename iterator_traits<InputIterator>::value_type reduce(InputIterator first, InputIterator last);

1
#

Effects: Equivalent to: 

return reduce(first, last,
              typename iterator_traits<InputIterator>::value_type{});

template<class ExecutionPolicy, class ForwardIterator> typename iterator_traits<ForwardIterator>::value_type reduce(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last);

2
#

Effects: Equivalent to: 

return reduce(std::forward<ExecutionPolicy>(exec), first, last,
              typename iterator_traits<ForwardIterator>::value_type{});

template<class InputIterator, class T> T reduce(InputIterator first, InputIterator last, T init);

3
#

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);

4
#

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);

5
#

Requires:

  • (5.1)

    T shall be MoveConstructible (Table 23).

  • (5.2)

    All of binary_­op(init, *first), binary_­op(*first, init), binary_­op(init, init), and binary_­op(*first, *first) shall be convertible to T.

  • (5.3)

    binary_­op shall neither invalidate iterators or subranges, nor modify elements in the range [first, last].

6
#

Returns: GENERALIZED_­SUM(binary_­op, init, *i, ...) for every i in [first, last).

7
#

Complexity: O(last - first) applications of binary_­op.

8
#

[ Note: The difference between reduce and accumulate is that reduce applies binary_­op in an unspecified order, which yields a nondeterministic result for non-associative or non-commutative binary_­op such as floating-point addition.  — end note ]

29.8.4 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);

1
#

Requires: T shall meet the requirements of CopyConstructible and CopyAssignable types. In the ranges [first1, last1] and [first2, first2 + (last1 - first1)] binary_­op1 and binary_­op2 shall neither modify elements nor invalidate iterators or subranges.283

2
#

Effects: Computes its result by initializing the accumulator acc with the initial value init and then modifying it with acc = acc + (*i1) * (*i2) or acc = binary_­op1(acc, binary_­op2(*i1, *i2)) for every iterator i1 in the range [first1, last1) and iterator i2 in the range [first2, first2 + (last1 - first1)) in order.

283)

The use of fully closed ranges is intentional.

29.8.5 Transform reduce [transform.reduce]

template <class InputIterator1, class InputIterator2, class T> T transform_reduce(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init); template <class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class T> T transform_reduce(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, T init);

1
#

Effects: Equivalent to: 

return transform_reduce(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);

2
#

Requires:

  • (2.1)

    T shall be MoveConstructible (Table 23).

  • (2.2)

    All of

    • (2.2.1)

      binary_­op1(init, init),

    • (2.2.2)

      binary_­op1(init, binary_­op2(*first1, *first2)),

    • (2.2.3)

      binary_­op1(binary_­op2(*first1, *first2), init), and

    • (2.2.4)

      binary_­op1(binary_­op2(*first1, *first2), binary_­op2(*first1, *first2))

    shall be convertible to T.

  • (2.3)

    Neither binary_­op1 nor binary_­op2 shall invalidate subranges, or modify elements in the ranges [first1, last1] and [first2, first2 + (last1 - first1)].

3
#

Returns: 

GENERALIZED_SUM(binary_op1, init, binary_op2(*i, *(first2 + (i - first1))), ...)

for every iterator i in [first1, last1).

4
#

Complexity: O(last1 - first1) applications each of binary_­op1 and binary_­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);

5
#

Requires:

  • (5.1)

    T shall be MoveConstructible (Table 23).

  • (5.2)

    All of

    • (5.2.1)

      binary_­op(init, init),

    • (5.2.2)

      binary_­op(init, unary_­op(*first)),

    • (5.2.3)

      binary_­op(unary_­op(*first), init), and

    • (5.2.4)

      binary_­op(unary_­op(*first), unary_­op(*first))

    shall be convertible to T.

  • (5.3)

    Neither unary_­op nor binary_­op shall invalidate subranges, or modify elements in the range [first, last].

6
#

Returns: 

GENERALIZED_SUM(binary_op, init, unary_op(*i), ...)

for every iterator i in [first, last).

7
#

Complexity: O(last - first) applications each of unary_­op and binary_­op.

8
#

[ Note: transform_­reduce does not apply unary_­op to init.  — end note ]

29.8.6 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);

1
#

Requires: InputIterator's value type shall be constructible from the type of *first. The result of the expression acc + *i or binary_­op(acc, *i) shall be implicitly convertible to InputIterator's value type. acc shall be writable to the result output iterator. In the ranges [first, last] and [result, result + (last - first)] binary_­op shall neither modify elements nor invalidate iterators or subranges.284

2
#

Effects: For a non-empty range, the function creates an accumulator acc whose type is InputIterator's value type, initializes it with *first, and assigns the result to *result. For every iterator i in [first + 1, last) in order, acc is then modified by acc = acc + *i or acc = binary_­op(acc, *i) and the result is assigned to *(result + (i - first)).

3
#

Returns: result + (last - first).

4
#

Complexity: Exactly (last - first) - 1 applications of the binary operation.

5
#

Remarks: result may be equal to first.

284)

The use of fully closed ranges is intentional.

29.8.7 Exclusive scan [exclusive.scan]

template<class InputIterator, class OutputIterator, class T> OutputIterator exclusive_scan(InputIterator first, InputIterator last, OutputIterator result, T init);

1
#

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);

2
#

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);

3
#

Requires:

  • (3.1)

    T shall be MoveConstructible (Table 23).

  • (3.2)

    All of binary_­op(init, init), binary_­op(init, *first), and binary_­op(*first, *first) shall be convertible to T.

  • (3.3)

    binary_­op shall neither invalidate iterators or subranges, nor modify elements in the ranges [first, last] or [result, result + (last - first)].

4
#

Effects: For each integer K in [0, last - first) assigns through result + K the value of: 

GENERALIZED_NONCOMMUTATIVE_SUM(
    binary_op, init, *(first + 0), *(first + 1), ..., *(first + K - 1))
5
#

Returns: The end of the resulting range beginning at result.

6
#

Complexity: O(last - first) applications of binary_­op.

7
#

Remarks: result may be equal to first.

8
#

[ Note: The difference between exclusive_­scan and inclusive_­scan is that exclusive_­scan excludes the ith input element from the ith sum. If binary_­op is not mathematically associative, the behavior of exclusive_­scan may be nondeterministic.  — end note ]

29.8.8 Inclusive scan [inclusive.scan]

template<class InputIterator, class OutputIterator> OutputIterator inclusive_scan(InputIterator first, InputIterator last, OutputIterator result);

1
#

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);

2
#

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);

3
#

Requires:

  • (3.1)

    If init is provided, T shall be MoveConstructible (Table 23); otherwise, ForwardIterator1's value type shall be MoveConstructible.

  • (3.2)

    If init is provided, all of binary_­op(init, init), binary_­op(init, *first), and binary_­op(*first, *first) shall be convertible to T; otherwise, binary_­op(*first, *first) shall be convertible to ForwardIterator1's value type.

  • (3.3)

    binary_­op shall neither invalidate iterators or subranges, nor modify elements in the ranges [first, last] or [result, result + (last - first)].

4
#

Effects: For each integer K in [0, last - first) assigns through result + K the value of

  • (4.1)

    GENERALIZED_­NONCOMMUTATIVE_­SUM(
        binary_­op, init, *(first + 0), *(first + 1), ..., *(first + K))
    if init is provided, or

  • (4.2)

    GENERALIZED_­NONCOMMUTATIVE_­SUM(
        binary_­op, *(first + 0), *(first + 1), ..., *(first + K))
    otherwise.

5
#

Returns: The end of the resulting range beginning at result.

6
#

Complexity: O(last - first) applications of binary_­op.

7
#

Remarks: result may be equal to first.

8
#

[ Note: The difference between exclusive_­scan and inclusive_­scan is that inclusive_­scan includes the ith input element in the ith sum. If binary_­op is not mathematically associative, the behavior of inclusive_­scan may be nondeterministic.  — end note ]

29.8.9 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);

1
#

Requires:

  • (1.1)

    T shall be MoveConstructible (Table 23).

  • (1.2)

    All of

    • (1.2.1)

      binary_­op(init, init),

    • (1.2.2)

      binary_­op(init, unary_­op(*first)), and

    • (1.2.3)

      binary_­op(unary_­op(*first), unary_­op(*first))

    shall be convertible to T.

  • (1.3)

    Neither unary_­op nor binary_­op shall invalidate iterators or subranges, or modify elements in the ranges [first, last] or [result, result + (last - first)].

2
#

Effects: For each integer K in [0, last - first) assigns through result + K the value of: 

GENERALIZED_NONCOMMUTATIVE_SUM(
    binary_op, init,
    unary_op(*(first + 0)), unary_op(*(first + 1)), ..., unary_op(*(first + K - 1)))
3
#

Returns: The end of the resulting range beginning at result.

4
#

Complexity: O(last - first) applications each of unary_­op and binary_­op.

5
#

Remarks: result may be equal to first.

6
#

[ Note: The difference between transform_­exclusive_­scan and transform_­inclusive_­scan is that transform_­exclusive_­scan excludes the ith input element from the ith sum. If binary_­op is not mathematically associative, the behavior of transform_­exclusive_­scan may be nondeterministic. transform_­exclusive_­scan does not apply unary_­op to init.  — end note ]

29.8.10 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);

1
#

Requires:

  • (1.1)

    If init is provided, T shall be MoveConstructible (Table 23); otherwise, ForwardIterator1's value type shall be MoveConstructible.

  • (1.2)

    If init is provided, all of

    • (1.2.1)

      binary_­op(init, init),

    • (1.2.2)

      binary_­op(init, unary_­op(*first)), and

    • (1.2.3)

      binary_­op(unary_­op(*first), unary_­op(*first))

    shall be convertible to T; otherwise, binary_­op(unary_­op(*first), unary_­op(*first)) shall be convertible to ForwardIterator1's value type.

  • (1.3)

    Neither unary_­op nor binary_­op shall invalidate iterators or subranges, nor modify elements in the ranges [first, last] or [result, result + (last - first)].

2
#

Effects: For each integer K in [0, last - first) assigns through result + K the value of

  • (2.1)

    GENERALIZED_­NONCOMMUTATIVE_­SUM(
        binary_­op, init,
        unary_­op(*(first + 0)), unary_­op(*(first + 1)), ..., unary_­op(*(first + K)))
    if init is provided, or

  • (2.2)

    GENERALIZED_­NONCOMMUTATIVE_­SUM(
        binary_­op,
        unary_­op(*(first + 0)), unary_­op(*(first + 1)), ..., unary_­op(*(first + K)))
    otherwise.

3
#

Returns: The end of the resulting range beginning at result.

4
#

Complexity: O(last - first) applications each of unary_­op and binary_­op.

5
#

Remarks: result may be equal to first.

6
#

[ Note: The difference between transform_­exclusive_­scan and transform_­inclusive_­scan is that transform_­inclusive_­scan includes the ith input element in the ith sum. If binary_­op is not mathematically associative, the behavior of transform_­inclusive_­scan may be nondeterministic. transform_­inclusive_­scan does not apply unary_­op to init.  — end note ]

29.8.11 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);

1
#

Requires:

  • (1.1)

    For the overloads with no ExecutionPolicy, InputIterator's value type shall be MoveAssignable (Table 25) and shall be constructible from the type of *first. acc (defined below) shall be writable ([iterator.requirements.general]) to the result output iterator. The result of the expression val - acc or binary_­op(val, acc) shall be writable to the result output iterator.

  • (1.2)

    For the overloads with an ExecutionPolicy, the value type of ForwardIterator1 shall be CopyConstructible (Table 24), constructible from the expression *first - *first or binary_­op(*first, *first), and assignable to the value type of ForwardIterator2.

  • (1.3)

    For all overloads, in the ranges [first, last] and [result, result + (last - first)], binary_­op shall neither modify elements nor invalidate iterators or subranges.285

2
#

Effects: For the overloads with no ExecutionPolicy and a non-empty range, the function creates an accumulator acc whose type is InputIterator's value type, initializes it with *first, and assigns the result to *result. For every iterator i in [first + 1, last) in order, creates an object val whose type is InputIterator's value type, initializes it with *i, computes val - acc or binary_­op(val, acc), assigns the result to *(result + (i - first)), and move assigns from val to acc.

3
#

For the overloads with an ExecutionPolicy and a non-empty range, first the function creates an object whose type is ForwardIterator1's value type, initializes it with *first, and assigns the result to *result. Then for every d in [1, last - first - 1], creates an object val whose type is ForwardIterator1's value type, initializes it with *(first + d) - *(first + d - 1) or binary_­op(*(first + d), *(first + d - 1)), and assigns the result to *(result + d).

4
#

Returns: result + (last - first).

5
#

Complexity: Exactly (last - first) - 1 applications of the binary operation.

6
#

Remarks: For the overloads with no ExecutionPolicy, result may be equal to first. For the overloads with an ExecutionPolicy, the ranges [first, last) and [result, result + (last - first)) shall not overlap.

285)

The use of fully closed ranges is intentional.

29.8.12 Iota [numeric.iota]

template <class ForwardIterator, class T> void iota(ForwardIterator first, ForwardIterator last, T value);

1
#

Requires: T shall be convertible to ForwardIterator's value type. The expression ++val, where val has type T, shall be well formed.

2
#

Effects: For each element referred to by the iterator i in the range [first, last), assigns *i = value and increments value as if by ++value.

3
#

Complexity: Exactly last - first increments and assignments.

29.8.13 Greatest common divisor [numeric.ops.gcd]

template <class M, class N> constexpr common_type_t<M,N> gcd(M m, N n);

1
#

Requires: |m| and |n| shall be representable as a value of common_­type_­t<M, N>. [ Note: These requirements ensure, for example, that gcd(m, m) = |m| is representable as a value of type M.  — end note ]

2
#

Remarks: If either M or N is not an integer type, or if either is cv bool, the program is ill-formed.

3
#

Returns: Zero when m and n are both zero. Otherwise, returns the greatest common divisor of |m| and |n|.

4
#

Throws: Nothing.

29.8.14 Least common multiple [numeric.ops.lcm]

template <class M, class N> constexpr common_type_t<M,N> lcm(M m, N n);

1
#

Requires: |m| and |n| shall be representable as a value of common_­type_­t<M, N>. The least common multiple of |m| and |n| shall be representable as a value of type common_­type_­t<M,N>.

2
#

Remarks: If either M or N is not an integer type, or if either is cv bool the program is ill-formed.

3
#

Returns: Zero when either m or n is zero. Otherwise, returns the least common multiple of |m| and |n|.

4
#

Throws: Nothing.