# Reductions

## Groups

` template <typename DerivedPolicy, typename InputIterator> _CCCL_HOST_DEVICE thrust::iterator_traits< InputIterator >::value_type `

**reduce**(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator first, InputIterator last);

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

template <typename DerivedPolicy, typename InputIterator, typename T> _CCCL_HOST_DEVICE T **reduce**(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator first, InputIterator last, T init);

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

template <typename DerivedPolicy, typename InputIterator, typename T, typename BinaryFunction> _CCCL_HOST_DEVICE T **reduce**(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator first, InputIterator last, T init, BinaryFunction binary_op);

template <typename InputIterator, typename T, typename BinaryFunction> T **reduce**(InputIterator first, InputIterator last, T init, BinaryFunction binary_op);

template <typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator1, typename OutputIterator2> _CCCL_HOST_DEVICE thrust::pair< OutputIterator1, OutputIterator2 > **reduce_by_key**(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator1 keys_first, InputIterator1 keys_last, InputIterator2 values_first, OutputIterator1 keys_output, OutputIterator2 values_output);

template <typename InputIterator1, typename InputIterator2, typename OutputIterator1, typename OutputIterator2> thrust::pair< OutputIterator1, OutputIterator2 > **reduce_by_key**(InputIterator1 keys_first, InputIterator1 keys_last, InputIterator2 values_first, OutputIterator1 keys_output, OutputIterator2 values_output);

template <typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator1, typename OutputIterator2, typename BinaryPredicate> _CCCL_HOST_DEVICE thrust::pair< OutputIterator1, OutputIterator2 > **reduce_by_key**(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator1 keys_first, InputIterator1 keys_last, InputIterator2 values_first, OutputIterator1 keys_output, OutputIterator2 values_output, BinaryPredicate binary_pred);

template <typename InputIterator1, typename InputIterator2, typename OutputIterator1, typename OutputIterator2, typename BinaryPredicate> thrust::pair< OutputIterator1, OutputIterator2 > **reduce_by_key**(InputIterator1 keys_first, InputIterator1 keys_last, InputIterator2 values_first, OutputIterator1 keys_output, OutputIterator2 values_output, BinaryPredicate binary_pred);

template <typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator1, typename OutputIterator2, typename BinaryPredicate, typename BinaryFunction> _CCCL_HOST_DEVICE thrust::pair< OutputIterator1, OutputIterator2 > **reduce_by_key**(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator1 keys_first, InputIterator1 keys_last, InputIterator2 values_first, OutputIterator1 keys_output, OutputIterator2 values_output, BinaryPredicate binary_pred, BinaryFunction binary_op);

template <typename InputIterator1, typename InputIterator2, typename OutputIterator1, typename OutputIterator2, typename BinaryPredicate, typename BinaryFunction> thrust::pair< OutputIterator1, OutputIterator2 > **reduce_by_key**(InputIterator1 keys_first, InputIterator1 keys_last, InputIterator2 values_first, OutputIterator1 keys_output, OutputIterator2 values_output, BinaryPredicate binary_pred, BinaryFunction binary_op);

## Functions

### Function `reduce`

` template <typename DerivedPolicy, typename InputIterator> _CCCL_HOST_DEVICE thrust::iterator_traits< InputIterator >::value_type `

**reduce**(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator first, InputIterator last);`reduce`

is a generalization of summation: it computes the sum (or some other binary operation) of all the elements in the range `[first, last)`

. This version of `reduce`

uses `0`

as the initial value of the reduction. `reduce`

is similar to the C++ Standard Template Library’s `std::accumulate`

. The primary difference between the two functions is that `std::accumulate`

guarantees the order of summation, while `reduce`

requires associativity of the binary operation to parallelize the reduction.

Note that `reduce`

also assumes that the binary reduction operator (in this case operator+) is commutative. If the reduction operator is not commutative then `thrust::reduce`

should not be used. Instead, one could use `inclusive_scan`

(which does not require commutativity) and select the last element of the output array.

