The function partition_point obtains the partition point by returning an iterator pointing to the initial partitioned element within the range [first, last] where the pred(predicate) evaluates to false, signifying the partition point location of that specific element.
If the partition function had been executed with the same parameters, the elements within the range should already be arranged in partitions.
The function examines elements that are not next to each other within the sorted range, which is particularly efficient when dealing with random-access iterators, in order to minimize the number of comparisons needed.
Locating the initial element within the given range where the predicate evaluates to false necessitates employing the partition_point function from the C++ algorithm library. The arrangement of elements ensures that items meeting the condition precede those that do not meet it.
Syntax
ForwardIterator partition_point(ForwardIterator first,
ForwardIterator last,
UnaryPredicate pred);
The initial and final arguments are forward iterators that point to the start and end of the divided sequence, correspondingly. The examined range encompasses [first, last], encompassing all elements from the initial to the final iterator, but excluding the element referenced by the final iterator.
A single-argument function that accepts a range element and produces a value that can be cast to a boolean. The output indicates whether the element should precede the partition point (true) or be positioned at or after it (false). The input parameter remains unchanged throughout the function's execution. This function can be implemented as either a function object or a function pointer.
Return Value: An iterator pointing to the final element within the segmented range [first, last] in case pred evaluates to false for any element, or to the last element if pred is false for any element.
This function template's definition is equal to:
template
ForwardIterator partition_point (ForwardIterator first, ForwardIterator last,
UnaryPredicate pred)
{
auto n = distance(first, last);
while (n>0)
{
ForwardIterator it = first;
auto step = n/2;
std::advance (it, step);
if (pred(*it)) { first=++it; n-=step+1; }
else n=step;
}
return first;
}
Example
// C++ program to get odd elements
// and even elements
#include <iostream> // std::cout
#include <algorithm> // std::partition, std::partition_point
#include <vector> // std::vector
bool IsOdd(int i) { return (i % 2) == 1; }
int main()
{
std::vector<int> data{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
std::vector<int> odd, even;
// partition data on the basis of odd elements
// using pred IsOdd()
std::stable_partition(data.begin(), data.end(), IsOdd);
// gets the partition point based on odd elements
auto it = std::partition_point(data.begin(), data.end(),
IsOdd);
// assign elements to odd from beginning till partition
// point.
odd.assign(data.begin(), it);
even.assign(it, data.end());
// print contents of odd:
std::cout << "odd:";
for (int& x : odd)
std::cout << ' ' << x;
std::cout << '\n';
// print contents of even:
std::cout << "even:";
for (int& x : even)
std::cout << ' ' << x;
std::cout << '\n';
return 0;
}
Output:
odd: 1 3 5 7 9
even: 2 4 6 8 10
Example
// C++ program to get negative elements
// and positive elements using partition_point
#include <iostream> // std::cout
#include <algorithm> // std::partition, std::partition_point
#include <vector> // std::vector
bool IsNegative(int i) { return (i < 0); }
int main()
{
std::vector<int> data{ 1, -1, 3, -4, 5, 2, -2, 4,
-5, -3 };
std::vector<int> negative, positive;
// partition data on the basis of odd elements using
// pred IsNegative()
std::stable_partition(data.begin(), data.end(),
IsNegative);
// gets the partition point based on odd elements
auto it = std::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:
std::cout << "Negative: ";
for (int& x : negative)
std::cout << ' ' << x;
std::cout << '\n';
// print contents of even:
std::cout << "Positive: ";
for (int& x : positive)
std::cout << ' ' << x;
std::cout << '\n';
return 0;
}
Output:
Negative: -1 -4 -2 -5 -3
Positive: 1 3 5 2 4
Roughly log2(N)+2 comparisons of elements are executed (where N represents this distance). The iterator progressions introduce an extra linear complexity in N for non-random access iterators, on average.
Example
#include <iostream>
#include <algorithm>
#include <vector>
bool IsOdd(int i) { return (i % 2) == 1; }
int main(){
std::vector<int> data{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
std::vector<int> odd, even;
std::stable_partition(data.begin(), data.end(), IsOdd);
auto it = std::partition_point(data.begin(), data.end(),
IsOdd);
odd.assign(data.begin(), it);
even.assign(it, data.end());
std::cout << "odd:";
for (int& x : odd)
std::cout << ' ' << x;
std::cout << '\n';
std::cout << "even:";
for (int& x : even)
std::cout << ' ' << x;
std::cout << '\n';
return 0;
}
Output:
odd: 1 3 5 7 9
even: 2 4 6 8 10
