partition function template — Partitions a range according to a predicate


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;
Partitioning a range into even and odd numbers
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.

Get C++ In a Nutshell now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.