Std partition_point in C++
Introduction:
In C++, the standard library provides various algorithms to simplify the development process of complex programs. One such algorithm is std::partition_point, which allows developers to divide a range of elements into two parts based on a specific predicate. In this article, we will explore std::partition_point, its functionality, and how it can be used effectively in C++ programs.
What is std::partition_point?
std::partition_point is a C++ algorithm that allows developers to partition a range of elements into two parts based on a specific predicate. The algorithm operates on a sorted range of elements and returns an iterator pointing to the first element in the second partition, which satisfies the predicate. In other words, the algorithm returns the partition point.
Syntax:
The syntax for std::partition_point is as follows:
template<class ForwardIt, class UnaryPredicate>
ForwardIt partition_point(ForwardIt first, ForwardIt last, UnaryPredicate p);
The std::partition_point function in C++ is a template function that takes three parameters:
- First and last are the iterators that define the range of elements to examine.
- p is a unary predicate that takes a value of the type pointed to by the iterators and returns a Boolean value indicating whether the value meets some criteria.
The function returns an iterator to the first element in the second partition for which the predicate p returns false.
Here's a breakdown of the template parameters:
- ForwardIt is a type parameter that represents the type of the iterator used to access the elements in the range. It must meet the requirements of a ForwardIterator.
- UnaryPredicate is a type parameter that represents the type of the predicate function that takes a value of the type pointed to by ForwardIt and returns a Boolean value.
In C++, templates allow for generic programming by allowing types to be defined at runtime. In this case, the std::partition_point function can work with any type of container as long as it has a ForwardIterator and any type of unary predicate function that returns a Boolean value when given a value of the type pointed to by the iterators. This makes the function highly versatile and useful in a wide range of scenarios.
Implementation:
The std::partition_point algorithm works by using the binary search algorithm on the partitioned range. The algorithm takes three parameters: the beginning and end of the range and a unary predicate function that determines whether an element belongs to the left or right side of the partition.
First, the algorithm checks if the entire range satisfies the predicate. If so, it returns the end iterator of the range. Otherwise, it divides the range into two halves and checks the second half. If the second half satisfies the predicate, the algorithm continues searching the second half. Otherwise, it continues searching the first half.
The algorithm repeats this process until it finds the partition point. Since the algorithm uses binary search, it has a time complexity of O(log n), making it efficient for large datasets.
How does std::partition_point work?
std::partition_point works by using a binary search algorithm to find the partition point. The algorithm begins by examining the middle element in the range. If the middle element satisfies the partitioning criterion, the algorithm continues searching in the second half of the range. Otherwise, the algorithm continues searching in the first half of the range. The process continues until the partition point is found.
If no element in the range satisfies the partitioning criterion, the algorithm returns the last iterator.
Example programs:
1. Find the first element that is greater than or equal to a given value in a sorted range.
#include <iostream>
#include <algorithm>
#include <vector>
int main()
{
std::vector<int> v{ 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int value = 5;
auto it = std::partition_point(v.begin(), v.end(), [value](int i) {
return i < value;
});
if (it != v.end()) {
std::cout << "The first element greater than or equal to " << value << " is " << *it << '\n';
}
else {
std::cout << "No element greater than or equal to " << value << " was found\n";
}
return 0;
}
Explanation:
- The program includes the necessary headers, i.e.,<iostream> and <algorithm>, and declares a std::vector named v that contains a sequence of integers.
- The program initializes an integer variable value with the value 5.
- The program calls std::partition_point with three arguments: v.begin(), v.end(), and a lambda function that takes an integer parameter i and returns a Boolean value indicating whether i is less than the value.
- The lambda function captures value by value, which means that the value of value will be copied and used inside the lambda function.
- The result of the std::partition_point function call is assigned to an iterator named it.
- The program checks if the iterator is equal to v.end(). If it is not, the program prints the value of the first element in the second partition that satisfies the predicate, i.e., the first element greater than or equal to the value.
- If the iterator is equal to v.end(), the program prints a message indicating that no element greater than or equal to the value was found.
Program Output:
![std::partition_point in C++](https://static.tutorialandexample.com/cpp/stdpartition-point-in-cpp1.png)
2. Find the partition point in a range of strings based on their length.
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
int main()
{
std::vector<std::string> v{ "apple", "banana", "pear", "orange", "grape" };
auto it = std::partition_point(v.begin(), v.end(), [](const std::string& s) {
return s.length() < 6;
});
std::cout << "The partition point is: " << *it << '\n';
return 0;
}
Explanation
- The program includes the necessary headers, i.e., <iostream>, <algorithm>, <vector>, and <string>, and declares a std::vector named v that contains a sequence of strings.
- The program calls std::partition_point with three arguments: v.begin(), v.end(), and a lambda function that takes a const std::string& parameter s and returns a Boolean value indicating whether the length of s is less than 6.
- The result of the std::partition_point function call is assigned to an iterator named it.
- The program prints the value of the iterator, which points to the partition point in the range, i.e., the first element for which the predicate is false.
Program Output:
![std::partition_point in C++](https://static.tutorialandexample.com/cpp/stdpartition-point-in-cpp2.png)
Conclusion:
In C++, std::partition_point is a function defined in the header that can be used to find the partition point in a sorted range. The partition point is the point in the range where all elements before it satisfies a given predicate, and all elements after it do not.
std::partition_point takes two iterators that define the range to search and a predicate that defines the partition condition. It returns an iterator to the partition point in the range.
This function is useful when dealing with sorted ranges, as it allows us to quickly find the position where the sorted range can be split into two parts based on a given predicate. This can be helpful when performing binary search operations, or when dealing with ordered data structures.