The C++ Standard Template Library provides several powerful algorithms for reorganizing container elemants based on predicate conditions. Among these, the partition family of algorithms offers flexible mechanisms for dividing sequences into two groups.

partition()

The partition() algorithm rearranges elements within a given range, separating them into two groups based on a unary predicate. Elements satisfying the predicate are moved to the front of the range, while elements not satisfying it appear after. The algorithm returns an iterator marking the boundary between the two groups. Note that this operation does not preserve the relative order of elements.

Function Signature:

template <class BidirectionalIterator, class UnaryPredicate>
BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate pred);

Example:

std::vector<int> data = {9, 7, 5, 3, 6, 4, 2, 8};
auto greater_than_five = [](int n) { return n > 5; };
auto boundary = std::partition(data.begin(), data.end(), greater_than_five);

After this operation, elements greater than 5 occupy positions before boundary, while elements 5 or less appear after it.

partition_copy()

Unlike partition(), the partition_copy() algorithm does not modify the original container. Instead, it copies elements satisfying the predicate to one output iterator and elements not satisfying it to another. The original sequence remains untouched.

Function Signature:

template <class InputIterator, class OutputIterator1, class OutputIterator2, class UnaryPredicate>
std::pair<OutputIterator1, OutputIterator2>
partition_copy(InputIterator first, InputIterator last, 
               OutputIterator1 out_true, OutputIterator2 out_false, 
               UnaryPredicate pred);

Example:

std::vector<double> source = {1.5, 2.7, 3.3, 4.8, 5.1};
std::vector<double> positive_values, non_positive_values;
auto is_positive = [](double n) { return n > 0.0; };

auto result = std::partition_copy(source.begin(), source.end(),
                                   std::back_inserter(positive_values),
                                   std::back_inserter(non_positive_values),
                                   is_positive);

This separates positive numbers into positive_values and non-positive numbers into non_positive_values.

stable_partition()

The stable_partition() algorithm performs the same logical separation as partition() but with a crucial difference: it maintains the relative order of elements within each partition. This stability comes with additional memory or time overhead compared to the unstable version.

Function Signature:

template <class BidirectionalIterator, class UnaryPredicate>
BidirectionalIterator stable_partition(BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate pred);

Example:

std::deque<char> characters = {'a', 'b', 'c', '1', '2', '3'};
auto is_letter = [](char c) { return std::isalpha(static_cast<unsigned char>(c)); };
auto boundary = std::stable_partition(characters.begin(), characters.end(), is_letter);

The letters 'a', 'b', 'c' remain in their original order within the first partition, followed by digits '1', '2', '3'.

partition_point()

The partition_point() algorithm locates the boundary iterator in a already partitioned range. Given a range where all elements before a certain point satisfy the predicate and all elements from that point onward do not, this function returns an iterator to the first element that does not satisfy the predicate.

Function Signature:

template <class ForwardIterator, class UnaryPredicate>
ForwardIterator partition_point(ForwardIterator first, ForwardIterator last, UnaryPredicate pred);

Example:

std::array<int, 6> values = {2, 4, 6, 7, 9, 11};
auto is_divisible_by_two = [](int n) { return n % 2 == 0; };
auto partition_boundary = std::partition_point(values.begin(), values.end(), is_divisible_by_two);

In this case, partition_boundary points to the element 7, which is the first odd number where the predicate transitions from true to false.