thrust

◆ set_intersection_by_key() [1/4]

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

set_intersection_by_key performs a key-value intersection operation from set theory. set_intersection_by_key constructs a sorted range that is the intersection 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_intersection_by_key performs the "intersection" operation from set theory: the keys output range contains a copy of every element that is contained in both [keys_first1, keys_last1) [keys_first2, keys_last2). The general case is more complicated, because the input ranges may contain duplicate elements. The generalization is that if an element appears m times in [keys_first1, keys_last1) and n times in [keys_first2, keys_last2) (where m may be zero), then it appears min(m,n) times in the keys output range. set_intersection_by_key is stable, meaning both that elements are copied from the first input range rather than the second, and that the relative order of elements in the output range is the same as the first input range.

Each time a key element is copied from [keys_first1, keys_last1) to the keys output range, the corresponding value element is copied from [values_first1, values_last1) to the values output range.

This version of set_intersection_by_key compares objects 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.
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.
Note
Unlike the other key-value set operations, set_intersection_by_key is unique in that it has no values_first2 parameter because elements from the second input range are never copied to the output range.
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.
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_intersection_by_key to compute the set intersection of two sets of integers sorted in ascending order with their values using the thrust::host execution policy for parallelization:

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