API Reference Guide

Contents

API Reference Guide#

This chapter describes the rocThrust C++ API.

Algorithms#

group algorithms

Copying#

group copying

Functions

template<typename DerivedPolicy, typename InputIterator, typename OutputIterator>
__host__ __device__ OutputIterator copy(const thrust::detail::execution_policy_base<DerivedPolicy> &exec, InputIterator first, InputIterator last, OutputIterator result)#

copy copies elements from the range [first, last) to the range [result, result + (last - first)). That is, it performs the assignments *result = *first, *(result + 1) = *(first + 1), and so on. Generally, for every integer n from 0 to last - first, copy performs the assignment *(result + n) = *(first + n). Unlike std::copy, copy offers no guarantee on order of operation. As a result, calling copy with overlapping source and destination ranges has undefined behavior.

The return value is result + (last - first).

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

The following code snippet demonstrates how to use copy to copy from one range to another using the thrust::device parallelization policy:

#include <thrust/copy.h>
#include <thrust/device_vector.h>
#include <thrust/execution_policy.h>
...

thrust::device_vector<int> vec0(100);
thrust::device_vector<int> vec1(100);
...

thrust::copy(thrust::device, vec0.begin(), vec0.end(), vec1.begin());

// vec1 is now a copy of vec0
Parameters:
  • exec – The execution policy to use for parallelization.

  • first – The beginning of the sequence to copy.

  • last – The end of the sequence to copy.

  • result – The destination sequence.

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

  • InputIterator – must be a model of Input Iterator and InputIterator's value_type must be convertible to OutputIterator's value_type.

  • OutputIterator – must be a model of Output Iterator.

Returns:

The end of the destination sequence.

Pre:

result may be equal to first, but result shall not be in the range [first, last) otherwise.

template<typename DerivedPolicy, typename InputIterator, typename Size, typename OutputIterator>
__host__ __device__ OutputIterator copy_n(const thrust::detail::execution_policy_base<DerivedPolicy> &exec, InputIterator first, Size n, OutputIterator result)#

copy_n copies elements from the range [first, first + n) to the range [result, result + n). That is, it performs the assignments *result = *first, *(result + 1) = *(first + 1), and so on. Generally, for every integer i from 0 to n, copy performs the assignment *(result + i) = *(first + i). Unlike std::copy_n, copy_n offers no guarantee on order of operation. As a result, calling copy_n with overlapping source and destination ranges has undefined behavior.

The return value is result + n.

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

The following code snippet demonstrates how to use copy to copy from one range to another using the thrust::device parallelization policy:

#include <thrust/copy.h>
#include <thrust/device_vector.h>
#include <thrust/execution_policy.h>
...
size_t n = 100;
thrust::device_vector<int> vec0(n);
thrust::device_vector<int> vec1(n);
...
thrust::copy_n(thrust::device, vec0.begin(), n, vec1.begin());

// vec1 is now a copy of vec0

See also

thrust::copy

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

  • first – The beginning of the range to copy.

  • n – The number of elements to copy.

  • result – The beginning destination range.

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

  • InputIterator – must be a model of Input Iterator and InputIterator's value_type must be convertible to OutputIterator's value_type.

  • Size – is an integral type.

  • OutputIterator – must be a model of Output Iterator.

Returns:

The end of the destination range.

Pre:

result may be equal to first, but result shall not be in the range [first, first + n) otherwise.

template<typename InputIterator, typename OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result)#

copy copies elements from the range [first, last) to the range [result, result + (last - first)). That is, it performs the assignments *result = *first, *(result + 1) = *(first + 1), and so on. Generally, for every integer n from 0 to last - first, copy performs the assignment *(result + n) = *(first + n). Unlike std::copy, copy offers no guarantee on order of operation. As a result, calling copy with overlapping source and destination ranges has undefined behavior.

The return value is result + (last - first).

The following code snippet demonstrates how to use copy to copy from one range to another.

#include <thrust/copy.h>
#include <thrust/device_vector.h>
...

thrust::device_vector<int> vec0(100);
thrust::device_vector<int> vec1(100);
...

thrust::copy(vec0.begin(), vec0.end(),
             vec1.begin());

// vec1 is now a copy of vec0
Parameters:
  • first – The beginning of the sequence to copy.

  • last – The end of the sequence to copy.

  • result – The destination sequence.

Template Parameters:
  • InputIterator – must be a model of Input Iterator and InputIterator's value_type must be convertible to OutputIterator's value_type.

  • OutputIterator – must be a model of Output Iterator.

Returns:

The end of the destination sequence.

Pre:

result may be equal to first, but result shall not be in the range [first, last) otherwise.

template<typename InputIterator, typename Size, typename OutputIterator>
OutputIterator copy_n(InputIterator first, Size n, OutputIterator result)#

copy_n copies elements from the range [first, first + n) to the range [result, result + n). That is, it performs the assignments *result = *first, *(result + 1) = *(first + 1), and so on. Generally, for every integer i from 0 to n, copy performs the assignment *(result + i) = *(first + i). Unlike std::copy_n, copy_n offers no guarantee on order of operation. As a result, calling copy_n with overlapping source and destination ranges has undefined behavior.

The return value is result + n.

The following code snippet demonstrates how to use copy to copy from one range to another.

#include <thrust/copy.h>
#include <thrust/device_vector.h>
...
size_t n = 100;
thrust::device_vector<int> vec0(n);
thrust::device_vector<int> vec1(n);
...
thrust::copy_n(vec0.begin(), n, vec1.begin());

// vec1 is now a copy of vec0

See also

thrust::copy

Parameters:
  • first – The beginning of the range to copy.

  • n – The number of elements to copy.

  • result – The beginning destination range.

Template Parameters:
  • InputIterator – must be a model of Input Iterator and InputIterator's value_type must be convertible to OutputIterator's value_type.

  • Size – is an integral type.

  • OutputIterator – must be a model of Output Iterator.

Returns:

The end of the destination range.

Pre:

result may be equal to first, but result shall not be in the range [first, first + n) otherwise.

template<typename DerivedPolicy, typename ForwardIterator1, typename ForwardIterator2>
__host__ __device__ ForwardIterator2 swap_ranges(const thrust::detail::execution_policy_base<DerivedPolicy> &exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2)#

swap_ranges swaps each of the elements in the range [first1, last1) with the corresponding element in the range [first2, first2 + (last1 - first1)). That is, for each integer n such that 0 <= n < (last1 - first1), it swaps *(first1 + n) and *(first2 + n). The return value is first2 + (last1 - first1).

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

The following code snippet demonstrates how to use swap_ranges to swap the contents of two thrust::device_vectors using the thrust::device execution policy for parallelization:

#include <thrust/swap.h>
#include <thrust/device_vector.h>
#include <thrust/execution_policy.h>
...
thrust::device_vector<int> v1(2), v2(2);
v1[0] = 1;
v1[1] = 2;
v2[0] = 3;
v2[1] = 4;

thrust::swap_ranges(thrust::device, v1.begin(), v1.end(), v2.begin());

// v1[0] == 3, v1[1] == 4, v2[0] == 1, v2[1] == 2

See also

swap

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

  • first1 – The beginning of the first sequence to swap.

  • last1 – One position past the last element of the first sequence to swap.

  • first2 – The beginning of the second sequence to swap.

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

  • ForwardIterator1 – is a model of Forward Iterator, and ForwardIterator1's value_type must be convertible to ForwardIterator2's value_type.

  • ForwardIterator2 – is a model of Forward Iterator, and ForwardIterator2's value_type must be convertible to ForwardIterator1's value_type.

Returns:

An iterator pointing to one position past the last element of the second sequence to swap.

Pre:

first1 may equal first2, but the range [first1, last1) shall not overlap the range [first2, first2 + (last1 - first1)) otherwise.

template<typename ForwardIterator1, typename ForwardIterator2>
ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2)#

swap_ranges swaps each of the elements in the range [first1, last1) with the corresponding element in the range [first2, first2 + (last1 - first1)). That is, for each integer n such that 0 <= n < (last1 - first1), it swaps *(first1 + n) and *(first2 + n). The return value is first2 + (last1 - first1).

The following code snippet demonstrates how to use swap_ranges to swap the contents of two thrust::device_vectors.

#include <thrust/swap.h>
#include <thrust/device_vector.h>
...
thrust::device_vector<int> v1(2), v2(2);
v1[0] = 1;
v1[1] = 2;
v2[0] = 3;
v2[1] = 4;

thrust::swap_ranges(v1.begin(), v1.end(), v2.begin());

// v1[0] == 3, v1[1] == 4, v2[0] == 1, v2[1] == 2

See also

swap

Parameters:
  • first1 – The beginning of the first sequence to swap.

  • last1 – One position past the last element of the first sequence to swap.

  • first2 – The beginning of the second sequence to swap.

Template Parameters:
  • ForwardIterator1 – is a model of Forward Iterator, and ForwardIterator1's value_type must be convertible to ForwardIterator2's value_type.

  • ForwardIterator2 – is a model of Forward Iterator, and ForwardIterator2's value_type must be convertible to ForwardIterator1's value_type.

Returns:

An iterator pointing to one position past the last element of the second sequence to swap.

Pre:

first1 may equal first2, but the range [first1, last1) shall not overlap the range [first2, first2 + (last1 - first1)) otherwise.

template<typename DerivedPolicy, typename InputIterator, typename ForwardIterator>
__host__ __device__ ForwardIterator uninitialized_copy(const thrust::detail::execution_policy_base<DerivedPolicy> &exec, InputIterator first, InputIterator last, ForwardIterator result)#

In thrust, the function thrust::device_new allocates memory for an object and then creates an object at that location by calling a constructor. Occasionally, however, it is useful to separate those two operations. If each iterator in the range [result, result + (last - first)) points to uninitialized memory, then uninitialized_copy creates a copy of [first, last) in that range. That is, for each iterator i in the input, uninitialized_copy creates a copy of *i in the location pointed to by the corresponding iterator in the output range by ForwardIterator's value_type's copy constructor with *i as its argument.

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

The following code snippet demonstrates how to use uninitialized_copy to initialize a range of uninitialized memory using the thrust::device execution policy for parallelization:

#include <thrust/uninitialized_copy.h>
#include <thrust/device_malloc.h>
#include <thrust/device_vector.h>
#include <thrust/execution_policy.h>

struct Int
{
  __host__ __device__
  Int(int x) : val(x) {}
  int val;
};  
...
const int N = 137;

Int val(46);
thrust::device_vector<Int> input(N, val);
thrust::device_ptr<Int> array = thrust::device_malloc<Int>(N);
thrust::uninitialized_copy(thrust::device, input.begin(), input.end(), array);

// Int x = array[i];
// x.val == 46 for all 0 <= i < N

See also

copy

See also

device_new

See also

device_malloc

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

  • first – The first element of the input range to copy from.

  • last – The last element of the input range to copy from.

  • result – The first element of the output range to copy to.

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

  • InputIterator – is a model of Input Iterator.

  • ForwardIterator – is a model of Forward Iterator, ForwardIterator is mutable, and ForwardIterator's value_type has a constructor that takes a single argument whose type is InputIterator's value_type.

Returns:

An iterator pointing to the last element of the output range.

Pre:

first may equal result, but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

template<typename InputIterator, typename ForwardIterator>
ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result)#

In thrust, the function thrust::device_new allocates memory for an object and then creates an object at that location by calling a constructor. Occasionally, however, it is useful to separate those two operations. If each iterator in the range [result, result + (last - first)) points to uninitialized memory, then uninitialized_copy creates a copy of [first, last) in that range. That is, for each iterator i in the input, uninitialized_copy creates a copy of *i in the location pointed to by the corresponding iterator in the output range by ForwardIterator's value_type's copy constructor with *i as its argument.

The following code snippet demonstrates how to use uninitialized_copy to initialize a range of uninitialized memory.

#include <thrust/uninitialized_copy.h>
#include <thrust/device_malloc.h>
#include <thrust/device_vector.h>

struct Int
{
  __host__ __device__
  Int(int x) : val(x) {}
  int val;
};  
...
const int N = 137;

Int val(46);
thrust::device_vector<Int> input(N, val);
thrust::device_ptr<Int> array = thrust::device_malloc<Int>(N);
thrust::uninitialized_copy(input.begin(), input.end(), array);

// Int x = array[i];
// x.val == 46 for all 0 <= i < N

See also

copy

See also

device_new

See also

device_malloc

Parameters:
  • first – The first element of the input range to copy from.

  • last – The last element of the input range to copy from.

  • result – The first element of the output range to copy to.

Template Parameters:
  • InputIterator – is a model of Input Iterator.

  • ForwardIterator – is a model of Forward Iterator, ForwardIterator is mutable, and ForwardIterator's value_type has a constructor that takes a single argument whose type is InputIterator's value_type.

