25 Algorithms library [algorithms]

25.10 Generalized numeric operations [numeric.ops]

25.10.1 General [numeric.ops.general]

[Note 1:

The use of closed ranges as well as semi-open ranges to specify requirements throughout [numeric.ops] is intentional.

— end note]

25.10.2 Definitions [numerics.defns]

Define GENERALIZED_NONCOMMUTATIVE_SUM(op, a1, ..., aN) as follows:

(1.1)
a1 when N is 1, otherwise
(1.2)
op(GENERALIZED_NONCOMMUTATIVE_SUM(op, a1, ..., aK),

op(GENERALIZED_NONCOMMUTATIVE_SUM(op, aM, ..., aN)) for any K where $1 < K + 1 = M \leq N$ .

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.3 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.241

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.242

241)

The use of fully closed ranges is intentional.

⮥

242)

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.4 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

(5.1)
binary_op(init, *first),
(5.2)
binary_op(*first, init),
(5.3)
binary_op(init, init), and
(5.4)
binary_op(*first, *first)

are convertible to T.

Preconditions:

(6.1)
T meets the Cpp17MoveConstructible (Table 28) requirements.
(6.2)
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:

O (last - first)

applications of binary_op.

[Note 1:

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.5 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.243

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.

243)

The use of fully closed ranges is intentional.

⮥

25.10.6 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

(3.1)
binary_op1(init, init),
(3.2)
binary_op1(init, binary_op2(*first1, *first2)),
(3.3)
binary_op1(binary_op2(*first1, *first2), init), and
(3.4)
binary_op1(binary_op2(*first1, *first2), binary_op2(*first1, *first2))

are convertible to T.

Preconditions:

(4.1)
T meets the Cpp17MoveConstructible (Table 28) requirements.
(4.2)
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:

O (last1 - first1)

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

(7.1)
binary_op(init, init),
(7.2)
binary_op(init, unary_op(*first)),
(7.3)
binary_op(unary_op(*first), init), and
(7.4)
binary_op(unary_op(*first), unary_op(*first))

are convertible to T.

Preconditions:

(8.1)
T meets the Cpp17MoveConstructible (Table 28) requirements.
(8.2)
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:

O (last - first)

applications each of unary_op and binary_op.

[Note 1:

transform_reduce does not apply unary_op to init.

— end note]

25.10.7 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.244

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.

244)

The use of fully closed ranges is intentional.

⮥

25.10.8 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

(3.1)
binary_op(init, init),
(3.2)
binary_op(init, *first), and
(3.3)
binary_op(*first, *first)

are convertible to T.

Preconditions:

(4.1)
T meets the Cpp17MoveConstructible (Table 28) requirements.
(4.2)
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:

O (last - first)

applications of binary_op.

Remarks: result may be equal to first.

[Note 1:

The difference between exclusive_scan and inclusive_scan is that exclusive_scan excludes the

i^{th}

input element from the

i^{th}

sum.

If binary_op is not mathematically associative, the behavior of exclusive_scan might be nondeterministic.

— end note]

25.10.9 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

(4.1)
binary_op(init, init),
(4.2)
binary_op(init, *first), and
(4.3)
binary_op(*first, *first)

are convertible to T; otherwise, binary_op(*first, *first) is convertible to U.

Preconditions:

(5.1)
If init is provided, T meets the Cpp17MoveConstructible (Table 28) requirements; otherwise, U meets the Cpp17MoveConstructible requirements.
(5.2)
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

(6.1)
GENERALIZED_NONCOMMUTATIVE_SUM(
binary_op, init, *(first + 0), *(first + 1), ..., *(first + K))

if init is provided, or
(6.2)
GENERALIZED_NONCOMMUTATIVE_SUM(
binary_op, *(first + 0), *(first + 1), ..., *(first + K))

otherwise.

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

Complexity:

O (last - first)

applications of binary_op.

Remarks: result may be equal to first.

[Note 1:

The difference between exclusive_scan and inclusive_scan is that inclusive_scan includes the

i^{th}

input element in the

i^{th}

sum.

If binary_op is not mathematically associative, the behavior of inclusive_scan might be nondeterministic.

— end note]

25.10.10 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

(1.1)
binary_op(init, init),
(1.2)
binary_op(init, unary_op(*first)), and
(1.3)
binary_op(unary_op(*first), unary_op(*first))

are convertible to T.

Preconditions:

(2.1)
T meets the Cpp17MoveConstructible (Table 28) requirements.
(2.2)
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:

O (last - first)

applications each of unary_op and binary_op.

Remarks: result may be equal to first.

[Note 1:

The difference between transform_exclusive_scan and transform_inclusive_scan is that transform_exclusive_scan excludes the

i^{th}

input element from the

i^{th}

sum.

If binary_op is not mathematically associative, the behavior of transform_exclusive_scan might be nondeterministic.

transform_exclusive_scan does not apply unary_op to init.

— end note]

25.10.11 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

(2.1)
binary_op(init, init),
(2.2)
binary_op(init, unary_op(*first)), and
(2.3)
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:

(3.1)
If init is provided, T meets the Cpp17MoveConstructible (Table 28) requirements; otherwise, U meets the Cpp17MoveConstructible requirements.
(3.2)
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

(4.1)
GENERALIZED_NONCOMMUTATIVE_SUM(
binary_op, init,
unary_op(*(first + 0)), unary_op(*(first + 1)), ..., unary_op(*(first + K)))

if init is provided, or
(4.2)
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:

O (last - first)

applications each of unary_op and binary_op.

Remarks: result may be equal to first.

[Note 1:

The difference between transform_exclusive_scan and transform_inclusive_scan is that transform_inclusive_scan includes the

i^{th}

input element in the

i^{th}

sum.

If binary_op is not mathematically associative, the behavior of transform_inclusive_scan might be nondeterministic.

transform_inclusive_scan does not apply unary_op to init.

— end note]

25.10.12 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:

(2.1)
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.
(2.2)
For the overloads with an ExecutionPolicy, the result of the expressions binary_op(*first, *first) and *first are writable to result.

Preconditions:

(3.1)
For the overloads with no ExecutionPolicy, T meets the Cpp17MoveAssignable (Table 30) requirements.
(3.2)
For all overloads, in the ranges [first, last] and [result, result + (last - first)], binary_op neither modifies elements nor invalidate iterators or subranges.245

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.

245)

The use of fully closed ranges is intentional.

⮥

25.10.13 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.14 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 other than cv bool.

Preconditions: |m| and |n| are representable as a value of common_type_t<M, N>.

[Note 1:

These requirements ensure, for example, that

gcd(m, m) = | m |

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.15 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 other than 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.16 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 1:

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

i + \frac{j - i}{2}

of x, where the result of the division is truncated towards zero.