stable_partition

stable_partition

template<class FwdIt, class Pred>
    FwdIt stable_partition(FwdIt first, FwdIt 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. It does so without altering the relative order of either the elements designated by indexes in the range [0, K) or the elements designated by indexes in the range [K, last - first). 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 at most ceil((last - first) * log(last - first)) pairs of elements. (Given enough temporary storage, it can replace the swaps with 2 * (last - first) assignments, at most.)