Note
Access to this page requires authorization. You can try signing in or changing directories.
Access to this page requires authorization. You can try changing directories.
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.)