Template Function thrust::merge_by_key(InputIterator1, InputIterator1, InputIterator2, InputIterator2, InputIterator3, InputIterator4, OutputIterator1, OutputIterator2, StrictWeakCompare)

Function Documentation

template<typename InputIterator1, typename InputIterator2, typename InputIterator3, typename InputIterator4, typename OutputIterator1, typename OutputIterator2, typename StrictWeakCompare>
thrust::pair<OutputIterator1, OutputIterator2> thrust::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.
Return

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.

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.

#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

merge

See

sort_by_key

See

is_sorted