The C++ Algorithm stable_partition method is employed to categorize the elements within the range [first, last) in a manner that ensures elements fulfilling the pred condition are positioned before those that do not, while maintaining the original sequence of elements.
Note: - This function is generally implemented using an internal temporary buffer.
Syntax
template <class BidirectionalIterator, class UnaryPredicate>
BidirectionalIterator stable_partition (BidirectionalIterator first,
BidirectionalIterator last,
UnaryPredicate pred);
Parameter
An iterator that moves bidirectionally and points to the initial element within the range intended for partitioning.
The last iterator points to the element before the last one in the bidirectional sequence to be divided.
A custom unary predicate function defined by the user to specify the criteria for categorizing an element.
Return value
This function provides an iterator pointing to the initial element within the range that does not meet the specified predicate condition.
Complexity
The time complexity is linear within the specified range [first, last) as long as there is sufficient memory available. This process involves applying the pred function to every element in the range.
Data races
The elements within the range [first, last) are altered.
Exceptions
This function will raise an exception if there is an error during comparisons between elements, swapping elements, or any operation involving iterators.
Please be aware that using incorrect parameters can lead to unpredictable behavior.
Example 1
Let's explore a straightforward example to showcase the functionality of stable_partition:
#include <iostream> // std::cout
#include <algorithm> // std::stable_partition
#include <vector> // std::vector
using namespace std;
bool IsOdd (int i) { return (i%2)==1; }
int main () {
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
vector<int>::iterator bound;
bound = stable_partition (myvector.begin(), myvector.end(), IsOdd);
// print out content:
cout << "odd elements:";
for (vector<int>::iterator it=myvector.begin(); it!=bound; ++it)
cout << ' ' << *it;
cout << '\n';
cout << "even elements:";
for (vector<int>::iterator it=bound; it!=myvector.end(); ++it)
cout << ' ' << *it;
cout << '\n';
return 0;
}
Output:
odd elements: 1 3 5 7 9
even elements: 2 4 6 8
In the provided example, numbers ranging from 1 to 9 are divided into sets of even and odd elements.
Example 2
Let's see another simple example:
#include <vector>
#include <algorithm>
#include <iostream>
bool greater5 ( int value ) {
return value >5;
}
int main( ) {
using namespace std;
vector <int> v1, v2;
vector <int>::iterator Iter1, Iter2, result;
int i;
for ( i = 0 ; i <= 10 ; i++ )
v1.push_back( i );
int ii;
for ( ii = 0 ; ii <= 4 ; ii++ )
v1.push_back( 5 );
random_shuffle(v1.begin( ), v1.end( ) );
cout << "Vector v1 is ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
// Partition the range with predicate greater10
result = stable_partition (v1.begin( ), v1.end( ), greater5 );
cout << "The partitioned set of elements in v1 is:\n ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
cout << "The first element in v1 to fail to satisfy the"
<< "\n predicate greater5 is: " << *result << "." << endl;
return 0;
}
Output:
Vector v1 is ( 4 10 5 5 5 5 5 1 6 9 3 7 8 2 0 5 ).
The partitioned set of elements in v1 is:
( 10 6 9 7 8 4 5 5 5 5 5 1 3 2 0 5 ).
The first element in v1 to fail to satisfy the
predicate greater5 is: 4.
Example 3
Let's explore another straightforward illustration to swiftly arrange the elements of a vector by employing the partition method:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
vector<int> v{0, 0, 3, 0, 2, 4, 5, 0, 7};
stable_partition(v.begin(), v.end(), [](int n){return n>0;});
for (int n : v) {
cout << n << ' ';
}
cout << '\n';
return 0;
}
Output:
3 2 4 5 7 0 0 0 0
Example 4
Let's see another simple example:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> v = {1, 0, 3, 4, 5, 6, 12, 7, 9};
stable_partition(v.begin(), v.end(), [](int x) { return x % 3 == 0; });
for_each(v.begin(), v.end(), [](int x) {
cout << x << endl;
});
return 0;
}
Output:
0
3
6
12
9
1
4
5
7
