Segmented Prefix Sums
template <typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator> _CCCL_HOST_DEVICE OutputIterator inclusive_scan_by_key(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result);
template <typename InputIterator1, typename InputIterator2, typename OutputIterator> OutputIterator inclusive_scan_by_key(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result);
template <typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator, typename BinaryPredicate> _CCCL_HOST_DEVICE OutputIterator inclusive_scan_by_key(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryPredicate binary_pred);
template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename BinaryPredicate> OutputIterator inclusive_scan_by_key(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryPredicate binary_pred);
template <typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator, typename BinaryPredicate, typename AssociativeOperator> _CCCL_HOST_DEVICE OutputIterator inclusive_scan_by_key(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryPredicate binary_pred, AssociativeOperator binary_op);
template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename BinaryPredicate, typename AssociativeOperator> OutputIterator inclusive_scan_by_key(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryPredicate binary_pred, AssociativeOperator binary_op);
template <typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator> _CCCL_HOST_DEVICE OutputIterator exclusive_scan_by_key(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result);
template <typename InputIterator1, typename InputIterator2, typename OutputIterator> OutputIterator exclusive_scan_by_key(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result);
template <typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator, typename T> _CCCL_HOST_DEVICE OutputIterator exclusive_scan_by_key(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, T init);
template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename T> OutputIterator exclusive_scan_by_key(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, T init);
template <typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator, typename T, typename BinaryPredicate> _CCCL_HOST_DEVICE OutputIterator exclusive_scan_by_key(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, T init, BinaryPredicate binary_pred);
template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename T, typename BinaryPredicate> OutputIterator exclusive_scan_by_key(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, T init, BinaryPredicate binary_pred);
template <typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator, typename T, typename BinaryPredicate, typename AssociativeOperator> _CCCL_HOST_DEVICE OutputIterator exclusive_scan_by_key(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, T init, BinaryPredicate binary_pred, AssociativeOperator binary_op);
template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename T, typename BinaryPredicate, typename AssociativeOperator> OutputIterator exclusive_scan_by_key(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, T init, BinaryPredicate binary_pred, AssociativeOperator binary_op);
Functions
Function inclusive_scan_by_key
template <typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator> _CCCL_HOST_DEVICE OutputIterator inclusive_scan_by_key(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result);
inclusive_scan_by_key
computes an inclusive key-value or ‘segmented’ prefix sum operation. The term ‘inclusive’ means that each result includes the corresponding input operand in the partial sum. The term ‘segmented’ means that the partial sums are broken into distinct segments. In other words, within each segment a separate inclusive scan operation is computed. Refer to the code sample below for example usage.
This version of inclusive_scan_by_key
assumes equal_to
as the binary predicate used to compare adjacent keys. Specifically, consecutive iterators i
and i+1
in the range [first1, last1)
belong to the same segment if *i == *(i+1)
, and belong to different segments otherwise.
This version of inclusive_scan_by_key
assumes plus
as the associative operator used to perform the prefix sum. When the input and output sequences are the same, the scan is performed in-place.
Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.
The algorithm’s execution is parallelized as determined by exec
.
The following code snippet demonstrates how to use inclusive_scan_by_key
using the thrust::host
execution policy for parallelization:
#include <thrust/scan.h>
#include <thrust/execution_policy.h>
...
int data[10] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int keys[10] = {0, 0, 0, 1, 1, 2, 3, 3, 3, 3};
thrust::inclusive_scan_by_key(thrust::host, keys, keys + 10, data, data); // in-place scan
// data is now {1, 2, 3, 1, 2, 1, 1, 2, 3, 4};
</code>
inclusive_scan
exclusive_scan_by_key
</code>
Template Parameters:
DerivedPolicy
The name of the derived execution policy.InputIterator1
is a model of Input IteratorInputIterator2
is a model of Input Iterator andInputIterator2's
value_type
is convertible toOutputIterator's
value_type
.OutputIterator
is a model of Output Iterator, and ifx
andy
are objects ofOutputIterator's
value_type
, thenbinary_op(x,y)
is defined.
Function Parameters:
exec
The execution policy to use for parallelization.first1
The beginning of the key sequence.last1
The end of the key sequence.first2
The beginning of the input value sequence.result
The beginning of the output value sequence.
Preconditions:
-
first1
may equalresult
but the range[first1, last1)
and the range[result, result + (last1
-
first1)) shall not overlap otherwise.
</code>
first2
may equalresult
but the range[first2, first2 + (last1 - first1)
and range[result, result + (last1 - first1))
shall not overlap otherwise.
Returns: The end of the output sequence.
Function inclusive_scan_by_key
template <typename InputIterator1, typename InputIterator2, typename OutputIterator> OutputIterator inclusive_scan_by_key(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result);
inclusive_scan_by_key
computes an inclusive key-value or ‘segmented’ prefix sum operation. The term ‘inclusive’ means that each result includes the corresponding input operand in the partial sum. The term ‘segmented’ means that the partial sums are broken into distinct segments. In other words, within each segment a separate inclusive scan operation is computed. Refer to the code sample below for example usage.
This version of inclusive_scan_by_key
assumes equal_to
as the binary predicate used to compare adjacent keys. Specifically, consecutive iterators i
and i+1
in the range [first1, last1)
belong to the same segment if *i == *(i+1)
, and belong to different segments otherwise.
This version of inclusive_scan_by_key
assumes plus
as the associative operator used to perform the prefix sum. When the input and output sequences are the same, the scan is performed in-place.
Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.
The following code snippet demonstrates how to use inclusive_scan_by_key
#include <thrust/scan.h>
int data[10] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int keys[10] = {0, 0, 0, 1, 1, 2, 3, 3, 3, 3};
thrust::inclusive_scan_by_key(keys, keys + 10, data, data); // in-place scan
// data is now {1, 2, 3, 1, 2, 1, 1, 2, 3, 4};
</code>
inclusive_scan
exclusive_scan_by_key
</code>
Template Parameters:
InputIterator1
is a model of Input IteratorInputIterator2
is a model of Input Iterator andInputIterator2's
value_type
is convertible toOutputIterator's
value_type
.OutputIterator
is a model of Output Iterator, and ifx
andy
are objects ofOutputIterator's
value_type
, thenbinary_op(x,y)
is defined.
Function Parameters:
first1
The beginning of the key sequence.last1
The end of the key sequence.first2
The beginning of the input value sequence.result
The beginning of the output value sequence.
Preconditions:
-
first1
may equalresult
but the range[first1, last1)
and the range[result, result + (last1
-
first1)) shall not overlap otherwise.
</code>
first2
may equalresult
but the range[first2, first2 + (last1 - first1)
and range[result, result + (last1 - first1))
shall not overlap otherwise.
Returns: The end of the output sequence.
Function inclusive_scan_by_key
template <typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator, typename BinaryPredicate> _CCCL_HOST_DEVICE OutputIterator inclusive_scan_by_key(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryPredicate binary_pred);
inclusive_scan_by_key
computes an inclusive key-value or ‘segmented’ prefix sum operation. The term ‘inclusive’ means that each result includes the corresponding input operand in the partial sum. The term ‘segmented’ means that the partial sums are broken into distinct segments. In other words, within each segment a separate inclusive scan operation is computed. Refer to the code sample below for example usage.
This version of inclusive_scan_by_key
uses the binary predicate pred
to compare adjacent keys. Specifically, consecutive iterators i
and i+1
in the range [first1, last1)
belong to the same segment if binary_pred(*i, *(i+1))
is true, and belong to different segments otherwise.
This version of inclusive_scan_by_key
assumes plus
as the associative operator used to perform the prefix sum. When the input and output sequences are the same, the scan is performed in-place.
Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.
The algorithm’s execution is parallelized as determined by exec
.
The following code snippet demonstrates how to use inclusive_scan_by_key
using the thrust::host
execution policy for parallelization:
#include <thrust/scan.h>
#include <thrust/functional.h>
#include <thrust/execution_policy.h>
...
int data[10] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int keys[10] = {0, 0, 0, 1, 1, 2, 3, 3, 3, 3};
thrust::equal_to<int> binary_pred;
thrust::inclusive_scan_by_key(thrust::host, keys, keys + 10, data, data, binary_pred); // in-place scan
// data is now {1, 2, 3, 1, 2, 1, 1, 2, 3, 4};
</code>
inclusive_scan
exclusive_scan_by_key
</code>
Template Parameters:
DerivedPolicy
The name of the derived execution policy.InputIterator1
is a model of Input IteratorInputIterator2
is a model of Input Iterator andInputIterator2's
value_type
is convertible toOutputIterator's
value_type
.OutputIterator
is a model of Output Iterator, and ifx
andy
are objects ofOutputIterator's
value_type
, thenbinary_op(x,y)
is defined.BinaryPredicate
is a model of Binary Predicate.
Function Parameters:
exec
The execution policy to use for parallelization.first1
The beginning of the key sequence.last1
The end of the key sequence.first2
The beginning of the input value sequence.result
The beginning of the output value sequence.binary_pred
The binary predicate used to determine equality of keys.
Preconditions:
-
first1
may equalresult
but the range[first1, last1)
and the range[result, result + (last1
-
first1)) shall not overlap otherwise.
</code>
first2
may equalresult
but the range[first2, first2 + (last1 - first1)
and range[result, result + (last1 - first1))
shall not overlap otherwise.
Returns: The end of the output sequence.
Function inclusive_scan_by_key
template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename BinaryPredicate> OutputIterator inclusive_scan_by_key(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryPredicate binary_pred);
inclusive_scan_by_key
computes an inclusive key-value or ‘segmented’ prefix sum operation. The term ‘inclusive’ means that each result includes the corresponding input operand in the partial sum. The term ‘segmented’ means that the partial sums are broken into distinct segments. In other words, within each segment a separate inclusive scan operation is computed. Refer to the code sample below for example usage.
This version of inclusive_scan_by_key
uses the binary predicate pred
to compare adjacent keys. Specifically, consecutive iterators i
and i+1
in the range [first1, last1)
belong to the same segment if binary_pred(*i, *(i+1))
is true, and belong to different segments otherwise.
This version of inclusive_scan_by_key
assumes plus
as the associative operator used to perform the prefix sum. When the input and output sequences are the same, the scan is performed in-place.
Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.
The following code snippet demonstrates how to use inclusive_scan_by_key
#include <thrust/scan.h>
#include <thrust/functional.h>
int data[10] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int keys[10] = {0, 0, 0, 1, 1, 2, 3, 3, 3, 3};
thrust::equal_to<int> binary_pred;
thrust::inclusive_scan_by_key(keys, keys + 10, data, data, binary_pred); // in-place scan
// data is now {1, 2, 3, 1, 2, 1, 1, 2, 3, 4};
</code>
inclusive_scan
exclusive_scan_by_key
</code>
Template Parameters:
InputIterator1
is a model of Input IteratorInputIterator2
is a model of Input Iterator andInputIterator2's
value_type
is convertible toOutputIterator's
value_type
.OutputIterator
is a model of Output Iterator, and ifx
andy
are objects ofOutputIterator's
value_type
, thenbinary_op(x,y)
is defined.BinaryPredicate
is a model of Binary Predicate.
Function Parameters:
first1
The beginning of the key sequence.last1
The end of the key sequence.first2
The beginning of the input value sequence.result
The beginning of the output value sequence.binary_pred
The binary predicate used to determine equality of keys.
Preconditions:
-
first1
may equalresult
but the range[first1, last1)
and the range[result, result + (last1
-
first1)) shall not overlap otherwise.
</code>
first2
may equalresult
but the range[first2, first2 + (last1 - first1)
and range[result, result + (last1 - first1))
shall not overlap otherwise.
Returns: The end of the output sequence.
Function inclusive_scan_by_key
template <typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator, typename BinaryPredicate, typename AssociativeOperator> _CCCL_HOST_DEVICE OutputIterator inclusive_scan_by_key(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryPredicate binary_pred, AssociativeOperator binary_op);
inclusive_scan_by_key
computes an inclusive key-value or ‘segmented’ prefix sum operation. The term ‘inclusive’ means that each result includes the corresponding input operand in the partial sum. The term ‘segmented’ means that the partial sums are broken into distinct segments. In other words, within each segment a separate inclusive scan operation is computed. Refer to the code sample below for example usage.
This version of inclusive_scan_by_key
uses the binary predicate pred
to compare adjacent keys. Specifically, consecutive iterators i
and i+1
in the range [first1, last1)
belong to the same segment if binary_pred(*i, *(i+1))
is true, and belong to different segments otherwise.
This version of inclusive_scan_by_key
uses the associative operator binary_op
to perform the prefix sum. When the input and output sequences are the same, the scan is performed in-place.
Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.
The algorithm’s execution is parallelized as determined by exec
.
The following code snippet demonstrates how to use inclusive_scan_by_key
using the thrust::host
execution policy for parallelization:
#include <thrust/scan.h>
#include <thrust/functional.h>
#include <thrust/execution_policy.h>
...
int data[10] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int keys[10] = {0, 0, 0, 1, 1, 2, 3, 3, 3, 3};
thrust::equal_to<int> binary_pred;
thrust::plus<int> binary_op;
thrust::inclusive_scan_by_key(thrust::host, keys, keys + 10, data, data, binary_pred, binary_op); // in-place scan
// data is now {1, 2, 3, 1, 2, 1, 1, 2, 3, 4};
</code>
inclusive_scan
exclusive_scan_by_key
</code>
Template Parameters:
DerivedPolicy
The name of the derived execution policy.InputIterator1
is a model of Input IteratorInputIterator2
is a model of Input Iterator andInputIterator2's
value_type
is convertible toOutputIterator's
value_type
.OutputIterator
is a model of Output Iterator, and ifx
andy
are objects ofOutputIterator's
value_type
, thenbinary_op(x,y)
is defined.BinaryPredicate
is a model of Binary Predicate.AssociativeOperator
is a model of Binary Function andAssociativeOperator's
result_type
is convertible toOutputIterator's
value_type
.
Function Parameters:
exec
The execution policy to use for parallelization.first1
The beginning of the key sequence.last1
The end of the key sequence.first2
The beginning of the input value sequence.result
The beginning of the output value sequence.binary_pred
The binary predicate used to determine equality of keys.binary_op
The associatve operator used to ‘sum’ values.
Preconditions:
-
first1
may equalresult
but the range[first1, last1)
and the range[result, result + (last1
-
first1)) shall not overlap otherwise.
</code>
first2
may equalresult
but the range[first2, first2 + (last1 - first1)
and range[result, result + (last1 - first1))
shall not overlap otherwise.
Returns: The end of the output sequence.
Function inclusive_scan_by_key
template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename BinaryPredicate, typename AssociativeOperator> OutputIterator inclusive_scan_by_key(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryPredicate binary_pred, AssociativeOperator binary_op);
inclusive_scan_by_key
computes an inclusive key-value or ‘segmented’ prefix sum operation. The term ‘inclusive’ means that each result includes the corresponding input operand in the partial sum. The term ‘segmented’ means that the partial sums are broken into distinct segments. In other words, within each segment a separate inclusive scan operation is computed. Refer to the code sample below for example usage.
This version of inclusive_scan_by_key
uses the binary predicate pred
to compare adjacent keys. Specifically, consecutive iterators i
and i+1
in the range [first1, last1)
belong to the same segment if binary_pred(*i, *(i+1))
is true, and belong to different segments otherwise.
Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.
This version of inclusive_scan_by_key
uses the associative operator binary_op
to perform the prefix sum. When the input and output sequences are the same, the scan is performed in-place.
The following code snippet demonstrates how to use inclusive_scan_by_key
#include <thrust/scan.h>
#include <thrust/functional.h>
int data[10] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int keys[10] = {0, 0, 0, 1, 1, 2, 3, 3, 3, 3};
thrust::equal_to<int> binary_pred;
thrust::plus<int> binary_op;
thrust::inclusive_scan_by_key(keys, keys + 10, data, data, binary_pred, binary_op); // in-place scan
// data is now {1, 2, 3, 1, 2, 1, 1, 2, 3, 4};
</code>
inclusive_scan
exclusive_scan_by_key
</code>
Template Parameters:
InputIterator1
is a model of Input IteratorInputIterator2
is a model of Input Iterator andInputIterator2's
value_type
is convertible toOutputIterator's
value_type
.OutputIterator
is a model of Output Iterator, and ifx
andy
are objects ofOutputIterator's
value_type
, thenbinary_op(x,y)
is defined.BinaryPredicate
is a model of Binary Predicate.AssociativeOperator
is a model of Binary Function andAssociativeOperator's
result_type
is convertible toOutputIterator's
value_type
.
Function Parameters:
first1
The beginning of the key sequence.last1
The end of the key sequence.first2
The beginning of the input value sequence.result
The beginning of the output value sequence.binary_pred
The binary predicate used to determine equality of keys.binary_op
The associatve operator used to ‘sum’ values.
Preconditions:
-
first1
may equalresult
but the range[first1, last1)
and the range[result, result + (last1
-
first1)) shall not overlap otherwise.
</code>
first2
may equalresult
but the range[first2, first2 + (last1 - first1)
and range[result, result + (last1 - first1))
shall not overlap otherwise.
Returns: The end of the output sequence.
Function exclusive_scan_by_key
template <typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator> _CCCL_HOST_DEVICE OutputIterator exclusive_scan_by_key(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result);
exclusive_scan_by_key
computes an exclusive segmented prefix
This version of exclusive_scan_by_key
uses the value 0
to initialize the exclusive scan operation.
This version of exclusive_scan_by_key
assumes plus
as the associative operator used to perform the prefix sum. When the input and output sequences are the same, the scan is performed in-place.
This version of exclusive_scan_by_key
assumes equal_to
as the binary predicate used to compare adjacent keys. Specifically, consecutive iterators i
and i+1
in the range [first1, last1
belong to the same segment if *i == *(i+1)
, and belong to different segments otherwise.
Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.
Refer to the most general form of exclusive_scan_by_key
for additional details.
The algorithm’s execution is parallelized as determined by exec
.
The following code snippet demonstrates how to use exclusive_scan_by_key
using the thrust::host
execution policy for parallelization:
#include <thrust/scan.h>
#include <thrust/execution_policy.h>
...
int keys[10] = {0, 0, 0, 1, 1, 2, 3, 3, 3, 3};
int vals[10] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
thrust::exclusive_scan_by_key(thrust::host, key, key + 10, vals, vals); // in-place scan
// vals is now {0, 1, 2, 0, 1, 0, 0, 1, 2, 3};
</code>
exclusive_scan
</code>
Function Parameters:
exec
The execution policy to use for parallelization.first1
The beginning of the key sequence.last1
The end of the key sequence.first2
The beginning of the input value sequence.result
The beginning of the output value sequence.
Preconditions:
-
first1
may equalresult
but the range[first1, last1)
and the range[result, result + (last1
-
first1)) shall not overlap otherwise.
</code>
first2
may equalresult
but the range[first2, first2 + (last1 - first1)
and range[result, result + (last1 - first1))
shall not overlap otherwise.
Function exclusive_scan_by_key
template <typename InputIterator1, typename InputIterator2, typename OutputIterator> OutputIterator exclusive_scan_by_key(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result);
exclusive_scan_by_key
computes an exclusive segmented prefix
This version of exclusive_scan_by_key
uses the value 0
to initialize the exclusive scan operation.
This version of exclusive_scan_by_key
assumes plus
as the associative operator used to perform the prefix sum. When the input and output sequences are the same, the scan is performed in-place.
This version of exclusive_scan_by_key
assumes equal_to
as the binary predicate used to compare adjacent keys. Specifically, consecutive iterators i
and i+1
in the range [first1, last1
belong to the same segment if *i == *(i+1)
, and belong to different segments otherwise.
Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.
Refer to the most general form of exclusive_scan_by_key
for additional details.
The following code snippet demonstrates how to use exclusive_scan_by_key
.
#include <thrust/scan.h>
int keys[10] = {0, 0, 0, 1, 1, 2, 3, 3, 3, 3};
int vals[10] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
thrust::exclusive_scan_by_key(key, key + 10, vals, vals); // in-place scan
// vals is now {0, 1, 2, 0, 1, 0, 0, 1, 2, 3};
</code>
exclusive_scan
</code>
Function Parameters:
first1
The beginning of the key sequence.last1
The end of the key sequence.first2
The beginning of the input value sequence.result
The beginning of the output value sequence.
Preconditions:
-
first1
may equalresult
but the range[first1, last1)
and the range[result, result + (last1
-
first1)) shall not overlap otherwise.
</code>
first2
may equalresult
but the range[first2, first2 + (last1 - first1)
and range[result, result + (last1 - first1))
shall not overlap otherwise.
Function exclusive_scan_by_key
template <typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator, typename T> _CCCL_HOST_DEVICE OutputIterator exclusive_scan_by_key(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, T init);
exclusive_scan_by_key
computes an exclusive key-value or ‘segmented’ prefix sum operation. The term ‘exclusive’ means that each result does not include the corresponding input operand in the partial sum. The term ‘segmented’ means that the partial sums are broken into distinct segments. In other words, within each segment a separate exclusive scan operation is computed. Refer to the code sample below for example usage.
This version of exclusive_scan_by_key
uses the value init
to initialize the exclusive scan operation.
Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.
The algorithm’s execution is parallelized as determined by exec
.
The following code snippet demonstrates how to use exclusive_scan_by_key
using the thrust::host
execution policy for parallelization:
#include <thrust/scan.h>
#include <thrust/functional.h>
#include <thrust/execution_policy.h>
...
int keys[10] = {0, 0, 0, 1, 1, 2, 3, 3, 3, 3};
int vals[10] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int init = 5;
thrust::exclusive_scan_by_key(thrust::host, key, key + 10, vals, vals, init); // in-place scan
// vals is now {5, 6, 7, 5, 6, 5, 5, 6, 7, 8};
</code>
exclusive_scan
inclusive_scan_by_key
</code>
Function Parameters:
exec
The execution policy to use for parallelization.first1
The beginning of the key sequence.last1
The end of the key sequence.first2
The beginning of the input value sequence.result
The beginning of the output value sequence.init
The initial of the exclusive sum value.
Preconditions:
-
first1
may equalresult
but the range[first1, last1)
and the range[result, result + (last1
-
first1)) shall not overlap otherwise.
</code>
first2
may equalresult
but the range[first2, first2 + (last1 - first1)
and range[result, result + (last1 - first1))
shall not overlap otherwise.
Returns: The end of the output sequence.
Function exclusive_scan_by_key
template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename T> OutputIterator exclusive_scan_by_key(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, T init);
exclusive_scan_by_key
computes an exclusive key-value or ‘segmented’ prefix sum operation. The term ‘exclusive’ means that each result does not include the corresponding input operand in the partial sum. The term ‘segmented’ means that the partial sums are broken into distinct segments. In other words, within each segment a separate exclusive scan operation is computed. Refer to the code sample below for example usage.
This version of exclusive_scan_by_key
uses the value init
to initialize the exclusive scan operation.
Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.
The following code snippet demonstrates how to use exclusive_scan_by_key
#include <thrust/scan.h>
#include <thrust/functional.h>
int keys[10] = {0, 0, 0, 1, 1, 2, 3, 3, 3, 3};
int vals[10] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int init = 5;
thrust::exclusive_scan_by_key(key, key + 10, vals, vals, init); // in-place scan
// vals is now {5, 6, 7, 5, 6, 5, 5, 6, 7, 8};
</code>
exclusive_scan
inclusive_scan_by_key
</code>
Function Parameters:
first1
The beginning of the key sequence.last1
The end of the key sequence.first2
The beginning of the input value sequence.result
The beginning of the output value sequence.init
The initial of the exclusive sum value.
Preconditions:
-
first1
may equalresult
but the range[first1, last1)
and the range[result, result + (last1
-
first1)) shall not overlap otherwise.
</code>
first2
may equalresult
but the range[first2, first2 + (last1 - first1)
and range[result, result + (last1 - first1))
shall not overlap otherwise.
Returns: The end of the output sequence.
Function exclusive_scan_by_key
template <typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator, typename T, typename BinaryPredicate> _CCCL_HOST_DEVICE OutputIterator exclusive_scan_by_key(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, T init, BinaryPredicate binary_pred);
exclusive_scan_by_key
computes an exclusive key-value or ‘segmented’ prefix sum operation. The term ‘exclusive’ means that each result does not include the corresponding input operand in the partial sum. The term ‘segmented’ means that the partial sums are broken into distinct segments. In other words, within each segment a separate exclusive scan operation is computed. Refer to the code sample below for example usage.
This version of exclusive_scan_by_key
uses the value init
to initialize the exclusive scan operation.
This version of exclusive_scan_by_key
uses the binary predicate binary_pred
to compare adjacent keys. Specifically, consecutive iterators i
and i+1
in the range [first1, last1)
belong to the same segment if binary_pred(*i, *(i+1))
is true, and belong to different segments otherwise.
Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.
The algorithm’s execution is parallelized as determined by exec
.
The following code snippet demonstrates how to use exclusive_scan_by_key
using the thrust::host
execution policy for parallelization:
#include <thrust/scan.h>
#include <thrust/functional.h>
#include <thrust/execution_policy.h>
...
int keys[10] = {0, 0, 0, 1, 1, 2, 3, 3, 3, 3};
int vals[10] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int init = 5;
thrust::equal_to<int> binary_pred;
thrust::exclusive_scan_by_key(thrust::host, key, key + 10, vals, vals, init, binary_pred); // in-place scan
// vals is now {5, 6, 7, 5, 6, 5, 5, 6, 7, 8};
</code>
exclusive_scan
inclusive_scan_by_key
</code>
Function Parameters:
exec
The execution policy to use for parallelization.first1
The beginning of the key sequence.last1
The end of the key sequence.first2
The beginning of the input value sequence.result
The beginning of the output value sequence.init
The initial of the exclusive sum value.binary_pred
The binary predicate used to determine equality of keys.
Preconditions:
-
first1
may equalresult
but the range[first1, last1)
and the range[result, result + (last1
-
first1)) shall not overlap otherwise.
</code>
first2
may equalresult
but the range[first2, first2 + (last1 - first1)
and range[result, result + (last1 - first1))
shall not overlap otherwise.
Returns: The end of the output sequence.
Function exclusive_scan_by_key
template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename T, typename BinaryPredicate> OutputIterator exclusive_scan_by_key(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, T init, BinaryPredicate binary_pred);
exclusive_scan_by_key
computes an exclusive key-value or ‘segmented’ prefix sum operation. The term ‘exclusive’ means that each result does not include the corresponding input operand in the partial sum. The term ‘segmented’ means that the partial sums are broken into distinct segments. In other words, within each segment a separate exclusive scan operation is computed. Refer to the code sample below for example usage.
This version of exclusive_scan_by_key
uses the value init
to initialize the exclusive scan operation.
This version of exclusive_scan_by_key
uses the binary predicate binary_pred
to compare adjacent keys. Specifically, consecutive iterators i
and i+1
in the range [first1, last1)
belong to the same segment if binary_pred(*i, *(i+1))
is true, and belong to different segments otherwise.
Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.
The following code snippet demonstrates how to use exclusive_scan_by_key
#include <thrust/scan.h>
#include <thrust/functional.h>
int keys[10] = {0, 0, 0, 1, 1, 2, 3, 3, 3, 3};
int vals[10] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int init = 5;
thrust::equal_to<int> binary_pred;
thrust::exclusive_scan_by_key(key, key + 10, vals, vals, init, binary_pred); // in-place scan
// vals is now {5, 6, 7, 5, 6, 5, 5, 6, 7, 8};
</code>
exclusive_scan
inclusive_scan_by_key
</code>
Function Parameters:
first1
The beginning of the key sequence.last1
The end of the key sequence.first2
The beginning of the input value sequence.result
The beginning of the output value sequence.init
The initial of the exclusive sum value.binary_pred
The binary predicate used to determine equality of keys.
Preconditions:
-
first1
may equalresult
but the range[first1, last1)
and the range[result, result + (last1
-
first1)) shall not overlap otherwise.
</code>
first2
may equalresult
but the range[first2, first2 + (last1 - first1)
and range[result, result + (last1 - first1))
shall not overlap otherwise.
Returns: The end of the output sequence.
Function exclusive_scan_by_key
template <typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator, typename T, typename BinaryPredicate, typename AssociativeOperator> _CCCL_HOST_DEVICE OutputIterator exclusive_scan_by_key(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, T init, BinaryPredicate binary_pred, AssociativeOperator binary_op);
exclusive_scan_by_key
computes an exclusive key-value or ‘segmented’ prefix sum operation. The term ‘exclusive’ means that each result does not include the corresponding input operand in the partial sum. The term ‘segmented’ means that the partial sums are broken into distinct segments. In other words, within each segment a separate exclusive scan operation is computed. Refer to the code sample below for example usage.
This version of exclusive_scan_by_key
uses the value init
to initialize the exclusive scan operation.
This version of exclusive_scan_by_key
uses the binary predicate binary_pred
to compare adjacent keys. Specifically, consecutive iterators i
and i+1
in the range [first1, last1)
belong to the same segment if binary_pred(*i, *(i+1))
is true, and belong to different segments otherwise.
This version of exclusive_scan_by_key
uses the associative operator binary_op
to perform the prefix sum. When the input and output sequences are the same, the scan is performed in-place.
Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.
The algorithm’s execution is parallelized as determined by exec
.
The following code snippet demonstrates how to use exclusive_scan_by_key
using the thrust::host
execution policy for parallelization:
#include <thrust/scan.h>
#include <thrust/functional.h>
#include <thrust/execution_policy.h>
...
int keys[10] = {0, 0, 0, 1, 1, 2, 3, 3, 3, 3};
int vals[10] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int init = 5;
thrust::equal_to<int> binary_pred;
thrust::plus<int> binary_op;
thrust::exclusive_scan_by_key(thrust::host, key, key + 10, vals, vals, init, binary_pred, binary_op); // in-place
scan
// vals is now {5, 6, 7, 5, 6, 5, 5, 6, 7, 8};
</code>
exclusive_scan
inclusive_scan_by_key
</code>
Template Parameters:
DerivedPolicy
The name of the derived execution policy.InputIterator1
is a model of Input IteratorInputIterator2
is a model of Input Iterator andInputIterator2's
value_type
is convertible toOutputIterator's
value_type
.OutputIterator
is a model of Output Iterator, and ifx
andy
are objects ofOutputIterator's
value_type
, thenbinary_op(x,y)
is defined.T
is convertible toOutputIterator's
value_type
.BinaryPredicate
is a model of Binary Predicate.AssociativeOperator
is a model of Binary Function andAssociativeOperator's
result_type
is convertible toOutputIterator's
value_type
.
Function Parameters:
exec
The execution policy to use for parallelization.first1
The beginning of the key sequence.last1
The end of the key sequence.first2
The beginning of the input value sequence.result
The beginning of the output value sequence.init
The initial of the exclusive sum value.binary_pred
The binary predicate used to determine equality of keys.binary_op
The associatve operator used to ‘sum’ values.
Preconditions:
-
first1
may equalresult
but the range[first1, last1)
and the range[result, result + (last1
-
first1)) shall not overlap otherwise.
</code>
first2
may equalresult
but the range[first2, first2 + (last1 - first1)
and range[result, result + (last1 - first1))
shall not overlap otherwise.
Returns: The end of the output sequence.
Function exclusive_scan_by_key
template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename T, typename BinaryPredicate, typename AssociativeOperator> OutputIterator exclusive_scan_by_key(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, T init, BinaryPredicate binary_pred, AssociativeOperator binary_op);
exclusive_scan_by_key
computes an exclusive key-value or ‘segmented’ prefix sum operation. The term ‘exclusive’ means that each result does not include the corresponding input operand in the partial sum. The term ‘segmented’ means that the partial sums are broken into distinct segments. In other words, within each segment a separate exclusive scan operation is computed. Refer to the code sample below for example usage.
This version of exclusive_scan_by_key
uses the value init
to initialize the exclusive scan operation.
This version of exclusive_scan_by_key
uses the binary predicate binary_pred
to compare adjacent keys. Specifically, consecutive iterators i
and i+1
in the range [first1, last1)
belong to the same segment if binary_pred(*i, *(i+1))
is true, and belong to different segments otherwise.
This version of exclusive_scan_by_key
uses the associative operator binary_op
to perform the prefix sum. When the input and output sequences are the same, the scan is performed in-place.
Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.
The following code snippet demonstrates how to use exclusive_scan_by_key
#include <thrust/scan.h>
#include <thrust/functional.h>
int keys[10] = {0, 0, 0, 1, 1, 2, 3, 3, 3, 3};
int vals[10] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int init = 5;
thrust::equal_to<int> binary_pred;
thrust::plus<int> binary_op;
thrust::exclusive_scan_by_key(key, key + 10, vals, vals, init, binary_pred, binary_op); // in-place scan
// vals is now {5, 6, 7, 5, 6, 5, 5, 6, 7, 8};
</code>
exclusive_scan
inclusive_scan_by_key
</code>
Template Parameters:
InputIterator1
is a model of Input IteratorInputIterator2
is a model of Input Iterator andInputIterator2's
value_type
is convertible toOutputIterator's
value_type
.OutputIterator
is a model of Output Iterator, and ifx
andy
are objects ofOutputIterator's
value_type
, thenbinary_op(x,y)
is defined.T
is convertible toOutputIterator's
value_type
.BinaryPredicate
is a model of Binary Predicate.AssociativeOperator
is a model of Binary Function andAssociativeOperator's
result_type
is convertible toOutputIterator's
value_type
.
Function Parameters:
first1
The beginning of the key sequence.last1
The end of the key sequence.first2
The beginning of the input value sequence.result
The beginning of the output value sequence.init
The initial of the exclusive sum value.binary_pred
The binary predicate used to determine equality of keys.binary_op
The associatve operator used to ‘sum’ values.
Preconditions:
-
first1
may equalresult
but the range[first1, last1)
and the range[result, result + (last1
-
first1)) shall not overlap otherwise.
</code>
first2
may equalresult
but the range[first2, first2 + (last1 - first1)
and range[result, result + (last1 - first1))
shall not overlap otherwise.
Returns: The end of the output sequence.