thrust

◆ set_difference_by_key() [1/4]

template<typename DerivedPolicy , typename InputIterator1 , typename InputIterator2 , typename InputIterator3 , typename InputIterator4 , typename OutputIterator1 , typename OutputIterator2 >
__host__ __device__ thrust::pair<OutputIterator1,OutputIterator2> thrust::set_difference_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 
)

set_difference_by_key performs a key-value difference operation from set theory. set_difference_by_key constructs a sorted range that is the difference of the sorted ranges [keys_first1, keys_last1) and [keys_first2, keys_last2). Associated with each element from the input and output key ranges is a value element. The associated input value ranges need not be sorted.

In the simplest case, set_difference_by_key performs the "difference" operation from set theory: the keys output range contains a copy of every element that is contained in [keys_first1, keys_last1) and not contained in [keys_first2, keys_last2). The general case is more complicated, because the input ranges may contain duplicate elements. The generalization is that if [keys_first1, keys_last1) contains m elements that are equivalent to each other and if [keys_first2, keys_last2) contains n elements that are equivalent to them, the last max(m-n,0) elements from [keys_first1, keys_last1) range shall be copied to the output range.

Each time a key element is copied from [keys_first1, keys_last1) or [keys_first2, keys_last2) is copied to the keys output range, the corresponding value element is copied from the corresponding values input range (beginning at values_first1 or values_first2) to the values output range.

This version of set_difference_by_key compares key elements using operator<.

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

Parameters
execThe execution policy to use for parallelization.
keys_first1The beginning of the first input range of keys.
keys_last1The end of the first input range of keys.
keys_first2The beginning of the second input range of keys.
keys_last2The end of the second input range of keys.
values_first1The beginning of the first input range of values.
values_first2The beginning of the first input range of values.
keys_resultThe beginning of the output range of keys.
values_resultThe beginning of the output range of values.
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.
Template Parameters
DerivedPolicyThe name of the derived execution policy.
InputIterator1is 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.
InputIterator2is 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.
InputIterator3is a model of Input Iterator, and InputIterator3's value_type is convertible to a type in OutputIterator2's set of value_types.
InputIterator4is a model of Input Iterator, and InputIterator4's value_type is convertible to a type in OutputIterator2's set of value_types.
OutputIterator1is a model of Output Iterator.
OutputIterator2is a model of Output Iterator.
Precondition
The ranges [keys_first1, keys_last1) and [keys_first2, keys_last2) shall be sorted with respect to operator<.
The resulting ranges shall not overlap with any input range.

The following code snippet demonstrates how to use set_difference_by_key to compute the set difference of two sets of integers sorted in ascending order with their values using the thrust::host execution policy for parallelization:

...
int A_keys[6] = {0, 1, 3, 4, 5, 6, 9};
int A_vals[6] = {0, 0, 0, 0, 0, 0, 0};
int B_keys[5] = {1, 3, 5, 7, 9};
int B_vals[5] = {1, 1, 1, 1, 1};
int keys_result[3];
int vals_result[3];
thrust::pair<int*,int*> end = thrust::set_difference_by_key(thrust::host, A_keys, A_keys + 6, B_keys, B_keys + 5, A_vals, B_vals, keys_result, vals_result);
// keys_result is now {0, 4, 6}
// vals_result is now {0, 0, 0}
See also
set_union_by_key
set_intersection_by_key
set_symmetric_difference_by_key
sort_by_key
is_sorted