Place all elements in the range [ first ... last ) that cause pred to evaluate to true before all elements in the range that cause pred to evaluate to false . Return an iterator i such that all elements in the range [ first...i ) cause pred to evaluate to true and all elements in the range [ i...last ) cause pred to evaluate to false .

Declaration


  
#include <algorithm>

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

Complexity

Time complexity is O(N * log(N)), where N = ( last - first ), as pred will be evaluated N times and at most N * log(N) swaps are performed. If there is enough available memory, O(N) swaps will be performed instead.

Example <ospace/osstd/examples/stblptn0.cpp>


    #include <iostream>
#include <algorithm>

bool
less_10( int a_ )
  {
  return a_ < 10 ? 1 : 0;
  }

int numbers[ 6 ] = { 10, 5, 11, 20, 6, -2 };

void
main()
  {
  stable_partition( numbers, numbers + 6, less_10 );

  for ( int i = 0; i < 6; ++i )
    cout << numbers[ i ] << ` `;
  cout << "\n";
  }

5 6 -2 10 11 20

Example <ospace/osstd/examples/stblptn1.cpp>


    #include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <functional>
#include <iterator>
#include <vector>

void
main()
  {
  vector< int > v1( 10 );
  for ( int i = 0; i < v1.size(); ++i )
    v1[ i ] = rand() % 20;
  ostream_iterator< int > iter( cout, " " );
  copy( v1.begin(), v1.end(), iter );
  cout << "\n";

  stable_partition( v1.begin(), v1.end(), bind2nd( less< int >(), 11 ) );

  copy( v1.begin(), v1.end(), iter );
  cout << "\n";
  }

6 10 2 10 16 17 15 15 8 6
6 10 2 10 8 6 16 17 15 15

stable_partition

Library

Declaration

Complexity

Example <ospace/osstd/examples/stblptn0.cpp>

Example <ospace/osstd/examples/stblptn1.cpp>