stable_partition function template — Partitions a range in stable order
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.
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.