25 Algorithms library [algorithms]

25.10 Generalized numeric operations [numeric.ops]

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

25.10.1 Definitions [numerics.defns]

Define GENERALIZED_­NONCOMMUTATIVE_­SUM(op, a1, ..., aN) as follows:
  • a1 when N is 1, otherwise
  • op(GENERALIZED_­NONCOMMUTATIVE_­SUM(op, a1, ..., aK),
    op(GENERALIZED_­NONCOMMUTATIVE_­SUM(op, aM, ..., aN)) for any K where .
Define GENERALIZED_­SUM(op, a1, ..., aN) as GENERALIZED_­NONCOMMUTATIVE_­SUM(op, b1, ..., bN), where b1, ..., bN may be any permutation of a1, ..., aN.

25.10.2 Accumulate [accumulate]

template<class InputIterator, class T> constexpr T accumulate(InputIterator first, InputIterator last, T init); template<class InputIterator, class T, class BinaryOperation> constexpr T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op);
Preconditions: T meets the Cpp17CopyConstructible (Table 29) and Cpp17CopyAssignable (Table 31) requirements.
In the range [first, last], binary_­op neither modifies elements nor invalidates iterators or subranges.235
Effects: Computes its result by initializing the accumulator acc with the initial value init and then modifies it with acc = std​::​move(acc) + *i or acc = binary_­op(std​::​move(acc), *i) for every iterator i in the range [first, last) in order.236
The use of fully closed ranges is intentional.
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.

25.10.3 Reduce [reduce]

template<class InputIterator> constexpr typename iterator_traits<InputIterator>::value_type reduce(InputIterator first, InputIterator last);
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);
Effects: Equivalent to:
return reduce(std::forward<ExecutionPolicy>(exec), first, last,
              typename iterator_traits<ForwardIterator>::value_type{});
template<class InputIterator, class T> constexpr 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> constexpr 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);
Mandates: All of
  • binary_­op(init, *first),
  • binary_­op(*first, init),
  • binary_­op(init, init), and
  • binary_­op(*first, *first)
are convertible to T.
Preconditions:
  • T meets the Cpp17MoveConstructible (Table 28) requirements.
  • binary_­op neither invalidates iterators or subranges, nor modifies elements in the range [first, last].
Returns: GENERALIZED_­SUM(binary_­op, init, *i, ...) for every i in [first, last).
Complexity: applications of binary_­op.
[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
]

25.10.4 Inner product [inner.product]

template<class InputIterator1, class InputIterator2, class T> constexpr T inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init); template<class InputIterator1, class InputIterator2, class T, class BinaryOperation1, class BinaryOperation2> constexpr T inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init, BinaryOperation1 binary_op1, BinaryOperation2 binary_op2);
Preconditions: T meets the Cpp17CopyConstructible (Table 29) and Cpp17CopyAssignable (Table 31) requirements.
In the ranges [first1, last1] and [first2, first2 + (last1 - first1)] binary_­op1 and binary_­op2 neither modifies elements nor invalidates iterators or subranges.237
Effects: Computes its result by initializing the accumulator acc with the initial value init and then modifying it with acc = std​::​move(acc) + (*i1) * (*i2) or acc = binary_­op1(std​::​move(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.
The use of fully closed ranges is intentional.

25.10.5 Transform reduce [transform.reduce]

template<class InputIterator1, class InputIterator2, class T> constexpr 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> constexpr 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);
Mandates: All of
  • binary_­op1(init, init),
  • binary_­op1(init, binary_­op2(*first1, *first2)),
  • binary_­op1(binary_­op2(*first1, *first2), init), and
  • binary_­op1(binary_­op2(*first1, *first2), binary_­op2(*first1, *first2))
are convertible to T.
Preconditions:
  • T meets the Cpp17MoveConstructible (Table 28) requirements.
  • Neither binary_­op1 nor binary_­op2 invalidates subranges, nor modifies elements in the ranges [first1, last1] and [first2, first2 + (last1 - first1)].
Returns:
GENERALIZED_SUM(binary_op1, init, binary_op2(*i, *(first2 + (i - first1))), ...)
for every iterator i in [first1, last1).
Complexity: applications each of binary_­op1 and binary_­op2.
template<class InputIterator, class T, class BinaryOperation, class UnaryOperation> constexpr 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);
Mandates: All of
  • binary_­op(init, init),
  • binary_­op(init, unary_­op(*first)),
  • binary_­op(unary_­op(*first), init), and
  • binary_­op(unary_­op(*first), unary_­op(*first))