The algorithm’s execution is parallelized as determined by `exec`

.

The following code snippet demonstrates how to use `reduce`

to compute the sum of a sequence of integers using the `thrust::host`

execution policy for parallelization:

```
#include <thrust/reduce.h>
#include <thrust/execution_policy.h>
...
int data[6] = {1, 0, 2, 2, 1, 3};
int result = thrust::reduce(thrust::host, data, data + 6);
// result == 9
```

**Template Parameters**:

The name of the derived execution policy.`DerivedPolicy`

is a model of Input Iterator and if`InputIterator`

`x`

and`y`

are objects of`InputIterator's`

`value_type`

, then`x + y`

is defined and is convertible to`InputIterator's`

`value_type`

. If`T`

is`InputIterator's`

`value_type`

, then`T(0)`

is defined.

**Function Parameters**:

The execution policy to use for parallelization.`exec`

The beginning of the sequence.`first`

The end of the sequence.`last`

**Returns**: The result of the reduction.

**See**: https://en.cppreference.com/w/cpp/algorithm/accumulate

### Function `reduce`

` template <typename InputIterator> thrust::iterator_traits< InputIterator >::value_type `

**reduce**(InputIterator first, InputIterator last);`reduce`

is a generalization of summation: it computes the sum (or some other binary operation) of all the elements in the range `[first, last)`

. This version of `reduce`

uses `0`

as the initial value of the reduction. `reduce`

is similar to the C++ Standard Template Library’s `std::accumulate`

. The primary difference between the two functions is that `std::accumulate`

guarantees the order of summation, while `reduce`

requires associativity of the binary operation to parallelize the reduction.

Note that `reduce`

also assumes that the binary reduction operator (in this case operator+) is commutative. If the reduction operator is not commutative then `thrust::reduce`

should not be used. Instead, one could use `inclusive_scan`

(which does not require commutativity) and select the last element of the output array.

The following code snippet demonstrates how to use `reduce`

to compute the sum of a sequence of integers.

```
#include <thrust/reduce.h>
...
int data[6] = {1, 0, 2, 2, 1, 3};
int result = thrust::reduce(data, data + 6);
// result == 9
```

**Template Parameters**: ** InputIterator**: is a model of Input Iterator and if

`x`

and `y`

are objects of `InputIterator's`

`value_type`

, then `x + y`

is defined and is convertible to `InputIterator's`

`value_type`

. If `T`

is `InputIterator's`

`value_type`

, then `T(0)`

is defined.**Function Parameters**:

The beginning of the sequence.`first`

The end of the sequence.`last`

**Returns**: The result of the reduction.

**See**: https://en.cppreference.com/w/cpp/algorithm/accumulate

### Function `reduce`

` template <typename DerivedPolicy, typename InputIterator, typename T> _CCCL_HOST_DEVICE T `

**reduce**(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator first, InputIterator last, T init);`reduce`

is a generalization of summation: it computes the sum (or some other binary operation) of all the elements in the range `[first, last)`

. This version of `reduce`

uses `init`

as the initial value of the reduction. `reduce`

is similar to the C++ Standard Template Library’s `std::accumulate`

. The primary difference between the two functions is that `std::accumulate`

guarantees the order of summation, while `reduce`

requires associativity of the binary operation to parallelize the reduction.

Note that `reduce`

also assumes that the binary reduction operator (in this case operator+) is commutative. If the reduction operator is not commutative then `thrust::reduce`

should not be used. Instead, one could use `inclusive_scan`

(which does not require commutativity) and select the last element of the output array.

The algorithm’s execution is parallelized as determined by `exec`

.

The following code snippet demonstrates how to use `reduce`

to compute the sum of a sequence of integers including an intialization value using the `thrust::host`

execution policy for parallelization:

```
#include <thrust/reduce.h>
#include <thrust/execution_policy.h>
...
int data[6] = {1, 0, 2, 2, 1, 3};
int result = thrust::reduce(thrust::host, data, data + 6, 1);
// result == 10
```

