Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

This is the documentation for an old version of Boost. Click here to view this page for the latest version.
PrevUpHomeNext

Function template reduce_by_key

boost::compute::reduce_by_key

Synopsis

// In header: <boost/compute/algorithm/reduce_by_key.hpp>


template<typename InputKeyIterator, typename InputValueIterator, 
         typename OutputKeyIterator, typename OutputValueIterator, 
         typename BinaryFunction, typename BinaryPredicate> 
  std::pair< OutputKeyIterator, OutputValueIterator > 
  reduce_by_key(InputKeyIterator keys_first, InputKeyIterator keys_last, 
                InputValueIterator values_first, 
                OutputKeyIterator keys_result, 
                OutputValueIterator values_result, BinaryFunction function, 
                BinaryPredicate predicate, 
                command_queue & queue = system::default_queue());

Description

The reduce_by_key() algorithm performs reduction for each contiguous subsequence of values determinate by equivalent keys.

Returns a pair of iterators at the end of the ranges [keys_result, keys_result_last) and [values_result, values_result_last).

If no function is specified, plus will be used. If no predicate is specified, equal_to will be used.

The reduce_by_key() algorithm assumes that the binary reduction function is associative. When used with non-associative functions the result may be non-deterministic and vary in precision. Notably this affects the plus<float>() function as floating-point addition is not associative and may produce slightly different results than a serial algorithm.

For example, to calculate the sum of the values for each key:


Space complexity on GPUs: \Omega(2n)
Space complexity on CPUs: \Omega(1)

See Also:

reduce()

Parameters:

function

binary reduction function

keys_first

the first key

keys_last

the last key

keys_result

iterator pointing to the key output

predicate

binary predicate which returns true only if two keys are equal

queue

command queue to perform the operation

values_first

the first input value

values_result

iterator pointing to the reduced value output


PrevUpHomeNext