stable_partition


function template
<algorithm> 
template <class BidirectionalIterator, class Predicate>
  BidirectionalIterator stable_partition ( BidirectionalIterator first,
                                           BidirectionalIterator last,
                                           Predicate pred );

Partition range in two - stable ordering

Rearranges the elements in the range [first,last), in such a way that all the elements for which pred returns true precede all those for which it returns false, and, unlike function partition, grants the preservation of the relative order of elements within each group.

This is generally implemented using a temporary buffer.

Parameters

first, last
Bidirectional iterators to the initial and final positions of the sequence to be partitioned. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
pred
Unary predicate taking an element in the range as argument, and returning a value indicating the falsehood (with false, or a zero value) or truth (true, or non-zero) of some condition applied to it. This can either be a pointer to a function or an object whose class overloads operator().


Return value

An iterator that points to the first element of the second group of elements. For all the elements in this second group, pred return false.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
// stable_partition example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool IsOdd (int i) { return (i%2)==1; }

int main () {
  vector<int> myvector;
  vector<int>::iterator it, bound;

  // set some values:
  for (int i=1; i<10; ++i) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9

  bound = stable_partition (myvector.begin(), myvector.end(), IsOdd);

  // print out content:
  cout << "odd members:";
  for (it=myvector.begin(); it!=bound; ++it)
    cout << " " << *it;

  cout << "\neven members:";
  for (it=bound; it!=myvector.end(); ++it)
    cout << " " << *it;

  cout << endl;

  return 0;
}


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


Complexity

N applications of pred (where N is the number elements in the range [first,last)), plus at most, NlogN swaps, except if an internal buffer could be used, in which case only linear number of swaps.

See also

partition Partition range in two (function template)
sort Sort elements in range (function template)
reverse Reverse range (function template)
find_if Find element in range (function template)