Set Operations

Functions
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator >
OutputIterator	thrust::set_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename StrictWeakCompare >
OutputIterator	thrust::set_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakCompare comp)
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator >
OutputIterator	thrust::set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename StrictWeakCompare >
OutputIterator	thrust::set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakCompare comp)
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator >
OutputIterator	thrust::set_symmetric_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename StrictWeakCompare >
OutputIterator	thrust::set_symmetric_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakCompare comp)
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator >
OutputIterator	thrust::set_union (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename StrictWeakCompare >
OutputIterator	thrust::set_union (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakCompare comp)

---

Function Documentation

template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator >

OutputIterator thrust::set_difference	(	InputIterator1	first1,
		InputIterator1	last1,
		InputIterator2	first2,
		InputIterator2	last2,
		OutputIterator	result
	)

set_difference constructs a sorted range that is the set difference of the sorted ranges [first1, last1) and [first2, last2). The return value is the end of the output range.

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

This version of set_difference compares elements using operator<.

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 output range.

Returns:

The end of the output range.

Template Parameters:

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 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'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.
OutputIterator	is a model of Output Iterator.

The following code snippet demonstrates how to use set_difference to compute the set difference of two sets of integers sorted in ascending order.

  #include <thrust/set_operations.h>
  ...
  int A1[6] = {0, 1, 3, 4, 5, 6, 9};
  int A2[5] = {1, 3, 5, 7, 9};

  int result[3];

  int *result_end = thrust::set_difference(A1, A1 + 6, A2, A2 + 5, result);
  // result is now {0, 4, 6}

See also:

http://www.sgi.com/tech/stl/set_difference.html

includes

set_union

set_intersection

set_symmetric_difference

sort

is_sorted

template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename StrictWeakCompare >

OutputIterator thrust::set_difference	(	InputIterator1	first1,
		InputIterator1	last1,
		InputIterator2	first2,
		InputIterator2	last2,
		OutputIterator	result,
		StrictWeakCompare	comp
	)

set_difference constructs a sorted range that is the set difference of the sorted ranges [first1, last1) and [first2, last2). The return value is the end of the output range.

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

This version of set_difference compares elements using a function object comp.

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 output range.
comp	Comparison operator.

Returns:

The end of the output range.

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 OutputIterator'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 OutputIterator's set of value_types.
OutputIterator	is a model of Output Iterator.
StrictWeakCompare	is a model of Strict Weak Ordering.

The following code snippet demonstrates how to use set_difference to compute the set difference of two sets of integers sorted in descending order.

  #include <thrust/set_operations.h>
  #include <thrust/functional.h>
  ...
  int A1[6] = {9, 6, 5, 4, 3, 1, 0};
  int A2[5] = {9, 7, 5, 3, 1};

  int result[3];

  int *result_end = thrust::set_difference(A1, A1 + 6, A2, A2 + 5, result, thrust::greater<int>());
  // result is now {6, 4, 0}

See also:

http://www.sgi.com/tech/stl/set_difference.html

includes

set_union

set_intersection

set_symmetric_difference

sort

is_sorted

template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename StrictWeakCompare >

OutputIterator thrust::set_intersection	(	InputIterator1	first1,
		InputIterator1	last1,
		InputIterator2	first2,
		InputIterator2	last2,
		OutputIterator	result,
		StrictWeakCompare	comp
	)

set_intersection constructs a sorted range that is the intersection of sorted ranges [first1, last1) and [first2, last2). The return value is the end of the output range.

In the simplest case, set_intersection performs the "intersection" operation from set theory: the output range contains a copy of every element that is contained in both [first1, last1) and [first2, last2). The general case is more complicated, because the input ranges may contain duplicate elements. The generalization is that if a value appears m times in [first1, last1) and n times in [first2, last2) (where m may be zero), then it appears min(m,n) times in the output range. set_intersection is stable, meaning that both elements are copied from the first range rather than the second, and that the relative order of elements in the output range is the same as in the first input range.

This version of set_intersection compares elements using a function object comp.

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 output range.
comp	Comparison operator.

Returns:

The end of the output range.

Template Parameters:

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 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'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.
OutputIterator	is a model of Output Iterator.

The following code snippet demonstrates how to use set_intersection to compute the set intersection of sets of integers sorted in descending order.

  #include <thrust/set_operations.h>
  ...
  int A1[6] = {11, 9, 7, 5, 3, 1};
  int A2[7] = {13, 8, 5, 3, 2,  1, 1};

  int result[3];

  int *result_end = thrust::set_intersection(A1, A1 + 6, A2, A2 + 7, result, thrust::greater<int>());
  // result is now {5, 3, 1}

See also:

http://www.sgi.com/tech/stl/set_intersection.html

includes

set_union

set_intersection

set_symmetric_difference

sort

is_sorted

template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator >

OutputIterator thrust::set_intersection	(	InputIterator1	first1,
		InputIterator1	last1,
		InputIterator2	first2,
		InputIterator2	last2,
		OutputIterator	result
	)

set_intersection constructs a sorted range that is the intersection of sorted ranges [first1, last1) and [first2, last2). The return value is the end of the output range.

In the simplest case, set_intersection performs the "intersection" operation from set theory: the output range contains a copy of every element that is contained in both [first1, last1) and [first2, last2). The general case is more complicated, because the input ranges may contain duplicate elements. The generalization is that if a value appears m times in [first1, last1) and n times in [first2, last2) (where m may be zero), then it appears min(m,n) times in the output range. set_intersection is stable, meaning that both elements are copied from the first range rather than the second, and that the relative order of elements in the output range is the same as in the first input range.

This version of set_intersection compares objects using operator<.

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 output range.

Returns:

The end of the output range.

Template Parameters:

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 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'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.
OutputIterator	is a model of Output Iterator.

The following code snippet demonstrates how to use set_intersection to compute the set intersection of two sets of integers sorted in ascending order.

  #include <thrust/set_operations.h>
  ...
  int A1[6] = {1, 3, 5, 7, 9, 11};
  int A2[7] = {1, 1, 2, 3, 5,  8, 13};

  int result[7];

  int *result_end = thrust::set_intersection(A1, A1 + 6, A2, A2 + 7, result);
  // result is now {1, 3, 5}

See also:

http://www.sgi.com/tech/stl/set_intersection.html

includes

set_union

set_intersection

set_symmetric_difference

sort

is_sorted

template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator >

OutputIterator thrust::set_symmetric_difference	(	InputIterator1	first1,
		InputIterator1	last1,
		InputIterator2	first2,
		InputIterator2	last2,
		OutputIterator	result
	)

set_symmetric_difference constructs a sorted range that is the set symmetric difference of the sorted ranges [first1, last1) and [first2, last2). The return value is the end of the output range.

In the simplest case, set_symmetric_difference performs a set theoretic calculation: it constructs the union of the two sets A - B and B - A, where A and B are the two input ranges. That is, the output range contains a copy of every element that is contained in [first1, last1) but not [first2, last1), and a copy of every element that is contained in [first2, last2) but not [first1, last1). The general case is more complicated, because the input ranges may contain duplicate elements. The generalization is that if [first1, last1) contains m elements that are equivalent to each other and [first2, last1) contains n elements that are equivalent to them, then |m - n| of those elements shall be copied to the output range: the last m - n elements from [first1, last1) if m > n, and the last n - m of these elements from [first2, last2) if m < n.

This version of set_union compares elements using operator<.

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 output range.

Returns:

The end of the output range.

Template Parameters:

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 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'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.
OutputIterator	is a model of Output Iterator.

The following code snippet demonstrates how to use set_symmetric_difference to compute the symmetric difference of two sets of integers sorted in ascending order.

  #include <thrust/set_operations.h>
  ...
  int A1[6] = {0, 1, 2, 2, 4, 6, 7};
  int A2[5] = {1, 1, 2, 5, 8};

  int result[6];

  int *result_end = thrust::set_symmetric_difference(A1, A1 + 6, A2, A2 + 5, result);
  // result = {0, 4, 5, 6, 7, 8}

See also:

http://www.sgi.com/tech/stl/set_symmetric_difference.html

merge

includes

set_difference

set_union

set_intersection

sort

is_sorted

template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename StrictWeakCompare >

OutputIterator thrust::set_symmetric_difference	(	InputIterator1	first1,
		InputIterator1	last1,
		InputIterator2	first2,
		InputIterator2	last2,
		OutputIterator	result,
		StrictWeakCompare	comp
	)

set_symmetric_difference constructs a sorted range that is the set symmetric difference of the sorted ranges [first1, last1) and [first2, last2). The return value is the end of the output range.

In the simplest case, set_symmetric_difference performs a set theoretic calculation: it constructs the union of the two sets A - B and B - A, where A and B are the two input ranges. That is, the output range contains a copy of every element that is contained in [first1, last1) but not [first2, last1), and a copy of every element that is contained in [first2, last2) but not [first1, last1). The general case is more complicated, because the input ranges may contain duplicate elements. The generalization is that if [first1, last1) contains m elements that are equivalent to each other and [first2, last1) contains n elements that are equivalent to them, then |m - n| of those elements shall be copied to the output range: the last m - n elements from [first1, last1) if m > n, and the last n - m of these elements from [first2, last2) if m < n.

This version of set_union compares elements using a function object comp.

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 output range.
comp	Comparison operator.

Returns:

The end of the output range.

Template Parameters:

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 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'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.
OutputIterator	is a model of Output Iterator.

The following code snippet demonstrates how to use set_symmetric_difference to compute the symmetric difference of two sets of integers sorted in descending order.

  #include <thrust/set_operations.h>
  ...
  int A1[6] = {7, 6, 4, 2, 2, 1, 0};
  int A2[5] = {8, 5, 2, 1, 1};

  int result[6];

  int *result_end = thrust::set_symmetric_difference(A1, A1 + 6, A2, A2 + 5, result);
  // result = {8, 7, 6, 5, 4, 0}

See also:

http://www.sgi.com/tech/stl/set_symmetric_difference.html

merge

includes

set_difference

set_union

set_intersection

sort

is_sorted

template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename StrictWeakCompare >

OutputIterator thrust::set_union	(	InputIterator1	first1,
		InputIterator1	last1,
		InputIterator2	first2,
		InputIterator2	last2,
		OutputIterator	result,
		StrictWeakCompare	comp
	)

set_union constructs a sorted range that is the union of the sorted ranges [first1, last1) and [first2, last2). The return value is the end of the output range.

In the simplest case, set_union performs the "union" operation from set theory: the output range contains a copy of every element that is contained in [first1, last1), [first2, last1), or both. The general case is more complicated, because the input ranges may contain duplicate elements. The generalization is that if [first1, last1) contains m elements that are equivalent to each other and if [first2, last2) contains n elements that are equivalent to them, then all m elements from the first range shall be copied to the output range, in order, and then max(n - m, 0) elements from the second range shall be copied to the output, in order.

This version of set_union compares elements using a function object comp.

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 output range.
comp	Comparison operator.

Returns:

The end of the output range.

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 OutputIterator'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 OutputIterator's set of value_types.
OutputIterator	is a model of Output Iterator.
StrictWeakCompare	is a model of Strict Weak Ordering.

The following code snippet demonstrates how to use set_union to compute the union of two sets of integers sorted in ascending order.

  #include <thrust/set_operations.h>
  #include <thrust/functional.h>
  ...
  int A1[6] = {12, 10, 8, 6, 4, 2, 12};
  int A2[5] = {9, 7, 5, 3, 1};

  int result[11];

  int *result_end = thrust::set_union(A1, A1 + 6, A2, A2 + 5, result, thrust::greater<int>());
  // result = {12, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0}

See also:

http://www.sgi.com/tech/stl/set_union.html

merge

includes

set_union

set_intersection

set_symmetric_difference

sort

is_sorted

template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator >

OutputIterator thrust::set_union	(	InputIterator1	first1,
		InputIterator1	last1,
		InputIterator2	first2,
		InputIterator2	last2,
		OutputIterator	result
	)

set_union constructs a sorted range that is the union of the sorted ranges [first1, last1) and [first2, last2). The return value is the end of the output range.

In the simplest case, set_union performs the "union" operation from set theory: the output range contains a copy of every element that is contained in [first1, last1), [first2, last1), or both. The general case is more complicated, because the input ranges may contain duplicate elements. The generalization is that if [first1, last1) contains m elements that are equivalent to each other and if [first2, last2) contains n elements that are equivalent to them, then all m elements from the first range shall be copied to the output range, in order, and then max(n - m, 0) elements from the second range shall be copied to the output, in order.

This version of set_union compares elements using operator<.

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 output range.

Returns:

The end of the output range.

Template Parameters:

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 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'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.
OutputIterator	is a model of Output Iterator.

The following code snippet demonstrates how to use set_union to compute the union of two sets of integers sorted in ascending order.

  #include <thrust/set_operations.h>
  ...
  int A1[6] = {0, 2, 4, 6, 8, 10, 12};
  int A2[5] = {1, 3, 5, 7, 9};

  int result[11];

  int *result_end = thrust::set_union(A1, A1 + 6, A2, A2 + 5, result);
  // result = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12}

See also:

http://www.sgi.com/tech/stl/set_union.html

merge

includes

set_union

set_intersection

set_symmetric_difference

sort

is_sorted