are convertible to T.
Preconditions:
  • T meets the Cpp17MoveConstructible (Table 28) requirements.
  • Neither unary_­op nor binary_­op invalidates subranges, nor modifies elements in the range [first, last].
Returns:
GENERALIZED_SUM(binary_op, init, unary_op(*i), ...)
for every iterator i in [first, last).
Complexity: applications each of unary_­op and binary_­op.
[Note
:
transform_­reduce does not apply unary_­op to init.
— end note
]

25.10.6 Partial sum [partial.sum]

template<class InputIterator, class OutputIterator> constexpr OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result); template<class InputIterator, class OutputIterator, class BinaryOperation> constexpr OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op);
Mandates: InputIterator's value type is constructible from *first.
The result of the expression std​::​move(acc) + *i or binary_­op(std​::​move(acc), *i) is implicitly convertible to InputIterator's value type.
acc is writable ([iterator.requirements.general]) to result.
Preconditions: In the ranges [first, last] and [result, result + (last - first)] binary_­op neither modifies elements nor invalidates iterators or subranges.238
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 = std​::​move(acc) + *i or acc = 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 to first.
The use of fully closed ranges is intentional.

25.10.7 Exclusive scan [exclusive.scan]

template<class InputIterator, class OutputIterator, class T> constexpr 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> constexpr 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);
Mandates: All of
  • binary_­op(init, init),
  • binary_­op(init, *first), and
  • binary_­op(*first, *first)
are convertible to T.
Preconditions:
  • T meets the Cpp17MoveConstructible (Table 28) requirements.
  • binary_­op neither invalidates iterators or subranges, nor modifies elements in the ranges [first, last] or [result, result + (last - first)].
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))
Returns: The end of the resulting range beginning at result.
Complexity: applications of binary_­op.
Remarks: result may be equal to first.
[Note
:
The difference between exclusive_­scan and inclusive_­scan is that exclusive_­scan excludes the input element from the sum.
If binary_­op is not mathematically associative, the behavior of exclusive_­scan may be nondeterministic.
— end note
]

25.10.8 Inclusive scan [inclusive.scan]

template<class InputIterator, class OutputIterator> constexpr 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> constexpr 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> constexpr 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);
Let U be the value type of decltype(first).
Mandates: If init is provided, all of
  • binary_­op(init, init),
  • binary_­op(init, *first), and
  • binary_­op(*first, *first)
are convertible to T; otherwise, binary_­op(*first, *first) is convertible to U.
Preconditions:
  • If init is provided, T meets the Cpp17MoveConstructible (Table 28) requirements; otherwise, U meets the Cpp17MoveConstructible requirements.
  • binary_­op neither invalidates iterators or subranges, nor modifies elements in the ranges [first, last] or [result, result + (last - first)].
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))

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

    otherwise.
Returns: The end of the resulting range beginning at result.
Complexity: applications of binary_­op.
Remarks: result may be equal to first.
[Note
:
The difference between exclusive_­scan and inclusive_­scan is that inclusive_­scan includes the input element in the sum.
If binary_­op is not mathematically associative, the behavior of inclusive_­scan may be nondeterministic.
— end note
]

25.10.9 Transform exclusive scan [transform.exclusive.scan]

template<class InputIterator, class OutputIterator, class T, class BinaryOperation, class UnaryOperation> constexpr 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);
Mandates: All of
  • binary_­op(init, init),
  • binary_­op(init, unary_­op(*first)), and
  • binary_­op(unary_­op(*first), unary_­op(*first))
are convertible to T.
Preconditions:
  • T meets the Cpp17MoveConstructible (Table 28) requirements.
  • Neither unary_­op nor binary_­op invalidates iterators or subranges, nor modifies elements in the ranges [first, last] or [result, result + (last - first)].
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)))
Returns: The end of the resulting range beginning at result.
Complexity: applications each of unary_­op and binary_­op.
Remarks: result may be equal to first.
[Note
:
The difference between transform_­exclusive_­scan and transform_­inclusive_­scan is that transform_­exclusive_­scan excludes the input element from the 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
]

25.10.10 Transform inclusive scan [transform.inclusive.scan]

template<class InputIterator, class OutputIterator, class BinaryOperation, class UnaryOperation> constexpr 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> constexpr 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);
Let U be the value type of decltype(first).
Mandates: If init is provided, all of
  • binary_­op(init, init),
  • binary_­op(init, unary_­op(*first)), and
  • binary_­op(unary_­op(*first), unary_­op(*first))
