The C++ algorithm function partition_point is employed to retrieve the initial element within the specified range where the predicate is false. The arrangement of elements ensures that those meeting the condition precede those that do not meet it.
Syntax
template <class ForwardIterator, class UnaryPredicate>
ForwardIterator partition_point (ForwardIterator first, ForwardIterator last,
UnaryPredicate pred);
Parameter
An initial forward iterator that points to the first element within the range for evaluating a specific condition.
last: An iterator positioned at the element immediately following the last element in the specified range.
pred : A custom unary predicate function created by the user that specifies the condition to be evaluated.
Return value
This function provides a forward iterator that points to the initial element that does not meet the condition evaluated by pred, or it returns the last element if such an element is not located.
Complexity
The complexity grows logarithmically within the interval [initial, final).
Data races
Some of the elements within the range [first, last) are being accessed.
Exceptions
This function will raise an exception if an error occurs during the comparison of elements or while performing an operation on an iterator.
Note: The invalid parameters cause an undefined behavior.
Example 1
Let's explore a basic example to showcase the functionality of partition_point:
#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>
using namespace std;
int main()
{
array<int, 9> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
auto is_even = [](int i)
{ return i % 2 == 0; };
partition(v.begin(), v.end(), is_even);
auto p = std::partition_point(v.begin(), v.end(), is_even);
cout << "Before partition:\n ";
copy(v.begin(), p, ostream_iterator<int>(cout, " "));
cout << "\nAfter partition:\n ";
copy(p, v.end(), ostream_iterator<int>(cout, " "));
return 0;
}
Output:
Before partition:
8 2 6 4
After partition:
5 3 7 1 9
Example 2
Let's see another simple example:
#include <iostream> // std::cout
#include <algorithm> // std::partition, std::partition_point
#include <vector> // std::vector
using namespace std;
bool IsOdd (int i) { return (i%2)==1; }
int main () {
vector<int> foo {1,2,3,4,5,6,7,8,9};
vector<int> odd;
partition (foo.begin(),foo.end(),IsOdd);
auto it = partition_point(foo.begin(),foo.end(),IsOdd);
odd.assign (foo.begin(),it);
// print contents of odd:
cout << "odd:";
for (int& x:odd) cout << ' ' << x;
cout << '\n';
return 0;
}
Output:
odd: 1 9 3 7 5
Example 3
Let's see another simple example:
#include<iostream>
#include<algorithm> // for partition algorithm
#include<vector> // for vector
using namespace std;
int main()
{
// Initializing vector
vector<int> vect = { 2, 1, 5, 6, 8, 7 };
// partitioning vector using stable_partition()
// in sorted order
stable_partition(vect.begin(), vect.end(), [](int x)
{
return x%2 == 0;
});
// Displaying partitioned Vector
cout << "The partitioned vector is : ";
for (int &x : vect) cout << x << " ";
cout << endl;
// Declaring iterator
vector<int>::iterator it1;
// using partition_point() to get ending position of partition
auto it = partition_point(vect.begin(), vect.end(), [](int x)
{
return x%2==0;
});
// Displaying partitioned Vector
cout << "The vector elements returning true for condition are : ";
for ( it1= vect.begin(); it1!=it; it1++)
cout << *it1 << " ";
cout << endl;
return 0;
}
Output:
The partitioned vector is : 2 6 8 1 5 7
The vector elements returning true for condition are : 2 6 8
Example 4
Let's see another simple example:
#include <iostream> // std::cout
#include <algorithm> // std::partition, std::partition_point
#include <vector> // std::vector
using namespace std;
bool IsNegative(int i) { return (i < 0); }
int main()
{
vector<int> data{ 1, -1, 3, -4, 5, 2, -2, 4, -5, -3 };
vector<int> negative, positive;
// partition data on the basis of odd elements using
// pred IsNegative()
stable_partition(data.begin(), data.end(), IsNegative);
// gets the partition point based on odd elements
auto it = partition_point(data.begin(), data.end(), IsNegative);
// assign elements to odd from beginning till
// partition point.
negative.assign(data.begin(), it);
positive.assign(it, data.end());
// print contents of odd:
cout << "Negative: ";
for (int& x : negative)
cout << ' ' << x;
cout << '\n';
// print contents of even:
cout << "Positive: ";
for (int& x : positive)
cout << ' ' << x;
cout << '\n';
return 0;
}
Output:
Negative: -1 -4 -2 -5 -3
Positive: 1 3 5 2 4