**Template Parameters**:

The name of the derived execution policy.`DerivedPolicy`

is a model of Input Iterator and if`InputIterator`

`x`

and`y`

are objects of`InputIterator's`

`value_type`

, then`x + y`

is defined and is convertible to`T`

.is convertible to`T`

`InputIterator's`

`value_type`

.

**Function Parameters**:

The execution policy to use for parallelization.`exec`

The beginning of the input sequence.`first`

The end of the input sequence.`last`

The initial value.`init`

**Returns**: The result of the reduction.

**See**: https://en.cppreference.com/w/cpp/algorithm/accumulate

### Function `reduce`

` template <typename InputIterator, typename T> T `

**reduce**(InputIterator first, InputIterator last, T init);`reduce`

is a generalization of summation: it computes the sum (or some other binary operation) of all the elements in the range `[first, last)`

. This version of `reduce`

uses `init`

as the initial value of the reduction. `reduce`

is similar to the C++ Standard Template Library’s `std::accumulate`

. The primary difference between the two functions is that `std::accumulate`

guarantees the order of summation, while `reduce`

requires associativity of the binary operation to parallelize the reduction.

`reduce`

also assumes that the binary reduction operator (in this case operator+) is commutative. If the reduction operator is not commutative then `thrust::reduce`

should not be used. Instead, one could use `inclusive_scan`

(which does not require commutativity) and select the last element of the output array.

The following code snippet demonstrates how to use `reduce`

to compute the sum of a sequence of integers including an intialization value.

```
#include <thrust/reduce.h>
...
int data[6] = {1, 0, 2, 2, 1, 3};
int result = thrust::reduce(data, data + 6, 1);
// result == 10
```

**Template Parameters**:

is a model of Input Iterator and if`InputIterator`

`x`

and`y`

are objects of`InputIterator's`

`value_type`

, then`x + y`

is defined and is convertible to`T`

.is convertible to`T`

`InputIterator's`

`value_type`

.

**Function Parameters**:

The beginning of the input sequence.`first`

The end of the input sequence.`last`

The initial value.`init`

**Returns**: The result of the reduction.

**See**: https://en.cppreference.com/w/cpp/algorithm/accumulate

### Function `reduce`

` template <typename DerivedPolicy, typename InputIterator, typename T, typename BinaryFunction> _CCCL_HOST_DEVICE T `

**reduce**(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator first, InputIterator last, T init, BinaryFunction binary_op);`reduce`

is a generalization of summation: it computes the sum (or some other binary operation) of all the elements in the range `[first, last)`

. This version of `reduce`

uses `init`

as the initial value of the reduction and `binary_op`

as the binary function used for summation. `reduce`

is similar to the C++ Standard Template Library’s `std::accumulate`

. The primary difference between the two functions is that `std::accumulate`

guarantees the order of summation, while `reduce`

requires associativity of `binary_op`

to parallelize the reduction.

Note that `reduce`

also assumes that the binary reduction operator (in this case `binary_op`

) is commutative. If the reduction operator is not commutative then `thrust::reduce`

should not be used. Instead, one could use `inclusive_scan`

(which does not require commutativity) and select the last element of the output array.

The algorithm’s execution is parallelized as determined by `exec`

.

The following code snippet demonstrates how to use `reduce`

to compute the maximum value of a sequence of integers using the `thrust::host`

execution policy for parallelization:

```
#include <thrust/reduce.h>
#include <thrust/functional.h>
#include <thrust/execution_policy.h>
...
int data[6] = {1, 0, 2, 2, 1, 3};
int result = thrust::reduce(thrust::host,
data, data + 6,
-1,
thrust::maximum<int>());
// result == 3
```

**Template Parameters**:

The name of the derived execution policy.`DerivedPolicy`

is a model of Input Iterator and`InputIterator`

`InputIterator's`

`value_type`

is convertible to`T`

.is a model of Assignable, and is convertible to`T`

`BinaryFunction's`

`first_argument_type`

and`second_argument_type`

.is a model of Binary Function, and`BinaryFunction`

