thrust::reduce_by_key

Defined in thrust/reduce.h

template<typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator1, typename OutputIterator2, typename BinaryPredicate, typename BinaryFunction>
thrust::pair<OutputIterator1, OutputIterator2> thrust::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.

See also

reduce

See also

unique_copy

See also

unique_by_key

See also

unique_by_key_copy

Parameters
  • exec – The execution policy to use for parallelization.

  • keys_first – The beginning of the input key range.

  • keys_last – The end of the input key range.

  • values_first – The beginning of the input value range.

  • keys_output – The beginning of the output key range.

  • values_output – The beginning of the output value range.

  • binary_pred – The binary predicate used to determine equality.

  • binary_op – The binary function used to accumulate values.

Template Parameters
  • DerivedPolicy – The name of the derived execution policy.

  • InputIterator1 – is a model of Input Iterator,

  • InputIterator2 – is a model of Input Iterator,

  • OutputIterator1 – is a model of Output Iterator and and InputIterator1's value_type is convertible to OutputIterator1's value_type.

  • OutputIterator2 – is a model of Output Iterator and and InputIterator2's value_type is convertible to OutputIterator2's value_type.

  • BinaryPredicate – is a model of Binary Predicate.

  • BinaryFunction – is a model of Binary Function and BinaryFunction's result_type is convertible to OutputIterator2's value_type.

Returns

A pair of iterators at end of the ranges [keys_output, keys_output_last) and [values_output, values_output_last).

Pre

The input ranges shall not overlap either output range.