C++ In a Nutshell

Name

partition function template — Partitions a range according to a predicate

Synopsis

template<typename BidiIter, typename Predicate>
  BidiIter partition(BidiIter first, BidiIter last, Predicate pred);

The partition function template swaps elements in the range [first, last) so that all elements that satisfy pred come before those that do not. The relative order of elements is not preserved.

The return value is an iterator that points to the first element for which pred is false, or last if there is no such element.

Figure 13-12 illustrates the partition function template for a predicate that tests whether a number is even:

function iseven(int n)
{
  return n % 2 == 0;
}

Figure 13-12. Partitioning a range into even and odd numbers

Technical Notes

Postcondition: Let r be an iterator in the range [first, last] such that pred(*i) is true for all i in [first, r), and pred(*j) is false for all j in [r, last).

The partition function template returns r.

Complexity is linear: pred is called exactly last - first times, and at most (last - first) / 2 swaps are performed.

See Also

nth_element function template, partial_sort function template, sort function template, stable_partition function template