`BinaryFunction's`

`result_type`

is convertible to`OutputType`

.

**Function Parameters**:

The execution policy to use for parallelization.`exec`

The beginning of the input sequence.`first`

The end of the input sequence.`last`

The initial value.`init`

The binary function used to ‘sum’ values.`binary_op`

**Returns**: The result of the reduction.

**See**:

- https://en.cppreference.com/w/cpp/algorithm/accumulate
- transform_reduce

### Function `reduce`

` template <typename InputIterator, typename T, typename BinaryFunction> T `

**reduce**(InputIterator first, InputIterator last, T init, BinaryFunction binary_op);`reduce`

is a generalization of summation: it computes the sum (or some other binary operation) of all the elements in the range `[first, last)`

. This version of `reduce`

uses `init`

as the initial value of the reduction and `binary_op`

as the binary function used for summation. `reduce`

is similar to the C++ Standard Template Library’s `std::accumulate`

. The primary difference between the two functions is that `std::accumulate`

guarantees the order of summation, while `reduce`

requires associativity of `binary_op`

to parallelize the reduction.

Note that `reduce`

also assumes that the binary reduction operator (in this case `binary_op`

) is commutative. If the reduction operator is not commutative then `thrust::reduce`

should not be used. Instead, one could use `inclusive_scan`

(which does not require commutativity) and select the last element of the output array.

The following code snippet demonstrates how to use `reduce`

to compute the maximum value of a sequence of integers.

```
#include <thrust/reduce.h>
#include <thrust/functional.h>
...
int data[6] = {1, 0, 2, 2, 1, 3};
int result = thrust::reduce(data, data + 6,
-1,
thrust::maximum<int>());
// result == 3
```

**Template Parameters**:

is a model of Input Iterator and`InputIterator`

`InputIterator's`

`value_type`

is convertible to`T`

.is a model of Assignable, and is convertible to`T`

`BinaryFunction's`

`first_argument_type`

and`second_argument_type`

.is a model of Binary Function, and`BinaryFunction`

`BinaryFunction's`

`result_type`

is convertible to`OutputType`

.

**Function Parameters**:

The beginning of the input sequence.`first`

The end of the input sequence.`last`

The initial value.`init`

The binary function used to ‘sum’ values.`binary_op`

**Returns**: The result of the reduction.

**See**:

- https://en.cppreference.com/w/cpp/algorithm/accumulate
- transform_reduce

### Function `reduce_by_key`

` template <typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator1, typename OutputIterator2> _CCCL_HOST_DEVICE thrust::pair< OutputIterator1, OutputIterator2 > `

**reduce_by_key**(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator1 keys_first, InputIterator1 keys_last, InputIterator2 values_first, OutputIterator1 keys_output, OutputIterator2 values_output);`reduce_by_key`

is a generalization of `reduce`

to key-value pairs. For each group of consecutive keys in the range `[keys_first, keys_last)`

that are equal, `reduce_by_key`

copies the first element of the group to the `keys_output`

. The corresponding values in the range are reduced using the `plus`

and the result copied to `values_output`

.

This version of `reduce_by_key`

uses the function object `equal_to`

to test for equality and `plus`

to reduce values with equal keys.

The algorithm’s execution is parallelized as determined by `exec`

.

The following code snippet demonstrates how to use `reduce_by_key`

to compact a sequence of key/value pairs and sum values with equal keys using the `thrust::host`

execution policy for parallelization:

```
#include <thrust/reduce.h>
#include <thrust/execution_policy.h>
...
const int N = 7;
int A[N] = {1, 3, 3, 3, 2, 2, 1}; // input keys
int B[N] = {9, 8, 7, 6, 5, 4, 3}; // input values
int C[N]; // output keys
int D[N]; // output values
thrust::pair<int*,int*> new_end;
new_end = thrust::reduce_by_key(thrust::host, A, A + N, B, C, D);
// The first four keys in C are now {1, 3, 2, 1} and new_end.first - C is 4.
// The first four values in D are now {9, 21, 9, 3} and new_end.second - D is 4.
```