Returns:

An iterator pointing to the last element of the output range.

Pre:

first may equal result, but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

template<typename DerivedPolicy, typename InputIterator, typename Size, typename ForwardIterator>
__host__ __device__ ForwardIterator uninitialized_copy_n(const thrust::detail::execution_policy_base<DerivedPolicy> &exec, InputIterator first, Size n, ForwardIterator result)#

In thrust, the function thrust::device_new allocates memory for an object and then creates an object at that location by calling a constructor. Occasionally, however, it is useful to separate those two operations. If each iterator in the range [result, result + n) points to uninitialized memory, then uninitialized_copy_n creates a copy of [first, first + n) in that range. That is, for each iterator i in the input, uninitialized_copy_n creates a copy of *i in the location pointed to by the corresponding iterator in the output range by InputIterator's value_type's copy constructor with *i as its argument.

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

The following code snippet demonstrates how to use uninitialized_copy to initialize a range of uninitialized memory using the thrust::device execution policy for parallelization:

#include <thrust/uninitialized_copy.h>
#include <thrust/device_malloc.h>
#include <thrust/device_vector.h>
#include <thrust/execution_policy.h>

struct Int
{
  __host__ __device__
  Int(int x) : val(x) {}
  int val;
};  
...
const int N = 137;

Int val(46);
thrust::device_vector<Int> input(N, val);
thrust::device_ptr<Int> array = thrust::device_malloc<Int>(N);
thrust::uninitialized_copy_n(thrust::device, input.begin(), N, array);

// Int x = array[i];
// x.val == 46 for all 0 <= i < N

See also

copy

See also

device_new

See also

device_malloc

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

  • first – The first element of the input range to copy from.

  • n – The number of elements to copy.

  • result – The first element of the output range to copy to.

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

  • InputIterator – is a model of Input Iterator.

  • Size – is an integral type.

  • ForwardIterator – is a model of Forward Iterator, ForwardIterator is mutable, and ForwardIterator's value_type has a constructor that takes a single argument whose type is InputIterator's value_type.

Returns:

An iterator pointing to the last element of the output range.

Pre:

first may equal result, but the range [first, first + n) and the range [result, result + n) shall not overlap otherwise.

template<typename InputIterator, typename Size, typename ForwardIterator>
ForwardIterator uninitialized_copy_n(InputIterator first, Size n, ForwardIterator result)#

In thrust, the function thrust::device_new allocates memory for an object and then creates an object at that location by calling a constructor. Occasionally, however, it is useful to separate those two operations. If each iterator in the range [result, result + n) points to uninitialized memory, then uninitialized_copy_n creates a copy of [first, first + n) in that range. That is, for each iterator i in the input, uninitialized_copy_n creates a copy of *i in the location pointed to by the corresponding iterator in the output range by InputIterator's value_type's copy constructor with *i as its argument.

The following code snippet demonstrates how to use uninitialized_copy to initialize a range of uninitialized memory.

#include <thrust/uninitialized_copy.h>
#include <thrust/device_malloc.h>
#include <thrust/device_vector.h>

struct Int
{
  __host__ __device__
  Int(int x) : val(x) {}
  int val;
};  
...
const int N = 137;

Int val(46);
thrust::device_vector<Int> input(N, val);
thrust::device_ptr<Int> array = thrust::device_malloc<Int>(N);
thrust::uninitialized_copy_n(input.begin(), N, array);

// Int x = array[i];
// x.val == 46 for all 0 <= i < N

See also

copy

See also

device_new

See also

device_malloc

Parameters:
  • first – The first element of the input range to copy from.

  • n – The number of elements to copy.

  • result – The first element of the output range to copy to.

Template Parameters:
  • InputIterator – is a model of Input Iterator.

  • Size – is an integral type.

  • ForwardIterator – is a model of Forward Iterator, ForwardIterator is mutable, and ForwardIterator's value_type has a constructor that takes a single argument whose type is InputIterator's value_type.

Returns:

An iterator pointing to the last element of the output range.

Pre:

first may equal result, but the range [first, first + n) and the range [result, result + n) shall not overlap otherwise.

Functions

template<typename DerivedPolicy, typename InputIterator, typename RandomAccessIterator, typename OutputIterator>
__host__ __device__ OutputIterator gather(const thrust::detail::execution_policy_base<DerivedPolicy> &exec, InputIterator map_first, InputIterator map_last, RandomAccessIterator input_first, OutputIterator result)#

gather copies elements from a source array into a destination range according to a map. For each input iterator i in the range [map_first, map_last), the value input_first[*i] is assigned to *(result + (i - map_first)). RandomAccessIterator must permit random access.

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

The following code snippet demonstrates how to use gather to reorder a range using the thrust::device execution policy for parallelization:

Remark

gather is the inverse of thrust::scatter.

#include <thrust/gather.h>
#include <thrust/device_vector.h>
#include <thrust/execution_policy.h>
...
// mark even indices with a 1; odd indices with a 0
int values[10] = {1, 0, 1, 0, 1, 0, 1, 0, 1, 0};
thrust::device_vector<int> d_values(values, values + 10);

// gather all even indices into the first half of the range
// and odd indices to the last half of the range
int map[10]   = {0, 2, 4, 6, 8, 1, 3, 5, 7, 9};
thrust::device_vector<int> d_map(map, map + 10);

thrust::device_vector<int> d_output(10);
thrust::gather(thrust::device,
               d_map.begin(), d_map.end(),
               d_values.begin(),
               d_output.begin());
// d_output is now {1, 1, 1, 1, 1, 0, 0, 0, 0, 0}
Parameters:
  • exec – The execution policy to use for parallelization.

  • map_first – Beginning of the range of gather locations.

  • map_last – End of the range of gather locations.

  • input_first – Beginning of the source range.

  • result – Beginning of the destination range.

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

  • InputIterator – must be a model of Input Iterator and InputIterator's value_type must be convertible to RandomAccessIterator's difference_type.

  • RandomAccessIterator – must be a model of Random Access Iterator and RandomAccessIterator's value_type must be convertible to OutputIterator's value_type.

  • OutputIterator – must be a model of Output Iterator.

Pre:

The range [map_first, map_last) shall not overlap the range [result, result + (map_last - map_first)).

Pre:

The input data shall not overlap the range [result, result + (map_last - map_first)).

template<typename InputIterator, typename RandomAccessIterator, typename OutputIterator>
OutputIterator gather(InputIterator map_first, InputIterator map_last, RandomAccessIterator input_first, OutputIterator result)#

gather copies elements from a source array into a destination range according to a map. For each input iterator i in the range [map_first, map_last), the value input_first[*i] is assigned to *(result + (i - map_first)). RandomAccessIterator must permit random access.

The following code snippet demonstrates how to use gather to reorder a range.

Remark

gather is the inverse of thrust::scatter.

#include <thrust/gather.h>
#include <thrust/device_vector.h>
...
// mark even indices with a 1; odd indices with a 0
int values[10] = {1, 0, 1, 0, 1, 0, 1, 0, 1, 0};
thrust::device_vector<int> d_values(values, values + 10);

// gather all even indices into the first half of the range
// and odd indices to the last half of the range
int map[10]   = {0, 2, 4, 6, 8, 1, 3, 5, 7, 9};
thrust::device_vector<int> d_map(map, map + 10);

thrust::device_vector<int> d_output(10);
thrust::gather(d_map.begin(), d_map.end(),
               d_values.begin(),
               d_output.begin());
// d_output is now {1, 1, 1, 1, 1, 0, 0, 0, 0, 0}
Parameters:
  • map_first – Beginning of the range of gather locations.

  • map_last – End of the range of gather locations.

  • input_first – Beginning of the source range.

  • result – Beginning of the destination range.

Template Parameters:
  • InputIterator – must be a model of Input Iterator and InputIterator's value_type must be convertible to RandomAccessIterator's difference_type.

  • RandomAccessIterator – must be a model of Random Access Iterator and RandomAccessIterator's value_type must be convertible to OutputIterator's value_type.

  • OutputIterator – must be a model of Output Iterator.

Pre:

The range [map_first, map_last) shall not overlap the range [result, result + (map_last - map_first)).

Pre:

The input data shall not overlap the range [result, result + (map_last - map_first)).

template<typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename RandomAccessIterator, typename OutputIterator>
__host__ __device__ OutputIterator gather_if(const thrust::detail::execution_policy_base<DerivedPolicy> &exec, InputIterator1 map_first, InputIterator1 map_last, InputIterator2 stencil, RandomAccessIterator input_first, OutputIterator result)#

gather_if conditionally copies elements from a source array into a destination range according to a map. For each input iterator i in the range [map_first, map_last), such that the value of *(stencil + (i - map_first)) is true, the value input_first[*i] is assigned to *(result + (i - map_first)). RandomAccessIterator must permit random access.

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

The following code snippet demonstrates how to use gather_if to gather selected values from an input range using the thrust::device execution policy:

Remark

gather_if is the inverse of scatter_if.

#include <thrust/gather.h>
#include <thrust/device_vector.h>
#include <thrust/execution_policy.h>
...

