The partition function in C++ algorithms is utilized to separate elements based on a specified predicate provided in its arguments. It returns true if the container is successfully partitioned, otherwise it returns false.
Syntax
template <class BidirectionalIterator, class UnaryPredicate>
BidirectionalIterator partition (BidirectionalIterator first,
BidirectionalIterator last, UnaryPredicate pred); //until C++ 11
template <class ForwardIterator, class UnaryPredicate>
ForwardIterator partition (ForwardIterator first,
ForwardIterator last, UnaryPredicate pred); //Since C++ 11
Parameter
An iterator that moves bidirectionally and points to the initial element within the specified range for partitioning.
last : A bidirectional iterator that points to the previous last element in the specified range for partitioning.
A custom unary predicate function that specifies the criteria an element must meet to be categorized.
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 complexity increases linearly within the specified range [first, last) when the pred function is applied to each element, potentially resulting in the swapping of certain elements.
Data races
The elements within the range [first, last) undergo modifications.
Exceptions
This function will raise an exception if an error occurs during either the swapping of elements or when performing an operation on an iterator.
Please be aware that using incorrect parameters can result in undefined behavior.
Example 1
Let's examine a basic example to illustrate the functionality of the partition method:
#include <iostream> // std::cout
#include <algorithm> // std::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 = 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 9 3 7 5
even elements: 6 4 8 2
In the previous example, elements 1 through 9 are divided into 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;
int i;
for ( i = 0 ; i <= 10 ; i++ )
{
v1.push_back( i );
}
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
partition ( v1.begin( ), v1.end( ), greater5 );
cout << "The partitioned set of elements in v1 is: ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
return 0;
}
Output:
Vector v1 is ( 4 10 7 8 0 5 2 1 6 9 3 ).
The partitioned set of elements in v1 is: ( 9 10 7 8 6 5 2 1 0 4 3 ).
Example 3
Let's explore another straightforward illustration for sorting the elements of a vector rapidly by utilizing the partition function:
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <forward_list>
template <class ForwardIt>
void quicksort(ForwardIt first, ForwardIt last)
{
if(first == last) return;
auto pivot = *std::next(first, std::distance(first,last)/2);
ForwardIt middle1 = std::partition(first, last,
[pivot](const auto& em){ return em < pivot; });
ForwardIt middle2 = std::partition(middle1, last,
[pivot](const auto& em){ return !(pivot < em); });
quicksort(first, middle1);
quicksort(middle2, last);
}
int main()
{
std::vector<int> v = {0,1,2,3,4,5,6,7,8,9};
std::cout << "Original vector:\n ";
for(int elem : v) std::cout << elem << ' ';
auto it = std::partition(v.begin(), v.end(), [](int i){return i % 2 == 0;});
std::cout << "\nPartitioned vector:\n ";
std::copy(std::begin(v), it, std::ostream_iterator<int>(std::cout, " "));
std::cout << " * ";
std::copy(it, std::end(v), std::ostream_iterator<int>(std::cout, " "));
std::forward_list<int> fl = {1, 30, -4, 3, 5, -4, 1, 6, -8, 2, -5, 64, 1, 92};
std::cout << "\nUnsorted list:\n ";
for(int n : fl) std::cout << n << ' ';
std::cout << '\n';
quicksort(std::begin(fl), std::end(fl));
std::cout << "Sorted using quicksort:\n ";
for(int fi : fl) std::cout << fi << ' ';
std::cout << '\n';
return 0;
}
Output:
Original vector:
0 1 2 3 4 5 6 7 8 9
Partitioned vector:
0 8 2 6 4 * 5 3 7 1 9
Unsorted list:
1 30 -4 3 5 -4 1 6 -8 2 -5 64 1 92
Sorted using quicksort:
-8 -5 -4 -4 1 1 1 2 3 5 6 30 64 92
Example 4
Let's see another simple example:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> v = {1, 2, 3, 4, 5};
cout<<"Before Partition: ";
for_each(v.begin(), v.end(), [](int v) {
cout << v << " ";
});
auto pred = [](int x) { return x % 2 == 0; };
// Divide it into an even group and an odd group
partition(v.begin(), v.end(), pred);
cout<<"\nAfter partition: ";
for_each(v.begin(), v.end(), [](int x) {
cout << x << " ";
});
cout<<"\n\nIs it partitioned?"<<endl;
// Is it divided into an even group and an odd group?
if (is_partitioned(v.begin(), v.end(), pred)) {
cout << "Yes, it is partitioned" << endl;
}
else {
cout << "No, it is not partitioned" << endl;
}
return 0;
}
Output:
Before Partition: 1 2 3 4 5
After partition: 4 2 3 1 5
Is it partitioned?
Yes, it is partitioned