**Template Parameters**:

The name of the derived execution policy.`DerivedPolicy`

is a model of Input Iterator,`InputIterator1`

is a model of Input Iterator,`InputIterator2`

is a model of Output Iterator and and`OutputIterator1`

`InputIterator1's`

`value_type`

is convertible to`OutputIterator1's`

`value_type`

.is a model of Output Iterator and and`OutputIterator2`

`InputIterator2's`

`value_type`

is convertible to`OutputIterator2's`

`value_type`

.

**Function Parameters**:

The execution policy to use for parallelization.`exec`

The beginning of the input key range.`keys_first`

The end of the input key range.`keys_last`

The beginning of the input value range.`values_first`

The beginning of the output key range.`keys_output`

The beginning of the output value range.`values_output`

**Preconditions**: The input ranges shall not overlap either output range.

**Returns**: A pair of iterators at end of the ranges `[keys_output, keys_output_last)`

and `[values_output, values_output_last)`

.

**See**:

- reduce
- unique_copy
- unique_by_key
- unique_by_key_copy

### Function `reduce_by_key`

` template <typename InputIterator1, typename InputIterator2, typename OutputIterator1, typename OutputIterator2> thrust::pair< OutputIterator1, OutputIterator2 > `

**reduce_by_key**(InputIterator1 keys_first, InputIterator1 keys_last, InputIterator2 values_first, OutputIterator1 keys_output, OutputIterator2 values_output);`reduce_by_key`

is a generalization of `reduce`

to key-value pairs. For each group of consecutive keys in the range `[keys_first, keys_last)`

that are equal, `reduce_by_key`

copies the first element of the group to the `keys_output`

. The corresponding values in the range are reduced using the `plus`

and the result copied to `values_output`

.

This version of `reduce_by_key`

uses the function object `equal_to`

to test for equality and `plus`

to reduce values with equal keys.

The following code snippet demonstrates how to use `reduce_by_key`

to compact a sequence of key/value pairs and sum values with equal keys.

```
#include <thrust/reduce.h>
...
const int N = 7;
int A[N] = {1, 3, 3, 3, 2, 2, 1}; // input keys
int B[N] = {9, 8, 7, 6, 5, 4, 3}; // input values
int C[N]; // output keys
int D[N]; // output values
thrust::pair<int*,int*> new_end;
new_end = thrust::reduce_by_key(A, A + N, B, C, D);
// The first four keys in C are now {1, 3, 2, 1} and new_end.first - C is 4.
// The first four values in D are now {9, 21, 9, 3} and new_end.second - D is 4.
```

**Template Parameters**:

is a model of Input Iterator,`InputIterator1`

is a model of Input Iterator,`InputIterator2`

is a model of Output Iterator and and`OutputIterator1`

`InputIterator1's`

`value_type`

is convertible to`OutputIterator1's`

`value_type`

.is a model of Output Iterator and and`OutputIterator2`

`InputIterator2's`

`value_type`

is convertible to`OutputIterator2's`

`value_type`

.

**Function Parameters**:

The beginning of the input key range.`keys_first`

The end of the input key range.`keys_last`

The beginning of the input value range.`values_first`

The beginning of the output key range.`keys_output`

The beginning of the output value range.`values_output`

**Preconditions**: The input ranges shall not overlap either output range.

**Returns**: A pair of iterators at end of the ranges `[keys_output, keys_output_last)`

and `[values_output, values_output_last)`

.

**See**:

- reduce
- unique_copy
- unique_by_key
- unique_by_key_copy

### Function `reduce_by_key`

` template <typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator1, typename OutputIterator2, typename BinaryPredicate> _CCCL_HOST_DEVICE thrust::pair< OutputIterator1, OutputIterator2 > `

**reduce_by_key**(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator1 keys_first, InputIterator1 keys_last, InputIterator2 values_first, OutputIterator1 keys_output, OutputIterator2 values_output, BinaryPredicate binary_pred);`reduce_by_key`

