std::partition() algorithm

od C++20

// (1)
template< class ForwardIt, class UnaryPredicate >
constexpr ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPredicate p );

// (2)
template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate >
ForwardIt partition( ExecutionPolicy&& policy,
                     ForwardIt first, ForwardIt last, UnaryPredicate p );

od C++17

// (1)
template< class ForwardIt, class UnaryPredicate >
ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPredicate p );

// (2)
template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate >
ForwardIt partition( ExecutionPolicy&& policy,
                     ForwardIt first, ForwardIt last, UnaryPredicate p );

do C++17

// (1)
template< class ForwardIt, class UnaryPredicate >
ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPredicate p );

• (1) Reorders the elements in the range [first; last) in such a way that all elements for which the predicate p returns true precede the elements for which predicate p returns false.

  uwaga

  Relative order of the elements is not preserved.

• (2) Same as (1), but executed according to policy.

  Overload Resolution

  These overloads participate in overload resolution only if std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>  (do C++20) std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>  (od C++20) is true.

Parameters

first last	The range of elements to reorder.
policy	The execution policy to use. See execution policy for details.
p	Unary predicate which returns true for the required element. The expression p(v) must be convertible to bool for every argument v of type (possibly const) VT, where VT is the value type of InputIt, regardless of value category, and must not modify v. Thus, a parameter type of VT& is not allowed , nor is VT unless for VT a move is equivalent to a copy. (od C++11).

Type requirements

ForwardIt

LegacyForwardIterator ValueSwappable

Implementations may carry out the operation more efficiently if ForwardIt satisfies LegacyBidirectionalIterator.

UnaryPredicate

Predicate

Return value

Iterator to the first element of the second group.

Complexity

Given N as std::distance(first, last):

(1) Exactly N applications of p. At most N / 2 swaps, if ForwardIt meets the requirements of LegacyForwardIterator,
N swaps otherwise.

(2) O(N * log(N)) swaps and O(N) applications of p.

Exceptions

The overloads with a template parameter named ExecutionPolicy report errors as follows:

• If execution of a function invoked as part of the algorithm throws an exception and ExecutionPolicy is one of the standard policies, std::terminate is called. For any other ExecutionPolicy, the behavior is implementation-defined.
• If the algorithm fails to allocate memory, std::bad_alloc is thrown.

Possible implementation

partition (1)

template<class ForwardIt, class UnaryPredicate>
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPredicate p)
{
    first = std::find_if_not(first, last, p);
    if (first == last)
        return first;

    for (auto i = std::next(first); i != last; ++i)
        if (p(*i))
        {
            std::iter_swap(i, first);
            ++first;
        }

    return first;
}

Examples

Main.cpp

#include <algorithm>
#include <forward_list>
#include <iostream>
#include <iterator>
#include <vector>

template<class ForwardIt>
void quicksort(ForwardIt first, ForwardIt last)
{
    if (first == last)
        return;

    auto pivot = *std::next(first, std::distance(first, last) / 2);
    auto middle1 = std::partition(first, last, [pivot](const auto& em)
    {
        return em < pivot;
    });
    auto 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: ";
    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: ";
    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: ";
    for (int n : fl)
        std::cout << n << ' ';

    quicksort(std::begin(fl), std::end(fl));
    std::cout << "\nSorted using quicksort: ";
    for (int fi : fl)
        std::cout << fi << ' ';
    std::cout << '\n';
}

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