thrust::set_intersection_by_key

Defined in thrust/set_operations.h

template<typename DerivedPolicy, typename InputIterator1, typename InputIterator2, typename InputIterator3, typename OutputIterator1, typename OutputIterator2, typename StrictWeakCompare>
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, StrictWeakCompare comp)

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 a function object comp.

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

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

 #include <thrust/set_operations.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 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, thrust::greater<int>());

 // keys_result is now {5, 3, 1}
 // vals_result is now {0, 0, 0}

See also

set_union_by_key

See also

set_difference_by_key

See also

set_symmetric_difference_by_key

See also

sort_by_key

See also

is_sorted

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.

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.

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

  • values_result – The beginning of the 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 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 convertible 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 convertible 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.

  • 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.