thrust::partition

Defined in thrust/partition.h

template<typename ForwardIterator, typename InputIterator, typename Predicate> ForwardIterator thrust::partition(ForwardIterator first, ForwardIterator last, InputIterator stencil, Predicate pred)

partition reorders the elements [first, last) based on the function object pred applied to a stencil range [stencil, stencil + (last - first)), such that all of the elements whose corresponding stencil element satisfies pred precede all of the elements whose corresponding stencil element fails to satisfy it. The postcondition is that, for some iterator middle in the range [first, last), pred(*stencil_i) is true for every iterator stencil_i in the range [stencil,stencil + (middle - first)) and false for every iterator stencil_i in the range [stencil + (middle - first), stencil + (last - first)). The return value of stable_partition is middle.

Note that the relative order of elements in the two reordered sequences is not necessarily the same as it was in the original sequence. A different algorithm, stable_partition, does guarantee to preserve the relative order.

The following code snippet demonstrates how to use partition to reorder a sequence so that even numbers precede odd numbers.

#include <thrust/partition.h>
...
struct is_even
{
  __host__ __device__
  bool operator()(const int &x)
  {
    return (x % 2) == 0;
  }
};
...
int A[] = {0, 1, 0, 1, 0, 1, 0, 1, 0,  1};
int S[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
const int N = sizeof(A)/sizeof(int);
thrust::partition(A, A + N, S, is_even());
// A is now {1, 1, 1, 1, 1, 0, 0, 0, 0, 0}
// S is unmodified