is a generalization of `reduce`

to key-value pairs. For each group of consecutive keys in the range `[keys_first, keys_last)`

that are equal, `reduce_by_key`

copies the first element of the group to the `keys_output`

. The corresponding values in the range are reduced using the `plus`

and the result copied to `values_output`

.

This version of `reduce_by_key`

uses the function object `binary_pred`

to test for equality and `plus`

to reduce values with equal keys.

The algorithm’s execution is parallelized as determined by `exec`

.

The following code snippet demonstrates how to use `reduce_by_key`

to compact a sequence of key/value pairs and sum values with equal keys using the `thrust::host`

execution policy for parallelization:

```
#include <thrust/reduce.h>
#include <thrust/execution_policy.h>
...
const int N = 7;
int A[N] = {1, 3, 3, 3, 2, 2, 1}; // input keys
int B[N] = {9, 8, 7, 6, 5, 4, 3}; // input values
int C[N]; // output keys
int D[N]; // output values
thrust::pair<int*,int*> new_end;
thrust::equal_to<int> binary_pred;
new_end = thrust::reduce_by_key(thrust::host, A, A + N, B, C, D, binary_pred);
// The first four keys in C are now {1, 3, 2, 1} and new_end.first - C is 4.
// The first four values in D are now {9, 21, 9, 3} and new_end.second - D is 4.
```

**Template Parameters**:

The name of the derived execution policy.`DerivedPolicy`

is a model of Input Iterator,`InputIterator1`

is a model of Input Iterator,`InputIterator2`

is a model of Output Iterator and and`OutputIterator1`

`InputIterator1's`

`value_type`

is convertible to`OutputIterator1's`

`value_type`

.is a model of Output Iterator and and`OutputIterator2`

`InputIterator2's`

`value_type`

is convertible to`OutputIterator2's`

`value_type`

.is a model of Binary Predicate.`BinaryPredicate`

**Function Parameters**:

The execution policy to use for parallelization.`exec`

The beginning of the input key range.`keys_first`

The end of the input key range.`keys_last`

The beginning of the input value range.`values_first`

The beginning of the output key range.`keys_output`

The beginning of the output value range.`values_output`

The binary predicate used to determine equality.`binary_pred`

**Preconditions**: The input ranges shall not overlap either output range.

**Returns**: A pair of iterators at end of the ranges `[keys_output, keys_output_last)`

and `[values_output, values_output_last)`

.

**See**:

- reduce
- unique_copy
- unique_by_key
- unique_by_key_copy

### Function `reduce_by_key`

` template <typename InputIterator1, typename InputIterator2, typename OutputIterator1, typename OutputIterator2, typename BinaryPredicate> thrust::pair< OutputIterator1, OutputIterator2 > `

**reduce_by_key**(InputIterator1 keys_first, InputIterator1 keys_last, InputIterator2 values_first, OutputIterator1 keys_output, OutputIterator2 values_output, BinaryPredicate binary_pred);`reduce_by_key`

is a generalization of `reduce`

to key-value pairs. For each group of consecutive keys in the range `[keys_first, keys_last)`

that are equal, `reduce_by_key`

copies the first element of the group to the `keys_output`

. The corresponding values in the range are reduced using the `plus`

and the result copied to `values_output`

.

This version of `reduce_by_key`

uses the function object `binary_pred`

to test for equality and `plus`

to reduce values with equal keys.

The following code snippet demonstrates how to use `reduce_by_key`

to compact a sequence of key/value pairs and sum values with equal keys.

```
#include <thrust/reduce.h>
...
const int N = 7;
int A[N] = {1, 3, 3, 3, 2, 2, 1}; // input keys
int B[N] = {9, 8, 7, 6, 5, 4, 3}; // input values
int C[N]; // output keys
int D[N]; // output values
thrust::pair<int*,int*> new_end;
thrust::equal_to<int> binary_pred;
new_end = thrust::reduce_by_key(A, A + N, B, C, D, binary_pred);
// The first four keys in C are now {1, 3, 2, 1} and new_end.first - C is 4.
// The first four values in D are now {9, 21, 9, 3} and new_end.second - D is 4.
```

