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.