Merging

template <typename DerivedPolicy,   typename InputIterator1,   typename InputIterator2,   typename OutputIterator> _CCCL_HOST_DEVICE OutputIterator merge(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   InputIterator1 first1,   InputIterator1 last1,   InputIterator2 first2,   InputIterator2 last2,   OutputIterator result);
template <typename InputIterator1,   typename InputIterator2,   typename OutputIterator> OutputIterator merge(InputIterator1 first1,   InputIterator1 last1,   InputIterator2 first2,   InputIterator2 last2,   OutputIterator result);
template <typename DerivedPolicy,   typename InputIterator1,   typename InputIterator2,   typename OutputIterator,   typename StrictWeakCompare> _CCCL_HOST_DEVICE OutputIterator merge(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   InputIterator1 first1,   InputIterator1 last1,   InputIterator2 first2,   InputIterator2 last2,   OutputIterator result,   StrictWeakCompare comp);
template <typename InputIterator1,   typename InputIterator2,   typename OutputIterator,   typename StrictWeakCompare> OutputIterator merge(InputIterator1 first1,   InputIterator1 last1,   InputIterator2 first2,   InputIterator2 last2,   OutputIterator result,   StrictWeakCompare comp);
template <typename DerivedPolicy,   typename InputIterator1,   typename InputIterator2,   typename InputIterator3,   typename InputIterator4,   typename OutputIterator1,   typename OutputIterator2> _CCCL_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);
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);
template <typename DerivedPolicy,   typename InputIterator1,   typename InputIterator2,   typename InputIterator3,   typename InputIterator4,   typename OutputIterator1,   typename OutputIterator2,   typename Compare> _CCCL_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);
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);

Functions

Function merge

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

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'svalue_type is a model of LessThan Comparable, the ordering on InputIterator1'svalue_type is a strict weak ordering, as defined in the LessThan Comparable requirements, and InputIterator1'svalue_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'svalue_type is a model of LessThan Comparable, the ordering on InputIterator2'svalue_type is a strict weak ordering, as defined in the LessThan Comparable requirements, and InputIterator2'svalue_type is convertable to a type in OutputIterator's set of value_types.
• OutputIterator is a model of Output Iterator.

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

Preconditions:

• The ranges [first1, last1) and [first2, last2) shall be sorted with respect to operator<.
• The resulting range shall not overlap with either input range.

Returns: The end of the output range.

See:

• https://en.cppreference.com/w/cpp/algorithm/merge
• set_union
• sort
• is_sorted

Function merge

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}

Template Parameters:

• InputIterator1 is a model of Input Iterator, InputIterator1 and InputIterator2 have the same value_type, InputIterator1'svalue_type is a model of LessThan Comparable, the ordering on InputIterator1'svalue_type is a strict weak ordering, as defined in the LessThan Comparable requirements, and InputIterator1'svalue_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'svalue_type is a model of LessThan Comparable, the ordering on InputIterator2'svalue_type is a strict weak ordering, as defined in the LessThan Comparable requirements, and InputIterator2'svalue_type is convertable to a type in OutputIterator's set of value_types.
• OutputIterator is a model of Output Iterator.

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

Preconditions:

• The ranges [first1, last1) and [first2, last2) shall be sorted with respect to operator<.
• The resulting range shall not overlap with either input range.

Returns: The end of the output range.

See:

• https://en.cppreference.com/w/cpp/algorithm/merge
• set_union
• sort
• is_sorted

Function merge

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

Template Parameters:

• DerivedPolicy The name of the derived execution policy.
• InputIterator1 is a model of Input Iterator, InputIterator1'svalue_type is convertable to StrictWeakCompare'sfirst_argument_type. and InputIterator1'svalue_type is convertable to a type in OutputIterator's set of value_types.
• InputIterator2 is a model of Input Iterator, InputIterator2'svalue_type is convertable to StrictWeakCompare'ssecond_argument_type. and InputIterator2'svalue_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.

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

Preconditions:

• The ranges [first1, last1) and [first2, last2) shall be sorted with respect to comp.
• The resulting range shall not overlap with either input range.

Returns: The end of the output range.

See:

• https://en.cppreference.com/w/cpp/algorithm/merge
• sort
• is_sorted

Function merge

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}

Template Parameters:

• InputIterator1 is a model of Input Iterator, InputIterator1'svalue_type is convertable to StrictWeakCompare'sfirst_argument_type. and InputIterator1'svalue_type is convertable to a type in OutputIterator's set of value_types.
• InputIterator2 is a model of Input Iterator, InputIterator2'svalue_type is convertable to StrictWeakCompare'ssecond_argument_type. and InputIterator2'svalue_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.

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