**Template Parameters**:

is a model of Input Iterator,`InputIterator1`

is a model of Input Iterator,`InputIterator2`

is a model of Output Iterator and and`OutputIterator1`

`InputIterator1's`

`value_type`

is convertible to`OutputIterator1's`

`value_type`

.is a model of Output Iterator and and`OutputIterator2`

`InputIterator2's`

`value_type`

is convertible to`OutputIterator2's`

`value_type`

.is a model of Binary Predicate.`BinaryPredicate`

**Function Parameters**:

The beginning of the input key range.`keys_first`

The end of the input key range.`keys_last`

The beginning of the input value range.`values_first`

The beginning of the output key range.`keys_output`

The beginning of the output value range.`values_output`

The binary predicate used to determine equality.`binary_pred`

**Preconditions**: The input ranges shall not overlap either output range.

**Returns**: A pair of iterators at end of the ranges `[keys_output, keys_output_last)`

and `[values_output, values_output_last)`

.

**See**:

- reduce
- unique_copy
- unique_by_key
- unique_by_key_copy

### Function `reduce_by_key`

` template <typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator1, typename OutputIterator2, typename BinaryPredicate, typename BinaryFunction> _CCCL_HOST_DEVICE thrust::pair< OutputIterator1, OutputIterator2 > `

**reduce_by_key**(const thrust::detail::execution_policy_base< DerivedPolicy > & exec, InputIterator1 keys_first, InputIterator1 keys_last, InputIterator2 values_first, OutputIterator1 keys_output, OutputIterator2 values_output, BinaryPredicate binary_pred, BinaryFunction binary_op);`reduce_by_key`

is a generalization of `reduce`

to key-value pairs. For each group of consecutive keys in the range `[keys_first, keys_last)`

that are equal, `reduce_by_key`

copies the first element of the group to the `keys_output`

. The corresponding values in the range are reduced using the `BinaryFunction`

`binary_op`

and the result copied to `values_output`

. Specifically, if consecutive key iterators `i`

and `(i + 1) are such that `

`binary_pred(*i, *(i+1))`

is `true`

, then the corresponding values are reduced to a single value with `binary_op`

.

This version of `reduce_by_key`

uses the function object `binary_pred`

to test for equality and `binary_op`

to reduce values with equal keys.

The algorithm’s execution is parallelized as determined by `exec`

.

The following code snippet demonstrates how to use `reduce_by_key`

to compact a sequence of key/value pairs and sum values with equal keys using the `thrust::host`

execution policy for parallelization:

```
#include <thrust/reduce.h>
#include <thrust/execution_policy.h>
...
const int N = 7;
int A[N] = {1, 3, 3, 3, 2, 2, 1}; // input keys
int B[N] = {9, 8, 7, 6, 5, 4, 3}; // input values
int C[N]; // output keys
int D[N]; // output values
thrust::pair<int*,int*> new_end;
thrust::equal_to<int> binary_pred;
thrust::plus<int> binary_op;
new_end = thrust::reduce_by_key(thrust::host, A, A + N, B, C, D, binary_pred, binary_op);
// The first four keys in C are now {1, 3, 2, 1} and new_end.first - C is 4.
// The first four values in D are now {9, 21, 9, 3} and new_end.second - D is 4.
```

**Template Parameters**:

The name of the derived execution policy.`DerivedPolicy`

is a model of Input Iterator,`InputIterator1`

is a model of Input Iterator,`InputIterator2`

is a model of Output Iterator and and`OutputIterator1`

`InputIterator1's`

`value_type`

is convertible to`OutputIterator1's`

`value_type`

.is a model of Output Iterator and and`OutputIterator2`

`InputIterator2's`

`value_type`

is convertible to`OutputIterator2's`

`value_type`

.is a model of Binary Predicate.`BinaryPredicate`

is a model of Binary Function and`BinaryFunction`

