std::stable_partition

template <class BidirectionalIterator, class UnaryPredicate>  BidirectionalIterator stable_partition (BidirectionalIterator first,                                          BidirectionalIterator last,                                          UnaryPredicate pred);

Partition range in two - stable ordering

Rearranges the elements in the range[first,last), in such a way that all the elements for whichpred returnstrue precede all those for which it returnsfalse, and, unlike functionpartition, the relative order of elements within each group is preserved.

This is generally implemented using an internal temporary buffer.

Parameters

first, last: Bidirectional iterators to the initial and final positions of the sequence to partition. The range used is[first,last), which contains all the elements betweenfirst andlast, including the element pointed byfirst but not the element pointed bylast.
BidirectionalIterator shall point to a type for whichswap is defined (and swaps the value of its arguments) and which is bothmove-constructible andmove-assignable.
pred: Unary function that accepts an element in the range as argument, and returns a value convertible tobool. The value returned indicates whether the element is to be placed before (iftrue, it is placed before all the elements for which it returnsfalse).
The function shall not modify its argument.
This can either be a function pointer or a function object.

Return value

An iterator that points to the first element of the second group of elements (those for whichpred returnsfalse), orlast if this group is empty.

Example

// stable_partition example#include <iostream>// std::cout#include <algorithm>// std::stable_partition#include <vector>// std::vectorbool IsOdd (int i) {return (i%2)==1; }int main () {  std::vector<int> myvector;// set some values:for (int i=1; i<10; ++i) myvector.push_back(i);// 1 2 3 4 5 6 7 8 9  std::vector<int>::iterator bound;  bound = std::stable_partition (myvector.begin(), myvector.end(), IsOdd);// print out content:  std::cout <<"odd elements:";for (std::vector<int>::iterator it=myvector.begin(); it!=bound; ++it)    std::cout <<' ' << *it;  std::cout <<'\n';  std::cout <<"even elements:";for (std::vector<int>::iterator it=bound; it!=myvector.end(); ++it)    std::cout <<' ' << *it;  std::cout <<'\n';return 0;}

Output:

odd elements: 1 3 5 7 9even elements: 2 4 6 8

Complexity

If enough extra memory is available, linear in thedistance betweenfirst andlast: Appliespred exactly once to each element, and performs up to that many element moves.
Otherwise, up to linearithmic: Performs up toN*log(N) element swaps (whereN is the distance above). It also appliespred exactly once to each element.

Data races

The objects in the range[first,last) are modified.

Exceptions

Throws if any of the element comparisons, the element swaps (or moves) or the operations on iterators throws.
Note that invalid arguments causeundefined behavior.

Movatterモバイル変換

C++

Reference

C library:

Containers:

Input/Output:

Multi-threading:

Other:

<algorithm>