Node:Partitions, Previous:Random shuffle, Up:Mutating sequence operations


Partitions

BidirectionalIterator partition (BidirectionalIterator first, BidirectionalIterator last, Predicate pred) Function 

template 
BidirectionalIterator partition(BidirectionalIterator first,
                                BidirectionalIterator last, Predicate pred);

partition places all the elements in the range [first, last) that satisfy pred before all the elements that do not satisfy it. It returns an iterator i such that for any iterator j in the range [first, i), pred(*j) == true, and for any iterator k in the range [i, last), pred(*j) == false. It does at most (last - first)/ 2 swaps. Exactly last - first applications of the predicate is done.

BidirectionalIterator stable_partition (BidirectionalIterator first, BidirectionalIterator last, Predicate pred) Function 

template 
BidirectionalIterator stable_partition(BidirectionalIterator first,
                                       BidirectionalIterator last,
                                       Predicate pred);

stable_partition places all the elements in the range [first, last) that satisfy pred before all the elements that do not satisfy it. It returns an iterator i such that for any iterator j in the range [first, i), pred(*j) == true, and for any iterator k in the range [i, last), pred(*j) == false. The relative order of the elements in both groups is preserved. It does at most (last - first) * log(last - first) swaps, but only linear number of swaps if there is enough extra memory. Exactly last - first applications of the predicate are done.