`BinaryFunction's`

`result_type`

is convertible to`OutputIterator2's`

`value_type`

.

**Function Parameters**:

The execution policy to use for parallelization.`exec`

The beginning of the input key range.`keys_first`

The end of the input key range.`keys_last`

The beginning of the input value range.`values_first`

The beginning of the output key range.`keys_output`

The beginning of the output value range.`values_output`

The binary predicate used to determine equality.`binary_pred`

The binary function used to accumulate values.`binary_op`

**Preconditions**: The input ranges shall not overlap either output range.

**Returns**: A pair of iterators at end of the ranges `[keys_output, keys_output_last)`

and `[values_output, values_output_last)`

.

**See**:

- reduce
- unique_copy
- unique_by_key
- unique_by_key_copy

### Function `reduce_by_key`

` template <typename InputIterator1, typename InputIterator2, typename OutputIterator1, typename OutputIterator2, typename BinaryPredicate, typename BinaryFunction> thrust::pair< OutputIterator1, OutputIterator2 > `

**reduce_by_key**(InputIterator1 keys_first, InputIterator1 keys_last, InputIterator2 values_first, OutputIterator1 keys_output, OutputIterator2 values_output, BinaryPredicate binary_pred, BinaryFunction binary_op);`reduce_by_key`

is a generalization of `reduce`

to key-value pairs. For each group of consecutive keys in the range `[keys_first, keys_last)`

that are equal, `reduce_by_key`

copies the first element of the group to the `keys_output`

. The corresponding values in the range are reduced using the `BinaryFunction`

`binary_op`

and the result copied to `values_output`

. Specifically, if consecutive key iterators `i`

and `(i + 1) are such that `

`binary_pred(*i, *(i+1))`

is `true`

, then the corresponding values are reduced to a single value with `binary_op`

.

This version of `reduce_by_key`

uses the function object `binary_pred`

to test for equality and `binary_op`

to reduce values with equal keys.

The following code snippet demonstrates how to use `reduce_by_key`

to compact a sequence of key/value pairs and sum values with equal keys.

```
#include <thrust/reduce.h>
...
const int N = 7;
int A[N] = {1, 3, 3, 3, 2, 2, 1}; // input keys
int B[N] = {9, 8, 7, 6, 5, 4, 3}; // input values
int C[N]; // output keys
int D[N]; // output values
thrust::pair<int*,int*> new_end;
thrust::equal_to<int> binary_pred;
thrust::plus<int> binary_op;
new_end = thrust::reduce_by_key(A, A + N, B, C, D, binary_pred, binary_op);
// The first four keys in C are now {1, 3, 2, 1} and new_end.first - C is 4.
// The first four values in D are now {9, 21, 9, 3} and new_end.second - D is 4.
```

**Template Parameters**:

is a model of Input Iterator,`InputIterator1`

is a model of Input Iterator,`InputIterator2`

is a model of Output Iterator and and`OutputIterator1`

`InputIterator1's`

`value_type`

is convertible to`OutputIterator1's`

`value_type`

.is a model of Output Iterator and and`OutputIterator2`

`InputIterator2's`

`value_type`

is convertible to`OutputIterator2's`

`value_type`

.is a model of Binary Predicate.`BinaryPredicate`

is a model of Binary Function and`BinaryFunction`

`BinaryFunction's`

`result_type`

is convertible to`OutputIterator2's`

`value_type`

.

**Function Parameters**:

The beginning of the input key range.`keys_first`

The end of the input key range.`keys_last`

The beginning of the input value range.`values_first`

The beginning of the output key range.`keys_output`

The beginning of the output value range.`values_output`

The binary predicate used to determine equality.`binary_pred`

The binary function used to accumulate values.`binary_op`

**Preconditions**: The input ranges shall not overlap either output range.

**Returns**: A pair of iterators at end of the ranges `[keys_output, keys_output_last)`

and `[values_output, values_output_last)`

.

**See**:

- reduce
- unique_copy
- unique_by_key
- unique_by_key_copy