Preconditions:

• The ranges [first1, last1) and [first2, last2) shall be sorted with respect to comp.
• The resulting range shall not overlap with either input range.

Returns: The end of the output range.

See:

• https://en.cppreference.com/w/cpp/algorithm/merge
• sort
• is_sorted

Function merge_by_key

template <typename DerivedPolicy,   typename InputIterator1,   typename InputIterator2,   typename InputIterator3,   typename InputIterator4,   typename OutputIterator1,   typename OutputIterator2> _CCCL_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}

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'svalue_type is a model of LessThan Comparable, the ordering on InputIterator1'svalue_type is a strict weak ordering, as defined in the LessThan Comparable requirements, and InputIterator1'svalue_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'svalue_type is a model of LessThan Comparable, the ordering on InputIterator2'svalue_type is a strict weak ordering, as defined in the LessThan Comparable requirements, and InputIterator2'svalue_type is convertable to a type in OutputIterator's set of value_types.
• InputIterator3 is a model of Input Iterator, and InputIterator3'svalue_type is convertible to a type in OutputIterator2's set of value_types.
• InputIterator4 is a model of Input Iterator, and InputIterator4'svalue_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.

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

Preconditions:

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

Returns: A pairp 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.

See:

• merge
• sort_by_key
• is_sorted

Function merge_by_key

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}

Template Parameters:

• InputIterator1 is a model of Input Iterator, InputIterator1 and InputIterator2 have the same value_type, InputIterator1'svalue_type is a model of LessThan Comparable, the ordering on InputIterator1'svalue_type is a strict weak ordering, as defined in the LessThan Comparable requirements, and InputIterator1'svalue_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'svalue_type is a model of LessThan Comparable, the ordering on InputIterator2'svalue_type is a strict weak ordering, as defined in the LessThan Comparable requirements, and InputIterator2'svalue_type is convertable to a type in OutputIterator's set of value_types.
• InputIterator3 is a model of Input Iterator, and InputIterator3'svalue_type is convertible to a type in OutputIterator2's set of value_types.
• InputIterator4 is a model of Input Iterator, and InputIterator4'svalue_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.

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

Preconditions:

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

Returns: A pairp 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.

See:

• merge
• sort_by_key
• is_sorted

Function merge_by_key

template <typename DerivedPolicy,   typename InputIterator1,   typename InputIterator2,   typename InputIterator3,   typename InputIterator4,   typename OutputIterator1,   typename OutputIterator2,   typename Compare> _CCCL_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}

Template Parameters:

• DerivedPolicy The name of the derived execution policy.
• InputIterator1 is a model of Input Iterator, InputIterator1'svalue_type is convertable to StrictWeakCompare'sfirst_argument_type. and InputIterator1'svalue_type is convertable to a type in OutputIterator1's set of value_types.
• InputIterator2 is a model of Input Iterator, InputIterator2'svalue_type is convertable to StrictWeakCompare'ssecond_argument_type. and InputIterator2'svalue_type is convertable to a type in OutputIterator1's set of value_types.
• InputIterator3 is a model of Input Iterator, and InputIterator3'svalue_type is convertible to a type in OutputIterator2's set of value_types.
• InputIterator4 is a model of Input Iterator, and InputIterator4'svalue_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.

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

Preconditions:

• The ranges [keys_first1, keys_last1) and [keys_first2, keys_last2) shall be sorted with respect to comp.
• The resulting ranges shall not overlap with any input range.

Returns: A pairp 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.

See:

• merge
• sort_by_key
• is_sorted

Function merge_by_key

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}

Template Parameters:

• InputIterator1 is a model of Input Iterator, InputIterator1'svalue_type is convertable to StrictWeakCompare'sfirst_argument_type. and InputIterator1'svalue_type is convertable to a type in OutputIterator1's set of value_types.
• InputIterator2 is a model of Input Iterator, InputIterator2'svalue_type is convertable to StrictWeakCompare'ssecond_argument_type. and InputIterator2'svalue_type is convertable to a type in OutputIterator1's set of value_types.
• InputIterator3 is a model of Input Iterator, and InputIterator3'svalue_type is convertible to a type in OutputIterator2's set of value_types.
• InputIterator4 is a model of Input Iterator, and InputIterator4'svalue_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.

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

Preconditions:

• The ranges [keys_first1, keys_last1) and [keys_first2, keys_last2) shall be sorted with respect to comp.
• The resulting ranges shall not overlap with any input range.

Returns: A pairp 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.

See:

• merge
• sort_by_key
• is_sorted