Przejdź do głównej zawartości

std::exclusive_scan() algorithm

// (1)
template< class InputIt, class OutputIt >
constexpr OutputIt exclusive_scan( InputIt first, InputIt last, OutputIt d_first );

// (2)
template< class InputIt, class OutputIt, class BinaryOperation >
constexpr OutputIt exclusive_scan( InputIt first, InputIt last, OutputIt d_first, BinaryOperation binary_op );

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

// (4)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardtIt2 exclusive_scan( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first );

// (5)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryOperation >
ForwardIt2 exclusive_scan( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first,
BinaryOperation binary_op );

// (6)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryOperation, class T >
ForwardIt2 exclusive_scan( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first,
BinaryOperation binary_op, T init );

Computes an exclusive prefix sum operation using binary_op (or std::plus<>() for overloads (1, 4)) for the range [first; last), using init as the initial value (if provided), and writes the results to the range beginning at d_first.

"exclusive" means that the i-th input element is not included in the i-th sum.

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:

  • (1, 2, 4, 5) The generalized noncommutative sum of *j... for every j in [first; first + (i - d_first + 1) ) over binary_op
  • (3, 6) The generalized noncommutative sum of init, *j... for every j in [first; first + (i - d_first + 1)) over binary_op

where generalized noncommutative sum GNSUM(op, a1, ..., aN) is defined as follows:

  • If N = 1, a1

  • If N > 1, op(GNSUM(op, a1, ..., aK), GNSUM(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

binary_op shall not invalidate iterators (including the end iterators) or subranges, nor modify elements in the ranges [first, last) or [d_first, d_first + (last - first)).

Otherwise, the behavior is undefined

.

Parameters

first
last

The range of elements to sum.

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.

binary_op

Binary FunctionObject that will be applied in unspecified order to the result of dereferencing the input iterators, the results of other binary_op and init.

Type requirements

InputItLegacyInputIterator
OutputItLegacyOutputIterator
ForwardIt1
ForwardIt2
LegacyForwardIterator
  • T (if init is provided) must meet the requirements of MoveConstructible. The following expressions must be convertible to T:
    • binary_op(init, *first)
    • binary_op(init, init)
    • binary_op(*first, *first)

Return value

Iterator to the element past the last element written.

Complexity

O(last - first) applications of binary_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.

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

std::cout << "Exclusive sum: ";
std::exclusive_scan(data.begin(), data.end(),
std::ostream_iterator<int>(std::cout, " "),
0);
std::cout << "\nInclusive sum: ";
std::inclusive_scan(data.begin(), data.end(),
std::ostream_iterator<int>(std::cout, " "));

std::cout << "\n\nExclusive product: ";
std::exclusive_scan(data.begin(), data.end(),
std::ostream_iterator<int>(std::cout, " "),
1, std::multiplies<>{});
std::cout << "\nInclusive product: ";
std::inclusive_scan(data.begin(), data.end(),
std::ostream_iterator<int>(std::cout, " "),
std::multiplies<>{});
}
Possible output
Exclusive sum: 0 3 4 8 9 14 23 25
Inclusive sum: 3 4 8 9 14 23 25 31

Exclusive product: 1 3 3 12 12 60 540 1080
Inclusive product: 3 3 12 12 60 540 1080 6480
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.

std::exclusive_scan() algorithm

// (1)
template< class InputIt, class OutputIt >
constexpr OutputIt exclusive_scan( InputIt first, InputIt last, OutputIt d_first );

// (2)
template< class InputIt, class OutputIt, class BinaryOperation >
constexpr OutputIt exclusive_scan( InputIt first, InputIt last, OutputIt d_first, BinaryOperation binary_op );

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

// (4)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardtIt2 exclusive_scan( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first );

// (5)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryOperation >
ForwardIt2 exclusive_scan( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first,
BinaryOperation binary_op );

// (6)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryOperation, class T >
ForwardIt2 exclusive_scan( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first,
BinaryOperation binary_op, T init );

Computes an exclusive prefix sum operation using binary_op (or std::plus<>() for overloads (1, 4)) for the range [first; last), using init as the initial value (if provided), and writes the results to the range beginning at d_first.

"exclusive" means that the i-th input element is not included in the i-th sum.

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:

  • (1, 2, 4, 5) The generalized noncommutative sum of *j... for every j in [first; first + (i - d_first + 1) ) over binary_op
  • (3, 6) The generalized noncommutative sum of init, *j... for every j in [first; first + (i - d_first + 1)) over binary_op

where generalized noncommutative sum GNSUM(op, a1, ..., aN) is defined as follows:

  • If N = 1, a1

  • If N > 1, op(GNSUM(op, a1, ..., aK), GNSUM(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

binary_op shall not invalidate iterators (including the end iterators) or subranges, nor modify elements in the ranges [first, last) or [d_first, d_first + (last - first)).

Otherwise, the behavior is undefined

.

Parameters

first
last

The range of elements to sum.

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.

binary_op

Binary FunctionObject that will be applied in unspecified order to the result of dereferencing the input iterators, the results of other binary_op and init.

Type requirements

InputItLegacyInputIterator
OutputItLegacyOutputIterator
ForwardIt1
ForwardIt2
LegacyForwardIterator
  • T (if init is provided) must meet the requirements of MoveConstructible. The following expressions must be convertible to T:
    • binary_op(init, *first)
    • binary_op(init, init)
    • binary_op(*first, *first)

Return value

Iterator to the element past the last element written.

Complexity

O(last - first) applications of binary_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.

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

std::cout << "Exclusive sum: ";
std::exclusive_scan(data.begin(), data.end(),
std::ostream_iterator<int>(std::cout, " "),
0);
std::cout << "\nInclusive sum: ";
std::inclusive_scan(data.begin(), data.end(),
std::ostream_iterator<int>(std::cout, " "));

std::cout << "\n\nExclusive product: ";
std::exclusive_scan(data.begin(), data.end(),
std::ostream_iterator<int>(std::cout, " "),
1, std::multiplies<>{});
std::cout << "\nInclusive product: ";
std::inclusive_scan(data.begin(), data.end(),
std::ostream_iterator<int>(std::cout, " "),
std::multiplies<>{});
}
Possible output
Exclusive sum: 0 3 4 8 9 14 23 25
Inclusive sum: 3 4 8 9 14 23 25 31

Exclusive product: 1 3 3 12 12 60 540 1080
Inclusive product: 3 3 12 12 60 540 1080 6480
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.