C++ Algorithm partition function is used to make partition the elements on the basis of given predicate (condition) mentioned in its arguments. If the container is partitioned then this function returns true, else 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
first : An bidirectional iterator pointing to the first element in the range to be partitioned.
last : An bidirectional iterator pointing to the past last element in the range to be partitioned.
pred : A user-defined unary predicate function that defines the condition to be satisfied if an element is to be classified.
Return value
This function returns an iterator to the first element of the range to not satisfy the predicate condition.
Complexity
Complexity is linear in the range [first, last) : Applies pred to each element, and possibly swaps some of them.
Data races
The object in the range [first, last) are modified.
Exceptions
This function throws an exception if either an element swap or an operation on iterator throws an exception.
Please note that invalid parameters cause an undefined behavior.
Example 1
Let's see the simple example to demonstrate the use of partition:
#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 above example, elements from 1 to 9 are partitioned 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 see another simple example to quick sort the elements of vector using 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