Template Function thrust::stable_partition(ForwardIterator, ForwardIterator, InputIterator, Predicate)¶

Function Documentation¶

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

stable_partition is much like partition: it reorders the elements in the range [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.

stable_partition differs from partition in that stable_partition is guaranteed to preserve relative order. That is, if x and y are elements in [first, last), such that pred(x) == pred(y), and if x precedes y, then it will still be true after stable_partition that x precedes y.

The following code snippet demonstrates how to use

stable_partition to reorder a sequence so that even numbers precede odd numbers.

Return

An iterator referring to the first element of the second partition, that is, the sequence of the elements whose stencil elements do not satisfy pred.

Pre

The range [first, last) shall not overlap with the range [stencil, stencil + (last - first)).

Parameters

first: The first element of the sequence to reorder.
last: One position past the last element of the sequence to reorder.
stencil: The beginning of the stencil sequence.
pred: A function object which decides to which partition each element of the sequence [first, last) belongs.

Template Parameters

ForwardIterator: is a model of Forward Iterator, and ForwardIterator is mutable.
InputIterator: is a model of Input Iterator, and InputIterator's value_type is convertible to Predicate's argument_type.
Predicate: is a model of Predicate.

#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::stable_partition(A, A + N, S, is_even());
// A is now {1, 1, 1, 1, 1, 0, 0, 0, 0, 0}
// S is unmodified

See: http://www.sgi.com/tech/stl/stable_partition.html
See: partition
See: stable_partition_copy