Name

stable_partition function template — Partitions a range in stable order

Synopsis

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

The stable_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 in each partition is 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 (under partition) illustrates the partition functionality.

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 stable_partition function template returns r.

Complexity is linear if there is enough memory. Otherwise, at most n log n swaps are performed, in which n = last - first. In all cases, pred is called exactly n times.

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

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.