are convertible to T; otherwise, binary_­op(unary_­op(*first), unary_­op(*first)) is convertible to U.
Preconditions:
  • If init is provided, T meets the Cpp17MoveConstructible (Table 28) requirements; otherwise, U meets the Cpp17MoveConstructible requirements.
  • Neither unary_­op nor binary_­op invalidates iterators or subranges, nor modifies elements in the ranges [first, last] or [result, result + (last - first)].
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)))

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

    otherwise.
Returns: The end of the resulting range beginning at result.
Complexity: applications each of unary_­op and binary_­op.
Remarks: result may be equal to first.
[Note
:
The difference between transform_­exclusive_­scan and transform_­inclusive_­scan is that transform_­inclusive_­scan includes the input element in the 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
]

25.10.11 Adjacent difference [adjacent.difference]

template<class InputIterator, class OutputIterator> constexpr 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> constexpr 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);
Let T be the value type of decltype(first).
For the overloads that do not take an argument binary_­op, let binary_­op be an lvalue that denotes an object of type minus<>.
Mandates:
  • For the overloads with no ExecutionPolicy, T is constructible from *first. acc (defined below) is writable ([iterator.requirements.general]) to the result output iterator. The result of the expression binary_­op(val, std​::​move(acc)) is writable to result.
  • For the overloads with an ExecutionPolicy, the result of the expressions binary_­op(*first, *first) and *first are writable to result.
Preconditions:
  • For the overloads with no ExecutionPolicy, T meets the Cpp17MoveAssignable (Table 30) requirements.
  • For all overloads, in the ranges [first, last] and [result, result + (last - first)], binary_­op neither modifies elements nor invalidate iterators or subranges.239
Effects: For the overloads with no ExecutionPolicy and a non-empty range, the function creates an accumulator acc of type T, 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 T, initializes it with *i, computes binary_­op(val, std​::​move(acc)), assigns the result to *(result + (i - first)), and move assigns from val to acc.
For the overloads with an ExecutionPolicy and a non-empty range, performs *result = *first.
Then, for every d 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 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.
The use of fully closed ranges is intentional.

25.10.12 Iota [numeric.iota]

template<class ForwardIterator, class T> constexpr void iota(ForwardIterator first, ForwardIterator last, T value);
Mandates: T is convertible to ForwardIterator's value type.
The expression ++val, where val has type T, is well-formed.
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.
Complexity: Exactly last - first increments and assignments.

25.10.13 Greatest common divisor [numeric.ops.gcd]

template<class M, class N> constexpr common_type_t<M,N> gcd(M m, N n);
Mandates: M and N both are integer types and not cv bool.
Preconditions: |m| and |n| are representable as a value of common_­type_­t<M, N>.
[Note
:
These requirements ensure, for example, that is representable as a value of type M.
— end note
]
Returns: Zero when m and n are both zero.
Otherwise, returns the greatest common divisor of |m| and |n|.
Throws: Nothing.

25.10.14 Least common multiple [numeric.ops.lcm]

template<class M, class N> constexpr common_type_t<M,N> lcm(M m, N n);
Mandates: M and N both are integer types and not cv bool.
Preconditions: |m| and |n| are representable as a value of common_­type_­t<M, N>.
The least common multiple of |m| and |n| is representable as a value of type common_­type_­t<M,N>.
Returns: Zero when either m or n is zero.
Otherwise, returns the least common multiple of |m| and |n|.
Throws: Nothing.

25.10.15 Midpoint [numeric.ops.midpoint]

template<class T> constexpr T midpoint(T a, T b) noexcept;
Constraints: T is an arithmetic type other than bool.
Returns: Half the sum of a and b.
If T is an integer type and the sum is odd, the result is rounded towards a.
Remarks: No overflow occurs.
If T is a floating-point type, at most one inexact operation occurs.
template<class T> constexpr T* midpoint(T* a, T* b);
Constraints: T is an object type.
Mandates: T is a complete type.
Preconditions: a and b point to, respectively, elements i and j of the same array object x.
[Note
:
As specified in [basic.compound], an object that is not an array element is considered to belong to a single-element array for this purpose and a pointer past the last element of an array of n elements is considered to be equivalent to a pointer to a hypothetical array element n for this purpose.
— end note
]
Returns: A pointer to array element of x, where the result of the division is truncated towards zero.