partition

template<class BidIt, class Pred>
    BidIt partition(BidIt first, BidIt last, Pred pr);

The template function reorders the sequence designated by iterators in the range [first, last) and determines the value K such that for each N in the range [0, K), the predicate pr(*(first + N)) is true, and for each N in the range [K, last - first), the predicate pr(*(first + N)) is false. The function then returns first + K.

The predicate must not alter its operand. The function evaluates pr(*(first + N)) exactly last - first times, and swaps (last - first) / 2 pairs of elements, at most.

See the related sample program.