int values[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
thrust::device_vector<int> d_values(values, values + 10);

// select elements at even-indexed locations
int stencil[10] = {1, 0, 1, 0, 1, 0, 1, 0, 1, 0};
thrust::device_vector<int> d_stencil(stencil, stencil + 10);

// map all even indices into the first half of the range
// and odd indices to the last half of the range
int map[10]   = {0, 2, 4, 6, 8, 1, 3, 5, 7, 9};
thrust::device_vector<int> d_map(map, map + 10);

thrust::device_vector<int> d_output(10, 7);
thrust::gather_if(thrust::device,
                  d_map.begin(), d_map.end(),
                  d_stencil.begin(),
                  d_values.begin(),
                  d_output.begin());
// d_output is now {0, 7, 4, 7, 8, 7, 3, 7, 7, 7}
Parameters:
  • exec – The execution policy to use for parallelization.

  • map_first – Beginning of the range of gather locations.

  • map_last – End of the range of gather locations.

  • stencil – Beginning of the range of predicate values.

  • input_first – Beginning of the source range.

  • result – Beginning of the destination range.

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

  • InputIterator1 – must be a model of Input Iterator and InputIterator1's value_type must be convertible to RandomAccessIterator's difference_type.

  • InputIterator2 – must be a model of Input Iterator and InputIterator2's value_type must be convertible to bool.

  • RandomAccessIterator – must be a model of Random Access iterator and RandomAccessIterator's value_type must be convertible to OutputIterator's value_type.

  • OutputIterator – must be a model of Output Iterator.

Pre:

The range [map_first, map_last) shall not overlap the range [result, result + (map_last - map_first)).

Pre:

The range [stencil, stencil + (map_last - map_first)) shall not overlap the range [result, result + (map_last - map_first)).

Pre:

The input data shall not overlap the range [result, result + (map_last - map_first)).

template<typename InputIterator1, typename InputIterator2, typename RandomAccessIterator, typename OutputIterator>
OutputIterator gather_if(InputIterator1 map_first, InputIterator1 map_last, InputIterator2 stencil, RandomAccessIterator input_first, OutputIterator result)#

gather_if conditionally copies elements from a source array into a destination range according to a map. For each input iterator i in the range [map_first, map_last), such that the value of *(stencil + (i - map_first)) is true, the value input_first[*i] is assigned to *(result + (i - map_first)). RandomAccessIterator must permit random access.

The following code snippet demonstrates how to use gather_if to gather selected values from an input range.

Remark

gather_if is the inverse of scatter_if.

#include <thrust/gather.h>
#include <thrust/device_vector.h>
...

int values[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
thrust::device_vector<int> d_values(values, values + 10);

// select elements at even-indexed locations
int stencil[10] = {1, 0, 1, 0, 1, 0, 1, 0, 1, 0};
thrust::device_vector<int> d_stencil(stencil, stencil + 10);

// map all even indices into the first half of the range
// and odd indices to the last half of the range
int map[10]   = {0, 2, 4, 6, 8, 1, 3, 5, 7, 9};
thrust::device_vector<int> d_map(map, map + 10);

thrust::device_vector<int> d_output(10, 7);
thrust::gather_if(d_map.begin(), d_map.end(),
                  d_stencil.begin(),
                  d_values.begin(),
                  d_output.begin());
// d_output is now {0, 7, 4, 7, 8, 7, 3, 7, 7, 7}
Parameters:
  • map_first – Beginning of the range of gather locations.

  • map_last – End of the range of gather locations.

  • stencil – Beginning of the range of predicate values.

  • input_first – Beginning of the source range.

  • result – Beginning of the destination range.

Template Parameters:
  • InputIterator1 – must be a model of Input Iterator and InputIterator1's value_type must be convertible to RandomAccessIterator's difference_type.

  • InputIterator2 – must be a model of Input Iterator and InputIterator2's value_type must be convertible to bool.

  • RandomAccessIterator – must be a model of Random Access iterator and RandomAccessIterator's value_type must be convertible to OutputIterator's value_type.

  • OutputIterator – must be a model of Output Iterator.

Pre:

The range [map_first, map_last) shall not overlap the range [result, result + (map_last - map_first)).

Pre:

The range [stencil, stencil + (map_last - map_first)) shall not overlap the range [result, result + (map_last - map_first)).

Pre:

The input data shall not overlap the range [result, result + (map_last - map_first)).

template<typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename RandomAccessIterator, typename OutputIterator, typename Predicate>
__host__ __device__ OutputIterator gather_if(const thrust::detail::execution_policy_base<DerivedPolicy> &exec, InputIterator1 map_first, InputIterator1 map_last, InputIterator2 stencil, RandomAccessIterator input_first, OutputIterator result, Predicate pred)#

gather_if conditionally copies elements from a source array into a destination range according to a map. For each input iterator i in the range [map_first, map_last) such that the value of pred(*(stencil + (i - map_first))) is true, the value input_first[*i] is assigned to *(result + (i - map_first)). RandomAccessIterator must permit random access.

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

The following code snippet demonstrates how to use gather_if to gather selected values from an input range based on an arbitrary selection function using the thrust::device execution policy for parallelization:

Remark

gather_if is the inverse of scatter_if.

#include <thrust/gather.h>
#include <thrust/device_vector.h>
#include <thrust/execution_policy.h>

struct is_even
{
  __host__ __device__
  bool operator()(const int x)
  {
    return (x % 2) == 0;
  }
};
...

int values[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
thrust::device_vector<int> d_values(values, values + 10);

// we will select an element when our stencil is even
int stencil[10] = {0, 3, 4, 1, 4, 1, 2, 7, 8, 9};
thrust::device_vector<int> d_stencil(stencil, stencil + 10);

// map all even indices into the first half of the range
// and odd indices to the last half of the range
int map[10]   = {0, 2, 4, 6, 8, 1, 3, 5, 7, 9};
thrust::device_vector<int> d_map(map, map + 10);

thrust::device_vector<int> d_output(10, 7);
thrust::gather_if(thrust::device,
                  d_map.begin(), d_map.end(),
                  d_stencil.begin(),
                  d_values.begin(),
                  d_output.begin(),
                  is_even());
// d_output is now {0, 7, 4, 7, 8, 7, 3, 7, 7, 7}
Parameters:
  • exec – The execution policy to use for parallelization.

  • map_first – Beginning of the range of gather locations.

  • map_last – End of the range of gather locations.

  • stencil – Beginning of the range of predicate values.

  • input_first – Beginning of the source range.

  • result – Beginning of the destination range.

  • pred – Predicate to apply to the stencil values.

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

  • InputIterator1 – must be a model of Input Iterator and InputIterator1's value_type must be convertible to RandomAccessIterator's difference_type.

  • InputIterator2 – must be a model of Input Iterator and InputIterator2's value_type must be convertible to Predicate's argument_type.

  • RandomAccessIterator – must be a model of Random Access iterator and RandomAccessIterator's value_type must be convertible to OutputIterator's value_type.

  • OutputIterator – must be a model of Output Iterator.

  • Predicate – must be a model of Predicate.

Pre:

The range [map_first, map_last) shall not overlap the range [result, result + (map_last - map_first)).

Pre:

The range [stencil, stencil + (map_last - map_first)) shall not overlap the range [result, result + (map_last - map_first)).

Pre:

The input data shall not overlap the range [result, result + (map_last - map_first)).

template<typename InputIterator1, typename InputIterator2, typename RandomAccessIterator, typename OutputIterator, typename Predicate>
OutputIterator gather_if(InputIterator1 map_first, InputIterator1 map_last, InputIterator2 stencil, RandomAccessIterator input_first, OutputIterator result, Predicate pred)#

gather_if conditionally copies elements from a source array into a destination range according to a map. For each input iterator i in the range [map_first, map_last) such that the value of pred(*(stencil + (i - map_first))) is true, the value input_first[*i] is assigned to *(result + (i - map_first)). RandomAccessIterator must permit random access.

The following code snippet demonstrates how to use gather_if to gather selected values from an input range based on an arbitrary selection function.

Remark

gather_if is the inverse of scatter_if.

#include <thrust/gather.h>
#include <thrust/device_vector.h>

struct is_even
{
  __host__ __device__
  bool operator()(const int x)
  {
    return (x % 2) == 0;
  }
};
...

int values[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
thrust::device_vector<int> d_values(values, values + 10);

// we will select an element when our stencil is even
int stencil[10] = {0, 3, 4, 1, 4, 1, 2, 7, 8, 9};
thrust::device_vector<int> d_stencil(stencil, stencil + 10);

// map all even indices into the first half of the range
// and odd indices to the last half of the range
int map[10]   = {0, 2, 4, 6, 8, 1, 3, 5, 7, 9};
thrust::device_vector<int> d_map(map, map + 10);

thrust::device_vector<int> d_output(10, 7);
thrust::gather_if(d_map.begin(), d_map.end(),
                  d_stencil.begin(),
                  d_values.begin(),
                  d_output.begin(),
                  is_even());
// d_output is now {0, 7, 4, 7, 8, 7, 3, 7, 7, 7}
Parameters:
  • map_first – Beginning of the range of gather locations.

  • map_last – End of the range of gather locations.

  • stencil – Beginning of the range of predicate values.

  • input_first – Beginning of the source range.

  • result – Beginning of the destination range.

  • pred – Predicate to apply to the stencil values.

Template Parameters:
  • InputIterator1 – must be a model of Input Iterator and InputIterator1's value_type must be convertible to RandomAccessIterator's difference_type.

  • InputIterator2 – must be a model of Input Iterator and InputIterator2's value_type must be convertible to Predicate's argument_type.

  • RandomAccessIterator – must be a model of Random Access iterator and RandomAccessIterator's value_type must be convertible to OutputIterator's value_type.

  • OutputIterator – must be a model of Output Iterator.

  • Predicate – must be a model of Predicate.

Pre:

The range [map_first, map_last) shall not overlap the range [result, result + (map_last - map_first)).

Pre:

The range [stencil, stencil + (map_last - map_first)) shall not overlap the range [result, result + (map_last - map_first)).

Pre:

The input data shall not overlap the range [result, result + (map_last - map_first)).

Functions

template<typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename RandomAccessIterator>
__host__ __device__ void scatter(const thrust::detail::execution_policy_base<DerivedPolicy> &exec, InputIterator1 first, InputIterator1 last, InputIterator2 map, RandomAccessIterator result)#

scatter copies elements from a source range into an output array according to a map. For each iterator i in the range [first, last), the value *i is assigned to output[*(map + (i - first))]. The output iterator must permit random access. If the same index appears more than once in the range [map, map + (last - first)), the result is undefined.

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

The following code snippet demonstrates how to use scatter to reorder a range using the thrust::device execution policy for parallelization:

#include <thrust/scatter.h>
#include <thrust/device_vector.h>
#include <thrust/execution_policy.h>
...
// mark even indices with a 1; odd indices with a 0
int values[10] = {1, 0, 1, 0, 1, 0, 1, 0, 1, 0};
thrust::device_vector<int> d_values(values, values + 10);

// scatter all even indices into the first half of the
// range, and odd indices vice versa
int map[10]   = {0, 5, 1, 6, 2, 7, 3, 8, 4, 9};
thrust::device_vector<int> d_map(map, map + 10);

thrust::device_vector<int> d_output(10);
thrust::scatter(thrust::device,
                d_values.begin(), d_values.end(),
                d_map.begin(), d_output.begin());
// d_output is now {1, 1, 1, 1, 1, 0, 0, 0, 0, 0}

Note

scatter is the inverse of thrust::gather.

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

  • first – Beginning of the sequence of values to scatter.

  • last – End of the sequence of values to scatter.

  • map – Beginning of the sequence of output indices.

  • result – Destination of the source elements.

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

  • InputIterator1 – must be a model of Input Iterator and InputIterator1's value_type must be convertible to RandomAccessIterator's value_type.

  • InputIterator2 – must be a model of Input Iterator and InputIterator2's value_type must be convertible to RandomAccessIterator's difference_type.

  • RandomAccessIterator – must be a model of Random Access iterator.

Pre:

The iterator result + i shall not refer to any element referenced by any iterator j in the range [first,last) for all iterators i in the range [map,map + (last - first)).

Pre:

The iterator result + i shall not refer to any element referenced by any iterator j in the range [map,map + (last - first)) for all iterators i in the range [map,map + (last - first)).

Pre:

The expression result[*i] shall be valid for all iterators in the range [map,map + (last - first)).

template<typename InputIterator1, typename InputIterator2, typename RandomAccessIterator>
void scatter(InputIterator1 first, InputIterator1 last, InputIterator2 map, RandomAccessIterator result)#

scatter copies elements from a source range into an output array according to a map. For each iterator i in the range [first, last), the value *i is assigned to output[*(map + (i - first))]. The output iterator must permit random access. If the same index appears more than once in the range [map, map + (last - first)), the result is undefined.

The following code snippet demonstrates how to use scatter to reorder a range.

#include <thrust/scatter.h>
#include <thrust/device_vector.h>
...
// mark even indices with a 1; odd indices with a 0
int values[10] = {1, 0, 1, 0, 1, 0, 1, 0, 1, 0};
thrust::device_vector<int> d_values(values, values + 10);

// scatter all even indices into the first half of the
// range, and odd indices vice versa
int map[10]   = {0, 5, 1, 6, 2, 7, 3, 8, 4, 9};
thrust::device_vector<int> d_map(map, map + 10);

thrust::device_vector<int> d_output(10);
thrust::scatter(d_values.begin(), d_values.end(),
                d_map.begin(), d_output.begin());
// d_output is now {1, 1, 1, 1, 1, 0, 0, 0, 0, 0}

Note

scatter is the inverse of thrust::gather.

Parameters:
  • first – Beginning of the sequence of values to scatter.

  • last – End of the sequence of values to scatter.

  • map – Beginning of the sequence of output indices.

  • result – Destination of the source elements.

Template Parameters:
  • InputIterator1 – must be a model of Input Iterator and InputIterator1's value_type must be convertible to RandomAccessIterator's value_type.

  • InputIterator2 – must be a model of Input Iterator and InputIterator2's value_type must be convertible to RandomAccessIterator's difference_type.

  • RandomAccessIterator – must be a model of Random Access iterator.

Pre:

The iterator result + i shall not refer to any element referenced by any iterator j in the range [first,last) for all iterators i in the range [map,map + (last - first)).

Pre:

The iterator result + i shall not refer to any element referenced by any iterator j in the range [map,map + (last - first)) for all iterators i in the range [map,map + (last - first)).

Pre:

The expression result[*i] shall be valid for all iterators in the range [map,map + (last - first)).

template<typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename InputIterator3, typename RandomAccessIterator>
__host__ __device__ void scatter_if(const thrust::detail::execution_policy_base<DerivedPolicy> &exec, InputIterator1 first, InputIterator1 last, InputIterator2 map, InputIterator3 stencil, RandomAccessIterator output)#

scatter_if conditionally copies elements from a source range into an output array according to a map. For each iterator i in the range [first, last) such that *(stencil + (i - first)) is true, the value *i is assigned to output[*(map + (i - first))]. The output iterator must permit random access. If the same index appears more than once in the range [map, map + (last - first)) the result is undefined.

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

#include <thrust/scatter.h>
#include <thrust/execution_policy.h>
...
int V[8] = {10, 20, 30, 40, 50, 60, 70, 80};
int M[8] = {0, 5, 1, 6, 2, 7, 3, 4};
int S[8] = {1, 0, 1, 0, 1, 0, 1, 0};
int D[8] = {0, 0, 0, 0, 0, 0, 0, 0};

thrust::scatter_if(thrust::host, V, V + 8, M, S, D);

// D contains [10, 30, 50, 70, 0, 0, 0, 0];

Note

scatter_if is the inverse of thrust::gather_if.

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

  • first – Beginning of the sequence of values to scatter.

  • last – End of the sequence of values to scatter.

  • map – Beginning of the sequence of output indices.

  • stencil – Beginning of the sequence of predicate values.

  • output – Beginning of the destination range.

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

  • InputIterator1 – must be a model of Input Iterator and InputIterator1's value_type must be convertible to RandomAccessIterator's value_type.

  • InputIterator2 – must be a model of Input Iterator and InputIterator2's value_type must be convertible to RandomAccessIterator's difference_type.

  • InputIterator3 – must be a model of Input Iterator and InputIterator3's value_type must be convertible to bool.

  • RandomAccessIterator – must be a model of Random Access iterator.

Pre:

The iterator result + i shall not refer to any element referenced by any iterator j in the range [first,last) for all iterators i in the range [map,map + (last - first)).

Pre:

The iterator result + i shall not refer to any element referenced by any iterator j in the range [map,map + (last - first)) for all iterators i in the range [map,map + (last - first)).

Pre:

The iterator result + i shall not refer to any element referenced by any iterator j in the range [stencil,stencil + (last - first)) for all iterators i in the range [map,map + (last - first)).

Pre:

The expression result[*i] shall be valid for all iterators i in the range [map,map + (last - first)) for which the following condition holds: *(stencil + i) != false.

template<typename InputIterator1, typename InputIterator2, typename InputIterator3, typename RandomAccessIterator>
void scatter_if(InputIterator1 first, InputIterator1 last, InputIterator2 map, InputIterator3 stencil, RandomAccessIterator output)#

scatter_if conditionally copies elements from a source range into an output array according to a map. For each iterator i in the range [first, last) such that *(stencil + (i - first)) is true, the value *i is assigned to output[*(map + (i - first))]. The output iterator must permit random access. If the same index appears more than once in the range [map, map + (last - first)) the result is undefined.

#include <thrust/scatter.h>
...
int V[8] = {10, 20, 30, 40, 50, 60, 70, 80};
int M[8] = {0, 5, 1, 6, 2, 7, 3, 4};
int S[8] = {1, 0, 1, 0, 1, 0, 1, 0};
int D[8] = {0, 0, 0, 0, 0, 0, 0, 0};

thrust::scatter_if(V, V + 8, M, S, D);

// D contains [10, 30, 50, 70, 0, 0, 0, 0];

Note

scatter_if is the inverse of thrust::gather_if.

Parameters:
  • first – Beginning of the sequence of values to scatter.

  • last – End of the sequence of values to scatter.

  • map – Beginning of the sequence of output indices.

  • stencil – Beginning of the sequence of predicate values.

  • output – Beginning of the destination range.

Template Parameters:
  • InputIterator1 – must be a model of Input Iterator and InputIterator1's value_type must be convertible to RandomAccessIterator's value_type.

  • InputIterator2 – must be a model of Input Iterator and InputIterator2's value_type must be convertible to RandomAccessIterator's difference_type.

  • InputIterator3 – must be a model of Input Iterator and InputIterator3's value_type must be convertible to bool.

  • RandomAccessIterator – must be a model of Random Access iterator.

Pre:

The iterator result + i shall not refer to any element referenced by any iterator j in the range [first,last) for all iterators i in the range [map,map + (last - first)).

Pre:

The iterator result + i shall not refer to any element referenced by any iterator j in the range [map,map + (last - first)) for all iterators i in the range [map,map + (last - first)).

Pre:

The iterator result + i shall not refer to any element referenced by any iterator j in the range [stencil,stencil + (last - first)) for all iterators i in the range [map,map + (last - first)).

Pre:

The expression result[*i] shall be valid for all iterators i in the range [map,map + (last - first)) for which the following condition holds: *(stencil + i) != false.

template<typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename InputIterator3, typename RandomAccessIterator, typename Predicate>
__host__ __device__ void scatter_if(const thrust::detail::execution_policy_base<DerivedPolicy> &exec, InputIterator1 first, InputIterator1 last, InputIterator2 map, InputIterator3 stencil, RandomAccessIterator output, Predicate pred)#

scatter_if conditionally copies elements from a source range into an output array according to a map. For each iterator i in the range [first, last) such that pred(*(stencil + (i - first))) is true, the value *i is assigned to output[*(map + (i - first))]. The output iterator must permit random access. If the same index appears more than once in the range [map, map + (last - first)) the result is undefined.

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

#include <thrust/scatter.h>
#include <thrust/execution_policy.h>

struct is_even
{
  __host__ __device__
  bool operator()(int x)
  {
    return (x % 2) == 0;
  }
};

...

int V[8] = {10, 20, 30, 40, 50, 60, 70, 80};
int M[8] = {0, 5, 1, 6, 2, 7, 3, 4};
int S[8] = {2, 1, 2, 1, 2, 1, 2, 1};
int D[8] = {0, 0, 0, 0, 0, 0, 0, 0};

is_even pred;
thrust::scatter_if(thrust::host, V, V + 8, M, S, D, pred);

// D contains [10, 30, 50, 70, 0, 0, 0, 0];

Note

scatter_if is the inverse of thrust::gather_if.

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

  • first – Beginning of the sequence of values to scatter.

  • last – End of the sequence of values to scatter.

  • map – Beginning of the sequence of output indices.

  • stencil – Beginning of the sequence of predicate values.

  • output – Beginning of the destination range.

  • pred – Predicate to apply to the stencil values.

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

  • InputIterator1 – must be a model of Input Iterator and InputIterator1's value_type must be convertible to RandomAccessIterator's value_type.

  • InputIterator2 – must be a model of Input Iterator and InputIterator2's value_type must be convertible to RandomAccessIterator's difference_type.

  • InputIterator3 – must be a model of Input Iterator and InputIterator3's value_type must be convertible to Predicate's argument_type.

  • RandomAccessIterator – must be a model of Random Access iterator.

  • Predicate – must be a model of Predicate.

Pre:

The iterator result + i shall not refer to any element referenced by any iterator j in the range [first,last) for all iterators i in the range [map,map + (last - first)).

Pre:

The iterator result + i shall not refer to any element referenced by any iterator j in the range [map,map + (last - first)) for all iterators i in the range [map,map + (last - first)).

Pre:

The iterator result + i shall not refer to any element referenced by any iterator j in the range [stencil,stencil + (last - first)) for all iterators i in the range [map,map + (last - first)).

Pre:

The expression result[*i] shall be valid for all iterators i in the range [map,map + (last - first)) for which the following condition holds: pred(*(stencil + i)) != false.

template<typename InputIterator1, typename InputIterator2, typename InputIterator3, typename RandomAccessIterator, typename Predicate>
void scatter_if(InputIterator1 first, InputIterator1 last, InputIterator2 map, InputIterator3 stencil, RandomAccessIterator output, Predicate pred)#

scatter_if conditionally copies elements from a source range into an output array according to a map. For each iterator i in the range [first, last) such that pred(*(stencil + (i - first))) is true, the value *i is assigned to output[*(map + (i - first))]. The output iterator must permit random access. If the same index appears more than once in the range [map, map + (last - first)) the result is undefined.

#include <thrust/scatter.h>

struct is_even
{
  __host__ __device__
  bool operator()(int x)
  {
    return (x % 2) == 0;
  }
};

...

int V[8] = {10, 20, 30, 40, 50, 60, 70, 80};
int M[8] = {0, 5, 1, 6, 2, 7, 3, 4};
int S[8] = {2, 1, 2, 1, 2, 1, 2, 1};
int D[8] = {0, 0, 0, 0, 0, 0, 0, 0};

is_even pred;
thrust::scatter_if(V, V + 8, M, S, D, pred);

// D contains [10, 30, 50, 70, 0, 0, 0, 0];

Note

scatter_if is the inverse of thrust::gather_if.

Parameters:
  • first – Beginning of the sequence of values to scatter.

  • last – End of the sequence of values to scatter.

  • map – Beginning of the sequence of output indices.

  • stencil – Beginning of the sequence of predicate values.

  • output – Beginning of the destination range.

  • pred – Predicate to apply to the stencil values.

Template Parameters:
  • InputIterator1 – must be a model of Input Iterator and InputIterator1's value_type must be convertible to RandomAccessIterator's value_type.

  • InputIterator2 – must be a model of Input Iterator and InputIterator2's value_type must be convertible to RandomAccessIterator's difference_type.

  • InputIterator3 – must be a model of Input Iterator and InputIterator3's value_type must be convertible to Predicate's argument_type.

  • RandomAccessIterator – must be a model of Random Access iterator.

  • Predicate – must be a model of Predicate.

Pre:

The iterator result + i shall not refer to any element referenced by any iterator j in the range [first,last) for all iterators i in the range [map,map + (last - first)).

Pre:

The iterator result + i shall not refer to any element referenced by any iterator j in the range [map,map + (last - first)) for all iterators i in the range [map,map + (last - first)).

Pre:

The iterator result + i shall not refer to any element referenced by any iterator j in the range [stencil,stencil + (last - first)) for all iterators i in the range [map,map + (last - first)).

Pre:

The expression result[*i] shall be valid for all iterators i in the range [map,map + (last - first)) for which the following condition holds: pred(*(stencil + i)) != false.

Merging#

group merging

Functions

template<typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator>
__host__ __device__ OutputIterator merge(const thrust::detail::execution_policy_base<DerivedPolicy> &exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)#

merge combines two sorted ranges [first1, last1) and [first2, last2) into a single sorted range. That is, it copies from [first1, last1) and [first2, last2) into [result, result + (last1 - first1) + (last2 - first2)) such that the resulting range is in ascending order. merge is stable, meaning both that the relative order of elements within each input range is preserved, and that for equivalent elements in both input ranges the element from the first range precedes the element from the second. The return value is result + (last1 - first1) + (last2 - first2).

This version of merge compares elements using operator<.

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

The following code snippet demonstrates how to use merge to compute the merger of two sorted sets of integers using the thrust::host execution policy for parallelization:

#include <thrust/merge.h>
#include <thrust/execution_policy.h>
...
int A1[6] = {1, 3, 5, 7, 9, 11};
int A2[7] = {1, 1, 2, 3, 5,  8, 13};

int result[13];

int *result_end =
  thrust::merge(thrust::host,
                A1, A1 + 6,
                A2, A2 + 7,
                result);
// result = {1, 1, 1, 2, 3, 3, 5, 5, 7, 8, 9, 11, 13}

See also

set_union

See also

sort

See also

is_sorted

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

  • first1 – The beginning of the first input range.

  • last1 – The end of the first input range.

  • first2 – The beginning of the second input range.

  • last2 – The end of the second input range.

  • result – The beginning of the merged output.

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

  • InputIterator1 – is a model of Input Iterator, InputIterator1 and InputIterator2 have the same value_type, InputIterator1's value_type is a model of LessThan Comparable, the ordering on InputIterator1's value_type is a strict weak ordering, as defined in the LessThan Comparable requirements, and InputIterator1's value_type is convertable to a type in OutputIterator's set of value_types.

  • InputIterator2 – is a model of Input Iterator, InputIterator2 and InputIterator1 have the same value_type, InputIterator2's value_type is a model of LessThan Comparable, the ordering on InputIterator2's value_type is a strict weak ordering, as defined in the LessThan Comparable requirements, and InputIterator2's value_type is convertable to a type in OutputIterator's set of value_types.

  • OutputIterator – is a model of Output Iterator.

Returns:

The end of the output range.

Pre:

The ranges [first1, last1) and [first2, last2) shall be sorted with respect to operator<.

Pre:

The resulting range shall not overlap with either input range.

template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)#

merge combines two sorted ranges [first1, last1) and [first2, last2) into a single sorted range. That is, it copies from [first1, last1) and [first2, last2) into [result, result + (last1 - first1) + (last2 - first2)) such that the resulting range is in ascending order. merge is stable, meaning both that the relative order of elements within each input range is preserved, and that for equivalent elements in both input ranges the element from the first range precedes the element from the second. The return value is result + (last1 - first1) + (last2 - first2).

This version of merge compares elements using operator<.

The following code snippet demonstrates how to use merge to compute the merger of two sorted sets of integers.

#include <thrust/merge.h>
...
int A1[6] = {1, 3, 5, 7, 9, 11};
int A2[7] = {1, 1, 2, 3, 5,  8, 13};

int result[13];

int *result_end = thrust::merge(A1, A1 + 6, A2, A2 + 7, result);
// result = {1, 1, 1, 2, 3, 3, 5, 5, 7, 8, 9, 11, 13}

See also

set_union

See also

sort

See also

is_sorted

Parameters:
  • first1 – The beginning of the first input range.

  • last1 – The end of the first input range.

  • first2 – The beginning of the second input range.

  • last2 – The end of the second input range.

  • result – The beginning of the merged output.

Template Parameters:
  • InputIterator1 – is a model of Input Iterator, InputIterator1 and InputIterator2 have the same value_type, InputIterator1's value_type is a model of LessThan Comparable, the ordering on InputIterator1's value_type is a strict weak ordering, as defined in the LessThan Comparable requirements, and InputIterator1's value_type is convertable to a type in OutputIterator's set of value_types.

  • InputIterator2 – is a model of Input Iterator, InputIterator2 and InputIterator1 have the same value_type, InputIterator2's value_type is a model of LessThan Comparable, the ordering on InputIterator2's value_type is a strict weak ordering, as defined in the LessThan Comparable requirements, and InputIterator2's value_type is convertable to a type in OutputIterator's set of value_types.

  • OutputIterator – is a model of Output Iterator.

Returns:

The end of the output range.

Pre:

The ranges [first1, last1) and [first2, last2) shall be sorted with respect to operator<.

Pre:

The resulting range shall not overlap with either input range.

template<typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator, typename StrictWeakCompare>
__host__ __device__ OutputIterator merge(const thrust::detail::execution_policy_base<DerivedPolicy> &exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakCompare comp)#

merge combines two sorted ranges [first1, last1) and [first2, last2) into a single sorted range. That is, it copies from [first1, last1) and [first2, last2) into [result, result + (last1 - first1) + (last2 - first2)) such that the resulting range is in ascending order. merge is stable, meaning both that the relative order of elements within each input range is preserved, and that for equivalent elements in both input ranges the element from the first range precedes the element from the second. The return value is result + (last1 - first1) + (last2 - first2).

This version of merge compares elements using a function object comp.

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

The following code snippet demonstrates how to use merge to compute the merger of two sets of integers sorted in descending order using the thrust::host execution policy for parallelization:

#include <thrust/merge.h>
#include <thrust/functional.h>
#include <thrust/execution_policy.h>
...
int A1[6] = {11, 9, 7, 5, 3, 1};
int A2[7] = {13, 8, 5, 3, 2, 1, 1};

int result[13];

int *result_end = thrust::merge(thrust::host,
                                A1, A1 + 6,
                                A2, A2 + 7,
                                result,
                                thrust::greater<int>());
// result = {13, 11, 9, 8, 7, 5, 5, 3, 3, 2, 1, 1, 1}

See also

sort

See also

is_sorted

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

  • first1 – The beginning of the first input range.

  • last1 – The end of the first input range.

  • first2 – The beginning of the second input range.

  • last2 – The end of the second input range.

  • result – The beginning of the merged output.

  • comp – Comparison operator.

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

  • InputIterator1 – is a model of Input Iterator, InputIterator1's value_type is convertable to StrictWeakCompare's first_argument_type. and InputIterator1's value_type is convertable to a type in OutputIterator's set of value_types.

  • InputIterator2 – is a model of Input Iterator, InputIterator2's value_type is convertable to StrictWeakCompare's second_argument_type. and InputIterator2's value_type is convertable to a type in OutputIterator's set of value_types.

  • OutputIterator – is a model of Output Iterator.

  • StrictWeakCompare – is a model of Strict Weak Ordering.

Returns:

The end of the output range.

Pre:

The ranges [first1, last1) and [first2, last2) shall be sorted with respect to comp.

Pre:

The resulting range shall not overlap with either input range.

template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename StrictWeakCompare>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakCompare comp)#

merge combines two sorted ranges [first1, last1) and [first2, last2) into a single sorted range. That is, it copies from [first1, last1) and [first2, last2) into [result, result + (last1 - first1) + (last2 - first2)) such that the resulting range is in ascending order. merge is stable, meaning both that the relative order of elements within each input range is preserved, and that for equivalent elements in both input ranges the element from the first range precedes the element from the second. The return value is result + (last1 - first1) + (last2 - first2).

This version of merge compares elements using a function object comp.

The following code snippet demonstrates how to use merge to compute the merger of two sets of integers sorted in descending order.

#include <thrust/merge.h>
#include <thrust/functional.h>
...
int A1[6] = {11, 9, 7, 5, 3, 1};
int A2[7] = {13, 8, 5, 3, 2, 1, 1};

int result[13];

int *result_end = thrust::merge(A1, A1 + 6, A2, A2 + 7, result, thrust::greater<int>());
// result = {13, 11, 9, 8, 7, 5, 5, 3, 3, 2, 1, 1, 1}

See also

sort

See also

is_sorted

Parameters:
  • first1 – The beginning of the first input range.

  • last1 – The end of the first input range.

  • first2 – The beginning of the second input range.

  • last2 – The end of the second input range.

  • result – The beginning of the merged output.

  • comp – Comparison operator.

Template Parameters:
  • InputIterator1 – is a model of Input Iterator, InputIterator1's value_type is convertable to StrictWeakCompare's first_argument_type. and InputIterator1's value_type is convertable to a type in OutputIterator's set of value_types.

  • InputIterator2 – is a model of Input Iterator, InputIterator2's value_type is convertable to StrictWeakCompare's second_argument_type. and InputIterator2's value_type is convertable to a type in OutputIterator's set of value_types.

  • OutputIterator – is a model of Output Iterator.

  • StrictWeakCompare – is a model of Strict Weak Ordering.

Returns:

The end of the output range.

Pre:

The ranges [first1, last1) and [first2, last2) shall be sorted with respect to comp.

Pre:

The resulting range shall not overlap with either input range.

template<typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename InputIterator3, typename InputIterator4, typename OutputIterator1, typename OutputIterator2>
__host__ __device__ thrust::pair<OutputIterator1, OutputIterator2> merge_by_key(const thrust::detail::execution_policy_base<DerivedPolicy> &exec, InputIterator1 keys_first1, InputIterator1 keys_last1, InputIterator2 keys_first2, InputIterator2 keys_last2, InputIterator3 values_first1, InputIterator4 values_first2, OutputIterator1 keys_result, OutputIterator2 values_result)#

merge_by_key performs a key-value merge. That is, merge_by_key copies elements from [keys_first1, keys_last1) and [keys_first2, keys_last2) into a single range, [keys_result, keys_result + (keys_last1 - keys_first1) + (keys_last2 - keys_first2)) such that the resulting range is in ascending key order.

At the same time, merge_by_key copies elements from the two associated ranges [values_first1 + (keys_last1 - keys_first1)) and [values_first2 + (keys_last2 - keys_first2)) into a single range, [values_result, values_result + (keys_last1 - keys_first1) + (keys_last2 - keys_first2)) such that the resulting range is in ascending order implied by each input element’s associated key.

merge_by_key is stable, meaning both that the relative order of elements within each input range is preserved, and that for equivalent elements in all input key ranges the element from the first range precedes the element from the second.

The return value is is (keys_result + (keys_last1 - keys_first1) + (keys_last2 - keys_first2)) and (values_result + (keys_last1 - keys_first1) + (keys_last2 - keys_first2)).

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

The following code snippet demonstrates how to use merge_by_key to compute the merger of two sets of integers sorted in ascending order using the thrust::host execution policy for parallelization:

#include <thrust/merge.h>
#include <thrust/functional.h>
#include <thrust/execution_policy.h>
...
int A_keys[6] = {1, 3, 5, 7, 9, 11};
int A_vals[6] = {0, 0, 0, 0, 0, 0};

int B_keys[7] = {1, 1, 2, 3, 5, 8, 13};
int B_vals[7] = {1, 1, 1, 1, 1, 1, 1};

int keys_result[13];
int vals_result[13];

thrust::pair<int*,int*> end =
  thrust::merge_by_key(thrust::host,
                       A_keys, A_keys + 6,
                       B_keys, B_keys + 7,
                       A_vals, B_vals,
                       keys_result, vals_result);

// keys_result = {1, 1, 1, 2, 3, 3, 5, 5, 7, 8, 9, 11, 13}
// vals_result = {0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0,  0,  1}

See also

merge

See also

sort_by_key

See also

is_sorted

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

  • keys_first1 – The beginning of the first input range of keys.

  • keys_last1 – The end of the first input range of keys.

  • keys_first2 – The beginning of the second input range of keys.

  • keys_last2 – The end of the second input range of keys.

  • values_first1 – The beginning of the first input range of values.

  • values_first2 – The beginning of the first input range of values.

  • keys_result – The beginning of the merged output range of keys.

  • values_result – The beginning of the merged output range of values.

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

  • InputIterator1 – is a model of Input Iterator, InputIterator1 and InputIterator2 have the same value_type, InputIterator1's value_type is a model of LessThan Comparable, the ordering on InputIterator1's value_type is a strict weak ordering, as defined in the LessThan Comparable requirements, and InputIterator1's value_type is convertable to a type in OutputIterator's set of value_types.

  • InputIterator2 – is a model of Input Iterator, InputIterator2 and InputIterator1 have the same value_type, InputIterator2's value_type is a model of LessThan Comparable, the ordering on InputIterator2's value_type is a strict weak ordering, as defined in the LessThan Comparable requirements, and InputIterator2's value_type is convertable to a type in OutputIterator's set of value_types.

  • InputIterator3 – is a model of Input Iterator, and InputIterator3's value_type is convertible to a type in OutputIterator2's set of value_types.

  • InputIterator4 – is a model of Input Iterator, and InputIterator4's value_type is convertible to a type in OutputIterator2's set of value_types.

  • OutputIterator1 – is a model of Output Iterator.

  • OutputIterator2 – is a model of Output Iterator.

Returns:

A pair p such that p.first is the end of the output range of keys, and such that p.second is the end of the output range of values.

Pre:

The ranges [keys_first1, keys_last1) and [keys_first2, keys_last2) shall be sorted with respect to operator<.

Pre:

The resulting ranges shall not overlap with any input range.

template<typename InputIterator1, typename InputIterator2, typename InputIterator3, typename InputIterator4, typename OutputIterator1, typename OutputIterator2>
thrust::pair<OutputIterator1, OutputIterator2> merge_by_key(InputIterator1 keys_first1, InputIterator1 keys_last1, InputIterator2 keys_first2, InputIterator2 keys_last2, InputIterator3 values_first1, InputIterator4 values_first2, OutputIterator1 keys_result, OutputIterator2 values_result)#

merge_by_key performs a key-value merge. That is, merge_by_key copies elements from [keys_first1, keys_last1) and [keys_first2, keys_last2) into a single range, [keys_result, keys_result + (keys_last1 - keys_first1) + (keys_last2 - keys_first2)) such that the resulting range is in ascending key order.

At the same time, merge_by_key copies elements from the two associated ranges [values_first1 + (keys_last1 - keys_first1)) and [values_first2 + (keys_last2 - keys_first2)) into a single range, [values_result, values_result + (keys_last1 - keys_first1) + (keys_last2 - keys_first2)) such that the resulting range is in ascending order implied by each input element’s associated key.

merge_by_key is stable, meaning both that the relative order of elements within each input range is preserved, and that for equivalent elements in all input key ranges the element from the first range precedes the element from the second.

The return value is is (keys_result + (keys_last1 - keys_first1) + (keys_last2 - keys_first2)) and (values_result + (keys_last1 - keys_first1) + (keys_last2 - keys_first2)).

The following code snippet demonstrates how to use merge_by_key to compute the merger of two sets of integers sorted in ascending order.

#include <thrust/merge.h>
#include <thrust/functional.h>
...
int A_keys[6] = {1, 3, 5, 7, 9, 11};
int A_vals[6] = {0, 0, 0, 0, 0, 0};

int B_keys[7] = {1, 1, 2, 3, 5, 8, 13};
int B_vals[7] = {1, 1, 1, 1, 1, 1, 1};

int keys_result[13];
int vals_result[13];

thrust::pair<int*,int*> end = thrust::merge_by_key(A_keys, A_keys + 6, B_keys, B_keys + 7, A_vals, B_vals, keys_result, vals_result);

// keys_result = {1, 1, 1, 2, 3, 3, 5, 5, 7, 8, 9, 11, 13}
// vals_result = {0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0,  0,  1}

See also

merge

See also

sort_by_key

See also

is_sorted

Parameters:
  • keys_first1 – The beginning of the first input range of keys.

  • keys_last1 – The end of the first input range of keys.

  • keys_first2 – The beginning of the second input range of keys.

  • keys_last2 – The end of the second input range of keys.

  • values_first1 – The beginning of the first input range of values.

  • values_first2 – The beginning of the first input range of values.

  • keys_result – The beginning of the merged output range of keys.

  • values_result – The beginning of the merged output range of values.

Template Parameters:
  • InputIterator1 – is a model of Input Iterator, InputIterator1 and InputIterator2 have the same value_type, InputIterator1's value_type is a model of LessThan Comparable, the ordering on InputIterator1's value_type is a strict weak ordering, as defined in the LessThan Comparable requirements, and InputIterator1's value_type is convertable to a type in OutputIterator's set of value_types.

  • InputIterator2 – is a model of Input Iterator, InputIterator2 and InputIterator1 have the same value_type, InputIterator2's value_type is a model of LessThan Comparable, the ordering on InputIterator2's value_type is a strict weak ordering, as defined in the LessThan Comparable requirements, and InputIterator2's value_type is convertable to a type in OutputIterator's set of value_types.

  • InputIterator3 – is a model of Input Iterator, and InputIterator3's value_type is convertible to a type in OutputIterator2's set of value_types.

  • InputIterator4 – is a model of Input Iterator, and InputIterator4's value_type is convertible to a type in OutputIterator2's set of value_types.

  • OutputIterator1 – is a model of Output Iterator.

  • OutputIterator2 – is a model of Output Iterator.

Returns:

A pair p such that p.first is the end of the output range of keys, and such that p.second is the end of the output range of values.

Pre:

The ranges [keys_first1, keys_last1) and [keys_first2, keys_last2) shall be sorted with respect to operator<.

Pre:

The resulting ranges shall not overlap with any input range.

template<typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename InputIterator3, typename InputIterator4, typename OutputIterator1, typename OutputIterator2, typename Compare>
__host__ __device__ thrust::pair<OutputIterator1, OutputIterator2> merge_by_key(const thrust::detail::execution_policy_base<DerivedPolicy> &exec, InputIterator1 keys_first1, InputIterator1 keys_last1, InputIterator2 keys_first2, InputIterator2 keys_last2, InputIterator3 values_first1, InputIterator4 values_first2, OutputIterator1 keys_result, OutputIterator2 values_result, Compare comp)#

merge_by_key performs a key-value merge. That is, merge_by_key copies elements from [keys_first1, keys_last1) and [keys_first2, keys_last2) into a single range, [keys_result, keys_result + (keys_last1 - keys_first1) + (keys_last2 - keys_first2)) such that the resulting range is in ascending key order.

At the same time, merge_by_key copies elements from the two associated ranges [values_first1 + (keys_last1 - keys_first1)) and [values_first2 + (keys_last2 - keys_first2)) into a single range, [values_result, values_result + (keys_last1 - keys_first1) + (keys_last2 - keys_first2)) such that the resulting range is in ascending order implied by each input element’s associated key.

merge_by_key is stable, meaning both that the relative order of elements within each input range is preserved, and that for equivalent elements in all input key ranges the element from the first range precedes the element from the second.

The return value is is (keys_result + (keys_last1 - keys_first1) + (keys_last2 - keys_first2)) and (values_result + (keys_last1 - keys_first1) + (keys_last2 - keys_first2)).

This version of merge_by_key compares key elements using a function object comp.

The algorithm’s execution is parallelized using exec.

The following code snippet demonstrates how to use merge_by_key to compute the merger of two sets of integers sorted in descending order using the thrust::host execution policy for parallelization:

#include <thrust/merge.h>
#include <thrust/functional.h>
#include <thrust/execution_policy.h>
...
int A_keys[6] = {11, 9, 7, 5, 3, 1};
int A_vals[6] = { 0, 0, 0, 0, 0, 0};

int B_keys[7] = {13, 8, 5, 3, 2, 1, 1};
int B_vals[7] = { 1, 1, 1, 1, 1, 1, 1};

int keys_result[13];
int vals_result[13];

thrust::pair<int*,int*> end =
  thrust::merge_by_key(thrust::host,
                       A_keys, A_keys + 6,
                       B_keys, B_keys + 7,
                       A_vals, B_vals,
                       keys_result, vals_result,
                       thrust::greater<int>());

// keys_result = {13, 11, 9, 8, 7, 5, 5, 3, 3, 2, 1, 1, 1}
// vals_result = { 1,  0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1}

See also

merge

See also

sort_by_key

See also

is_sorted

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

  • keys_first1 – The beginning of the first input range of keys.

  • keys_last1 – The end of the first input range of keys.

  • keys_first2 – The beginning of the second input range of keys.

  • keys_last2 – The end of the second input range of keys.

  • values_first1 – The beginning of the first input range of values.

  • values_first2 – The beginning of the first input range of values.

  • keys_result – The beginning of the merged output range of keys.

  • values_result – The beginning of the merged output range of values.

  • comp – Comparison operator.

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

  • InputIterator1 – is a model of Input Iterator, InputIterator1's value_type is convertable to StrictWeakCompare's first_argument_type. and InputIterator1's value_type is convertable to a type in OutputIterator1's set of value_types.

  • InputIterator2 – is a model of Input Iterator, InputIterator2's value_type is convertable to StrictWeakCompare's second_argument_type. and InputIterator2's value_type is convertable to a type in OutputIterator1's set of value_types.

  • InputIterator3 – is a model of Input Iterator, and InputIterator3's value_type is convertible to a type in OutputIterator2's set of value_types.

  • InputIterator4 – is a model of Input Iterator, and InputIterator4's value_type is convertible to a type in OutputIterator2's set of value_types.

  • OutputIterator1 – is a model of Output Iterator.

  • OutputIterator2 – is a model of Output Iterator.

  • StrictWeakCompare – is a model of Strict Weak Ordering.

Returns:

A pair p such that p.first is the end of the output range of keys, and such that p.second is the end of the output range of values.

Pre:

The ranges [keys_first1, keys_last1) and [keys_first2, keys_last2) shall be sorted with respect to comp.

Pre:

The resulting ranges shall not overlap with any input range.

template<typename InputIterator1, typename InputIterator2, typename InputIterator3, typename InputIterator4, typename OutputIterator1, typename OutputIterator2, typename StrictWeakCompare>
thrust::pair<OutputIterator1, OutputIterator2> merge_by_key(InputIterator1 keys_first1, InputIterator1 keys_last1, InputIterator2 keys_first2, InputIterator2 keys_last2, InputIterator3 values_first1, InputIterator4 values_first2, OutputIterator1 keys_result, OutputIterator2 values_result, StrictWeakCompare comp)#

merge_by_key performs a key-value merge. That is, merge_by_key copies elements from [keys_first1, keys_last1) and [keys_first2, keys_last2) into a single range, [keys_result, keys_result + (keys_last1 - keys_first1) + (keys_last2 - keys_first2)) such that the resulting range is in ascending key order.

At the same time, merge_by_key copies elements from the two associated ranges [values_first1 + (keys_last1 - keys_first1)) and [values_first2 + (keys_last2 - keys_first2)) into a single range, [values_result, values_result + (keys_last1 - keys_first1) + (keys_last2 - keys_first2)) such that the resulting range is in ascending order implied by each input element’s associated key.

merge_by_key is stable, meaning both that the relative order of elements within each input range is preserved, and that for equivalent elements in all input key ranges the element from the first range precedes the element from the second.

The return value is is (keys_result + (keys_last1 - keys_first1) + (keys_last2 - keys_first2)) and (values_result + (keys_last1 - keys_first1) + (keys_last2 - keys_first2)).

This version of merge_by_key compares key elements using a function object comp.

The following code snippet demonstrates how to use merge_by_key to compute the merger of two sets of integers sorted in descending order.

#include <thrust/merge.h>
#include <thrust/functional.h>
...
int A_keys[6] = {11, 9, 7, 5, 3, 1};
int A_vals[6] = { 0, 0, 0, 0, 0, 0};

int B_keys[7] = {13, 8, 5, 3, 2, 1, 1};
int B_vals[7] = { 1, 1, 1, 1, 1, 1, 1};

int keys_result[13];
int vals_result[13];

thrust::pair<int*,int*> end = thrust::merge_by_key(A_keys, A_keys + 6, B_keys, B_keys + 7, A_vals, B_vals, keys_result, vals_result, thrust::greater<int>());

// keys_result = {13, 11, 9, 8, 7, 5, 5, 3, 3, 2, 1, 1, 1}
// vals_result = { 1,  0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1}

See also

merge

See also

sort_by_key

See also

is_sorted

Parameters:
  • keys_first1 – The beginning of the first input range of keys.

  • keys_last1 – The end of the first input range of keys.

  • keys_first2 – The beginning of the second input range of keys.

  • keys_last2 – The end of the second input range of keys.

  • values_first1 – The beginning of the first input range of values.

  • values_first2 – The beginning of the first input range of values.

  • keys_result – The beginning of the merged output range of keys.

  • values_result – The beginning of the merged output range of values.

  • comp – Comparison operator.

Template Parameters:
  • InputIterator1 – is a model of Input Iterator, InputIterator1's value_type is convertable to StrictWeakCompare's first_argument_type. and InputIterator1's value_type is convertable to a type in OutputIterator1's set of value_types.

  • InputIterator2 – is a model of Input Iterator, InputIterator2's value_type is convertable to StrictWeakCompare's second_argument_type. and InputIterator2's value_type is convertable to a type in OutputIterator1's set of value_types.

  • InputIterator3 – is a model of Input Iterator, and InputIterator3's value_type is convertible to a type in OutputIterator2's set of value_types.

  • InputIterator4 – is a model of Input Iterator, and InputIterator4's value_type is convertible to a type in OutputIterator2's set of value_types.

  • OutputIterator1 – is a model of Output Iterator.

  • OutputIterator2 – is a model of Output Iterator.

  • StrictWeakCompare – is a model of Strict Weak Ordering.

Returns:

A pair p such that p.first is the end of the output range of keys, and such that p.second is the end of the output range of values.

Pre:

The ranges [keys_first1, keys_last1) and [keys_first2, keys_last2) shall be sorted with respect to comp.

Pre:

The resulting ranges shall not overlap with any input range.

Prefixsums#

group prefixsums

Functions

template<typename DerivedPolicy, typename InputIterator, typename OutputIterator>
__host__ __device__ OutputIterator inclusive_scan(const thrust::detail::execution_policy_base<DerivedPolicy> &exec, InputIterator first, InputIterator last, OutputIterator result)#

inclusive_scan computes an inclusive prefix sum operation. The term ‘inclusive’ means that each result includes the corresponding input operand in the partial sum. More precisely, *first is assigned to *result and the sum of *first and *(first + 1) is assigned to *(result + 1), and so on. This version of inclusive_scan assumes plus as the associative operator. When the input and output sequences are the same, the scan is performed in-place.

inclusive_scan is similar to std::partial_sum in the STL. The primary difference between the two functions is that std::partial_sum guarantees a serial summation order, while inclusive_scan requires associativity of the binary operation to parallelize the prefix sum.

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 to compute an in-place prefix sum using the thrust::host execution policy for parallelization:

#include <thrust/scan.h>
#include <thrust/execution_policy.h>
...

int data[6] = {1, 0, 2, 2, 1, 3};

thrust::inclusive_scan(thrust::host, data, data + 6, data); // in-place scan

// data is now {1, 1, 3, 5, 6, 9}

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

  • first – The beginning of the input sequence.

  • last – The end of the input sequence.

  • result – The beginning of the output sequence.

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

  • InputIterator – is a model of Input Iterator and InputIterator's value_type is convertible to OutputIterator's value_type.

  • OutputIterator – is a model of Output Iterator, and if x and y are objects of OutputIterator's value_type, then x + y is defined. If T is OutputIterator's value_type, then T(0) is defined.

Returns:

The end of the output sequence.

Pre:

first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

template<typename InputIterator, typename OutputIterator>
OutputIterator inclusive_scan(InputIterator first, InputIterator last, OutputIterator result)#

inclusive_scan computes an inclusive prefix sum operation. The term ‘inclusive’ means that each result includes the corresponding input operand in the partial sum. More precisely, *first is assigned to *result and the sum of *first and *(first + 1) is assigned to *(result + 1), and so on. This version of inclusive_scan assumes plus as the associative operator. When the input and output sequences are the same, the scan is performed in-place.

inclusive_scan is similar to std::partial_sum in the STL. The primary difference between the two functions is that std::partial_sum guarantees a serial summation order, while inclusive_scan requires associativity of the binary operation to parallelize the prefix sum.

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

#include <thrust/scan.h>

int data[6] = {1, 0, 2, 2, 1, 3};

thrust::inclusive_scan(data, data + 6, data); // in-place scan

// data is now {1, 1, 3, 5, 6, 9}

Parameters:
  • first – The beginning of the input sequence.

  • last – The end of the input sequence.

  • result – The beginning of the output sequence.

Template Parameters:
  • InputIterator – is a model of Input Iterator and InputIterator's value_type is convertible to OutputIterator's value_type.

  • OutputIterator – is a model of Output Iterator, and if x and y are objects of OutputIterator's value_type, then x + y is defined. If T is OutputIterator's value_type, then T(0) is defined.

Returns:

The end of the output sequence.

Pre:

first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

template<typename DerivedPolicy, typename InputIterator, typename OutputIterator, typename AssociativeOperator>
__host__ __device__ OutputIterator inclusive_scan(const thrust::detail::execution_policy_base<DerivedPolicy> &exec, InputIterator first, InputIterator last, OutputIterator result, AssociativeOperator binary_op)#

inclusive_scan computes an inclusive prefix sum operation. The term ‘inclusive’ means that each result includes the corresponding input operand in the partial sum. When the input and output sequences are the same, the scan is performed in-place.

inclusive_scan is similar to std::partial_sum in the STL. The primary difference between the two functions is that std::partial_sum guarantees a serial summation order, while inclusive_scan requires associativity of the binary operation to parallelize the prefix sum.

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 to compute an in-place prefix sum using the thrust::host execution policy for parallelization:

int data[10] = {-5, 0, 2, -3, 2, 4, 0, -1, 2, 8};

thrust::maximum<int> binary_op;

thrust::inclusive_scan(thrust::host, data, data + 10, data, binary_op); // in-place scan

// data is now {-5, 0, 2, 2, 2, 4, 4, 4, 4, 8}

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

  • first – The beginning of the input sequence.

  • last – The end of the input sequence.

  • result – The beginning of the output sequence.

  • binary_op – The associatve operator used to ‘sum’ values.

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

  • InputIterator – is a model of Input Iterator and InputIterator's value_type is convertible to OutputIterator's value_type.

  • OutputIterator – is a model of Output Iterator and OutputIterator's value_type is convertible to both AssociativeOperator's first_argument_type and second_argument_type.

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

Returns:

The end of the output sequence.

Pre:

first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

template<typename InputIterator, typename OutputIterator, typename AssociativeOperator>
OutputIterator inclusive_scan(InputIterator first, InputIterator last, OutputIterator result, AssociativeOperator binary_op)#

inclusive_scan computes an inclusive prefix sum operation. The term ‘inclusive’ means that each result includes the corresponding input operand in the partial sum. When the input and output sequences are the same, the scan is performed in-place.

inclusive_scan is similar to std::partial_sum in the STL. The primary difference between the two functions is that std::partial_sum guarantees a serial summation order, while inclusive_scan requires associativity of the binary operation to parallelize the prefix sum.

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

int data[10] = {-5, 0, 2, -3, 2, 4, 0, -1, 2, 8};

thrust::maximum<int> binary_op;

thrust::inclusive_scan(data, data + 10, data, binary_op); // in-place scan

// data is now {-5, 0, 2, 2, 2, 4, 4, 4, 4, 8}

Parameters:
  • first – The beginning of the input sequence.

  • last – The end of the input sequence.

  • result – The beginning of the output sequence.

  • binary_op – The associatve operator used to ‘sum’ values.

Template Parameters:
  • InputIterator – is a model of Input Iterator and InputIterator's value_type is convertible to OutputIterator's value_type.

  • OutputIterator – is a model of Output Iterator and OutputIterator's value_type is convertible to both AssociativeOperator's first_argument_type and second_argument_type.

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

Returns:

The end of the output sequence.

Pre:

first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

template<typename DerivedPolicy, typename InputIterator, typename OutputIterator>
__host__ __device__ OutputIterator exclusive_scan(const thrust::detail::execution_policy_base<DerivedPolicy> &exec, InputIterator first, InputIterator last, OutputIterator result)#

exclusive_scan computes an exclusive prefix sum operation. The term ‘exclusive’ means that each result does not include the corresponding input operand in the partial sum. More precisely, 0 is assigned to *result and the sum of 0 and *first is assigned to *(result + 1), and so on. This version of exclusive_scan assumes plus as the associative operator and 0 as the initial value. 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 to compute an in-place prefix sum using the thrust::host execution policy for parallelization:

#include <thrust/scan.h>
#include <thrust/execution_policy.h>
...

int data[6] = {1, 0, 2, 2, 1, 3};

thrust::exclusive_scan(thrust::host, data, data + 6, data); // in-place scan

// data is now {0, 1, 1, 3, 5, 6}

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

  • first – The beginning of the input sequence.

  • last – The end of the input sequence.

  • result – The beginning of the output sequence.

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

  • InputIterator – is a model of Input Iterator and InputIterator's value_type is convertible to OutputIterator's value_type.

  • OutputIterator – is a model of Output Iterator, and if x and y are objects of OutputIterator's value_type, then x + y is defined. If T is OutputIterator's value_type, then T(0) is defined.

Returns:

The end of the output sequence.

Pre:

first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

template<typename InputIterator, typename OutputIterator>
OutputIterator exclusive_scan(InputIterator first, InputIterator last, OutputIterator result)#

exclusive_scan computes an exclusive prefix sum operation. The term ‘exclusive’ means that each result does not include the corresponding input operand in the partial sum. More precisely, 0 is assigned to *result and the sum of 0 and *first is assigned to *(result + 1), and so on. This version of exclusive_scan assumes plus as the associative operator and 0 as the initial value. 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

#include <thrust/scan.h>

int data[6] = {1, 0, 2, 2, 1, 3};

thrust::exclusive_scan(data, data + 6, data); // in-place scan

// data is now {0, 1, 1, 3, 5, 6}

Parameters:
  • first – The beginning of the input sequence.

  • last – The end of the input sequence.

  • result – The beginning of the output sequence.

Template Parameters:
  • InputIterator – is a model of Input Iterator and InputIterator's value_type is convertible to OutputIterator's value_type.

  • OutputIterator – is a model of Output Iterator, and if x and y are objects of OutputIterator's value_type, then x + y is defined. If T is OutputIterator's value_type, then T(0) is defined.

Returns:

The end of the output sequence.

Pre:

first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

template<typename DerivedPolicy, typename InputIterator, typename OutputIterator, typename T>
__host__ __device__ OutputIterator exclusive_scan(const thrust::detail::execution_policy_base<DerivedPolicy> &exec, InputIterator first, InputIterator last, OutputIterator result, T init)#

exclusive_scan computes an exclusive prefix sum operation. The term ‘exclusive’ means that each result does not include the corresponding input operand in the partial sum. More precisely, init is assigned to *result and the sum of init and *first is assigned to *(result + 1), and so on. This version of exclusive_scan assumes plus as the associative operator but requires an initial value init. 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 to compute an in-place prefix sum using the thrust::host execution policy for parallelization:

#include <thrust/scan.h>
#include <thrust/execution_policy.h>

int data[6] = {1, 0, 2, 2, 1, 3};

thrust::exclusive_scan(thrust::host, data, data + 6, data, 4); // in-place scan

// data is now {4, 5, 5, 7, 9, 10}

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

  • first – The beginning of the input sequence.

  • last – The end of the input sequence.

  • result – The beginning of the output sequence.

  • init – The initial value.

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

  • InputIterator – is a model of Input Iterator and InputIterator's value_type is convertible to OutputIterator's value_type.

  • OutputIterator – is a model of Output Iterator, and if x and y are objects of OutputIterator's value_type, then x + y is defined.

  • T – is convertible to OutputIterator's value_type.

Returns:

The end of the output sequence.

Pre:

first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

template<typename InputIterator, typename OutputIterator, typename T>
OutputIterator exclusive_scan(InputIterator first, InputIterator last, OutputIterator result, T init)#

exclusive_scan computes an exclusive prefix sum operation. The term ‘exclusive’ means that each result does not include the corresponding input operand in the partial sum. More precisely, init is assigned to *result and the sum of init and *first is assigned to *(result + 1), and so on. This version of exclusive_scan assumes plus as the associative operator but requires an initial value init. 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

#include <thrust/scan.h>

int data[6] = {1, 0, 2, 2, 1, 3};

thrust::exclusive_scan(data, data + 6, data, 4); // in-place scan

// data is now {4, 5, 5, 7, 9, 10}

Parameters:
  • first – The beginning of the input sequence.

  • last – The end of the input sequence.

  • result – The beginning of the output sequence.

  • init – The initial value.

Template Parameters:
  • InputIterator – is a model of Input Iterator and InputIterator's value_type is convertible to OutputIterator's value_type.

  • OutputIterator – is a model of Output Iterator, and if x and y are objects of OutputIterator's value_type, then x + y is defined.

  • T – is convertible to OutputIterator's value_type.

Returns:

The end of the output sequence.

Pre:

first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

template<typename DerivedPolicy, typename InputIterator, typename OutputIterator, typename T, typename AssociativeOperator>
__host__ __device__ OutputIterator exclusive_scan(const thrust::detail::execution_policy_base<DerivedPolicy> &exec, InputIterator first, InputIterator last, OutputIterator result, T init, AssociativeOperator binary_op)#

exclusive_scan computes an exclusive prefix sum operation. The term ‘exclusive’ means that each result does not include the corresponding input operand in the partial sum. More precisely, init is assigned to *result and the value binary_op(init, *first) is assigned to *(result + 1), and so on. This version of the function requires both an associative operator and an initial value init. 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 to compute an in-place prefix sum using the thrust::host execution policy for parallelization:

#include <thrust/scan.h>
#include <thrust/functional.h>
#include <thrust/execution_policy.h>
...

int data[10] = {-5, 0, 2, -3, 2, 4, 0, -1, 2, 8};

thrust::maximum<int> binary_op;

thrust::exclusive_scan(thrust::host, data, data + 10, data, 1, binary_op); // in-place scan

// data is now {1, 1, 1, 2, 2, 2, 4, 4, 4, 4 }

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

  • first – The beginning of the input sequence.

  • last – The end of the input sequence.

  • result – The beginning of the output sequence.

  • init – The initial value.

  • binary_op – The associatve operator used to ‘sum’ values.

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

  • InputIterator – is a model of Input Iterator and InputIterator's value_type is convertible to OutputIterator's value_type.

  • OutputIterator – is a model of Output Iterator and OutputIterator's value_type is convertible to both AssociativeOperator's first_argument_type and second_argument_type.

  • T – is convertible to OutputIterator's value_type.

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

Returns:

The end of the output sequence.

Pre:

first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

template<typename InputIterator, typename OutputIterator, typename T, typename AssociativeOperator>
OutputIterator exclusive_scan(InputIterator first, InputIterator last, OutputIterator result, T init, AssociativeOperator binary_op)#

exclusive_scan computes an exclusive prefix sum operation. The term ‘exclusive’ means that each result does not include the corresponding input operand in the partial sum. More precisely, init is assigned to *result and the value binary_op(init, *first) is assigned to *(result + 1), and so on. This version of the function requires both an associative operator and an initial value init. 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

#include <thrust/scan.h>
#include <thrust/functional.h>

int data[10] = {-5, 0, 2, -3, 2, 4, 0, -1, 2, 8};

thrust::maximum<int> binary_op;

thrust::exclusive_scan(data, data + 10, data, 1, binary_op); // in-place scan

// data is now {1, 1, 1, 2, 2, 2, 4, 4, 4, 4 }

Parameters:
  • first – The beginning of the input sequence.

  • last – The end of the input sequence.

  • result – The beginning of the output sequence.

  • init – The initial value.

  • binary_op – The associatve operator used to ‘sum’ values.

Template Parameters:
  • InputIterator – is a model of Input Iterator and InputIterator's value_type is convertible to OutputIterator's value_type.

  • OutputIterator – is a model of Output Iterator and OutputIterator's value_type is convertible to both AssociativeOperator's first_argument_type and second_argument_type.

  • T – is convertible to OutputIterator's value_type.

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

Returns:

The end of the output sequence.

Pre:

first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

Functions

template<typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator>
__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};

See also

inclusive_scan

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.

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

  • InputIterator1 – is a model of Input Iterator

  • InputIterator2 – is a model of Input Iterator and InputIterator2's value_type is convertible to OutputIterator's value_type.

  • OutputIterator – is a model of Output Iterator, and if x and y are objects of OutputIterator's value_type, then binary_op(x,y) is defined.

Returns:

The end of the output sequence.

Pre:

first1 may equal result but the range [first1, last1) and the range [result, result + (last1 - first1)) shall not overlap otherwise.

Pre:

first2 may equal result but the range [first2, first2 + (last1 - first1) and range [result, result + (last1 - first1)) shall not overlap otherwise.

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

See also

inclusive_scan

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.

Template Parameters:
  • InputIterator1 – is a model of Input Iterator

  • InputIterator2 – is a model of Input Iterator and InputIterator2's value_type is convertible to OutputIterator's value_type.

  • OutputIterator – is a model of Output Iterator, and if x and y are objects of OutputIterator's value_type, then binary_op(x,y) is defined.

Returns:

The end of the output sequence.

Pre:

first1 may equal result but the range [first1, last1) and the range [result, result + (last1 - first1)) shall not overlap otherwise.

Pre:

first2 may equal result but the range [first2, first2 + (last1 - first1) and range [result, result + (last1 - first1)) shall not overlap otherwise.

template<typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator, typename BinaryPredicate>
__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};

See also

inclusive_scan

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.

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

  • InputIterator1 – is a model of Input Iterator

  • InputIterator2 – is a model of Input Iterator and InputIterator2's value_type is convertible to OutputIterator's value_type.

  • OutputIterator – is a model of Output Iterator, and if x and y are objects of OutputIterator's value_type, then binary_op(x,y) is defined.

  • BinaryPredicate – is a model of Binary Predicate.

Returns:

The end of the output sequence.

Pre:

first1 may equal result but the range [first1, last1) and the range [result, result + (last1 - first1)) shall not overlap otherwise.

Pre:

first2 may equal result but the range [first2, first2 + (last1 - first1) and range [result, result + (last1 - first1)) shall not overlap otherwise.

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

See also

inclusive_scan

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.

Template Parameters:
  • InputIterator1 – is a model of Input Iterator

  • InputIterator2 – is a model of Input Iterator and InputIterator2's value_type is convertible to OutputIterator's value_type.

  • OutputIterator – is a model of Output Iterator, and if x and y are objects of OutputIterator's value_type, then binary_op(x,y) is defined.

  • BinaryPredicate – is a model of Binary Predicate.

Returns:

The end of the output sequence.

Pre:

first1 may equal result but the range [first1, last1) and the range [result, result + (last1 - first1)) shall not overlap otherwise.

Pre:

first2 may equal result but the range [first2, first2 + (last1 - first1) and range [result, result + (last1 - first1)) shall not overlap otherwise.

template<typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator, typename BinaryPredicate, typename AssociativeOperator>
__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};

See also

inclusive_scan

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.

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

  • InputIterator1 – is a model of Input Iterator

  • InputIterator2 – is a model of Input Iterator and InputIterator2's value_type is convertible to OutputIterator's value_type.

  • OutputIterator – is a model of Output Iterator, and if x and y are objects of OutputIterator's value_type, then binary_op(x,y) is defined.

  • BinaryPredicate – is a model of Binary Predicate.

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

Returns:

The end of the output sequence.

Pre:

first1 may equal result but the range [first1, last1) and the range [result, result + (last1 - first1)) shall not overlap otherwise.

Pre:

first2 may equal result but the range [first2, first2 + (last1 - first1) and range [result, result + (last1 - first1)) shall not overlap otherwise.

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

See also

inclusive_scan

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.

Template Parameters:
  • InputIterator1 – is a model of Input Iterator

  • InputIterator2 – is a model of Input Iterator and InputIterator2's value_type is convertible to OutputIterator's value_type.

  • OutputIterator – is a model of Output Iterator, and if x and y are objects of OutputIterator's value_type, then binary_op(x,y) is defined.

  • BinaryPredicate – is a model of Binary Predicate.

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

Returns:

The end of the output sequence.

Pre:

first1 may equal result but the range [first1, last1) and the range [result, result + (last1 - first1)) shall not overlap otherwise.

Pre:

first2 may equal result but the range [first2, first2 + (last1 - first1) and range [result, result + (last1 - first1)) shall not overlap otherwise.

template<typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator>
__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};

See also

exclusive_scan

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.

Pre:

first1 may equal result but the range [first1, last1) and the range [result, result + (last1 - first1)) shall not overlap otherwise.

Pre:

first2 may equal result but the range [first2, first2 + (last1 - first1) and range [result, result + (last1 - first1)) shall not overlap otherwise.

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

See also

exclusive_scan

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.

Pre:

first1 may equal result but the range [first1, last1) and the range [result, result + (last1 - first1)) shall not overlap otherwise.

Pre:

first2 may equal result but the range [first2, first2 + (last1 - first1) and range [result, result + (last1 - first1)) shall not overlap otherwise.

template<typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator, typename T>
__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};

See also

exclusive_scan

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.

Returns:

The end of the output sequence.

Pre:

first1 may equal result but the range [first1, last1) and the range [result, result + (last1 - first1)) shall not overlap otherwise.

Pre:

first2 may equal result but the range [first2, first2 + (last1 - first1) and range [result, result + (last1 - first1)) shall not overlap otherwise.

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

See also

exclusive_scan

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.

Returns:

The end of the output sequence.

Pre:

first1 may equal result but the range [first1, last1) and the range [result, result + (last1 - first1)) shall not overlap otherwise.

Pre:

first2 may equal result but the range [first2, first2 + (last1 - first1) and range [result, result + (last1 - first1)) shall not overlap otherwise.

template<typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator, typename T, typename BinaryPredicate>
__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};

See also

exclusive_scan

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.

Returns:

The end of the output sequence.

Pre:

first1 may equal result but the range [first1, last1) and the range [result, result + (last1 - first1)) shall not overlap otherwise.

Pre:

first2 may equal result but the range [first2, first2 + (last1 - first1) and range [result, result + (last1 - first1)) shall not overlap otherwise.

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

See also

exclusive_scan

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.

Returns:

The end of the output sequence.

Pre:

first1 may equal result but the range [first1, last1) and the range [result, result + (last1 - first1)) shall not overlap otherwise.

Pre:

first2 may equal result but the range [first2, first2 + (last1 - first1) and range [result, result + (last1 - first1)) shall not overlap otherwise.

template<typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename OutputIterator, typename T, typename BinaryPredicate, typename AssociativeOperator>
__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};

See also

exclusive_scan

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.

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

  • InputIterator1 – is a model of Input Iterator

  • InputIterator2 – is a model of Input Iterator and InputIterator2's value_type is convertible to OutputIterator's value_type.

  • OutputIterator – is a model of Output Iterator, and if x and y are objects of OutputIterator's value_type, then binary_op(x,y) is defined.

  • T – is convertible to OutputIterator's value_type.

  • BinaryPredicate – is a model of Binary Predicate.

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

Returns:

The end of the output sequence.

Pre:

first1 may equal result but the range [first1, last1) and the range [result, result + (last1 - first1)) shall not overlap otherwise.

Pre:

first2 may equal result but the range [first2, first2 + (last1 - first1) and range [result, result + (last1 - first1)) shall not overlap otherwise.

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

See also

exclusive_scan

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.

Template Parameters:
  • InputIterator1 – is a model of Input Iterator

  • InputIterator2 – is a model of Input Iterator and InputIterator2's value_type is convertible to OutputIterator's value_type.

  • OutputIterator – is a model of Output Iterator, and if x and y are objects of OutputIterator's value_type, then binary_op(x,y) is defined.

  • T – is convertible to OutputIterator's value_type.

  • BinaryPredicate – is a model of Binary Predicate.

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

Returns:

The end of the output sequence.

Pre:

first1 may equal result but the range [first1, last1) and the range [result, result + (last1 - first1)) shall not overlap otherwise.

Pre:

first2 may equal result but the range [first2, first2 + (last1 - first1) and range [result, result + (last1 - first1)) shall not overlap otherwise.

Functions

template<typename DerivedPolicy, typename InputIterator, typename OutputIterator, typename UnaryFunction, typename AssociativeOperator>
__host__ __device__ OutputIterator transform_inclusive_scan(const thrust::detail::execution_policy_base<DerivedPolicy> &exec, InputIterator first, InputIterator last, OutputIterator result, UnaryFunction unary_op, AssociativeOperator binary_op)#

transform_inclusive_scan fuses the transform and inclusive_scan operations. transform_inclusive_scan is equivalent to performing a tranformation defined by unary_op into a temporary sequence and then performing an inclusive_scan on the tranformed sequence. In most cases, fusing these two operations together is more efficient, since fewer memory reads and writes are required. In transform_inclusive_scan, unary_op(*first) is assigned to *result and the result of binary_op(unary_op(*first), unary_op(*(first + 1))) is assigned to *(result + 1), and so on. The transform scan operation is permitted to be in-place.

Results from this function may vary from run to run depending on the inputs provided.

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

The following code snippet demonstrates how to use transform_inclusive_scan using the thrust::host execution policy for parallelization:

#include <thrust/transform_scan.h>
#include <thrust/execution_policy.h>
...

int data[6] = {1, 0, 2, 2, 1, 3};

thrust::negate<int> unary_op;
thrust::plus<int> binary_op;

thrust::transform_inclusive_scan(thrust::host, data, data + 6, data, unary_op, binary_op); // in-place scan

// data is now {-1, -1, -3, -5, -6, -9}

See also

transform

See also

inclusive_scan

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

  • first – The beginning of the input sequence.

  • last – The end of the input sequence.

  • result – The beginning of the output sequence.

  • unary_op – The function used to tranform the input sequence.

  • binary_op – The associatve operator used to ‘sum’ transformed values.

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

  • InputIterator – is a model of Input Iterator and InputIterator's value_type is convertible to unary_op's input type.

  • OutputIterator – is a model of Output Iterator.

  • UnaryFunction – is a model of Unary Function and accepts inputs of InputIterator's value_type. UnaryFunction's result_type is convertable to OutputIterator's value_type.

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

Returns:

The end of the output sequence.

Pre:

first may equal result, but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

template<typename InputIterator, typename OutputIterator, typename UnaryFunction, typename AssociativeOperator>
OutputIterator transform_inclusive_scan(InputIterator first, InputIterator last, OutputIterator result, UnaryFunction unary_op, AssociativeOperator binary_op)#

transform_inclusive_scan fuses the transform and inclusive_scan operations. transform_inclusive_scan is equivalent to performing a tranformation defined by unary_op into a temporary sequence and then performing an inclusive_scan on the tranformed sequence. In most cases, fusing these two operations together is more efficient, since fewer memory reads and writes are required. In transform_inclusive_scan, unary_op(*first) is assigned to *result and the result of binary_op(unary_op(*first), unary_op(*(first + 1))) is assigned to *(result + 1), and so on. The transform scan operation is permitted to be in-place.

Results from this function may vary from run to run depending on the inputs provided.

The following code snippet demonstrates how to use transform_inclusive_scan

#include <thrust/transform_scan.h>

int data[6] = {1, 0, 2, 2, 1, 3};

thrust::negate<int> unary_op;
thrust::plus<int> binary_op;

thrust::transform_inclusive_scan(data, data + 6, data, unary_op, binary_op); // in-place scan

// data is now {-1, -1, -3, -5, -6, -9}

See also

transform

See also

inclusive_scan

Parameters:
  • first – The beginning of the input sequence.

  • last – The end of the input sequence.

  • result – The beginning of the output sequence.

  • unary_op – The function used to tranform the input sequence.

  • binary_op – The associatve operator used to ‘sum’ transformed values.

Template Parameters:
  • InputIterator – is a model of Input Iterator and InputIterator's value_type is convertible to unary_op's input type.

  • OutputIterator – is a model of Output Iterator.

  • UnaryFunction – is a model of Unary Function and accepts inputs of InputIterator's value_type. UnaryFunction's result_type is convertable to OutputIterator's value_type.

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

Returns:

The end of the output sequence.

Pre:

first may equal result, but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

template<typename DerivedPolicy, typename InputIterator, typename OutputIterator, typename UnaryFunction, typename T, typename AssociativeOperator>
__host__ __device__ OutputIterator transform_exclusive_scan(const thrust::detail::execution_policy_base<DerivedPolicy> &exec, InputIterator first, InputIterator last, OutputIterator result, UnaryFunction unary_op, T init, AssociativeOperator binary_op)#

transform_exclusive_scan fuses the transform and exclusive_scan operations. transform_exclusive_scan is equivalent to performing a tranformation defined by unary_op into a temporary sequence and then performing an exclusive_scan on the tranformed sequence. In most cases, fusing these two operations together is more efficient, since fewer memory reads and writes are required. In transform_exclusive_scan, init is assigned to *result and the result of binary_op(init, unary_op(*first)) is assigned to *(result + 1), and so on. The transform scan operation is permitted to be in-place.

Results from this function may vary from run to run depending on the inputs provided.

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

The following code snippet demonstrates how to use transform_exclusive_scan using the thrust::host execution policy for parallelization:

#include <thrust/transform_scan.h>
#include <thrust/execution_policy.h>
...

int data[6] = {1, 0, 2, 2, 1, 3};

thrust::negate<int> unary_op;
thrust::plus<int> binary_op;

thrust::transform_exclusive_scan(thrust::host, data, data + 6, data, unary_op, 4, binary_op); // in-place scan

// data is now {4, 3, 3, 1, -1, -2}

See also

transform

See also

exclusive_scan

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

  • first – The beginning of the input sequence.

  • last – The end of the input sequence.

  • result – The beginning of the output sequence.

  • unary_op – The function used to tranform the input sequence.

  • init – The initial value of the exclusive_scan

  • binary_op – The associatve operator used to ‘sum’ transformed values.

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

  • InputIterator – is a model of Input Iterator and InputIterator's value_type