std::partition
From cppreference.com
| Defined in header <algorithm>
|
||
template< class ForwardIt, class UnaryPred >
ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPred p );
|
(1) | (constexpr since C++20) |
template< class ExecutionPolicy, class ForwardIt, class UnaryPred >
ForwardIt partition( ExecutionPolicy&& policy,
ForwardIt first, ForwardIt last, UnaryPred p );
|
(2) | (since C++17) |
1) Partitions the elements
e in the target range [first, last) with respect to the expression bool(p(e)): all elements satisfy p appear before all elements that do not.2) Same as (1), but executed according to
policy. This overload participates in overload resolution only if the value of the following expression is
true:
|
|
(until C++20) |
|
|
(since C++20) |
If the type of *first is not Swappable(until C++11)ForwardIt is not ValueSwappable(since C++11), the behavior is undefined.
Contents
Parameters
| first, last | - | the pair of iterators defining the target range |
| p | - | unary predicate which returns true for the elements before the partition point. The expression |
| policy | - | the execution policy to use |
| Type requirements | ||
-ForwardIt must meet the requirements of LegacyForwardIterator.
| ||
-UnaryPred must meet the requirements of Predicate.
|
Return value
The iterator iter indicating the partition point: all elements before iter satisfy p, while all elements starting from iter do not.
Complexity
Given N as std::distance(first, last):
1) At most N swaps (or only at most
swaps if
| N |
| 2 |
ForwardIt meets the requirements of LegacyBidirectionalIterator), and exactly N applications of p.2) 𝓞(N·log(N)) swaps, and 𝓞(N) applications of
p.Exceptions
2) During the execution process:
- If the temporary memory resources required for parallelization are not available, std::bad_alloc is thrown.
- If an uncaught exception is thrown while accessing objects via an algorithm argument, the behavior is determined by the execution policy (for standard policies, std::terminate is invoked).
Possible implementation
Implements overload (1) preserving C++11 compatibility.
template<class ForwardIt, class UnaryPred>
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPred 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;
}
|
Example
Run this code
#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';
}
Possible 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
Defect reports
The following behavior-changing defect reports were applied retroactively to previously published C++ standards.
| DR | Applied to | Behavior as published | Correct behavior |
|---|---|---|---|
| LWG 498 | C++98 | std::partition required first andlast to be LegacyBidirectionalIterator
|
only required to be LegacyForwardIterator |
| LWG 2150 | C++98 | std::partition was only required to place one elementsatisfying p before one element not satisfying p
|
corrected the requirement |
See also
(C++20) |
divides a range of elements into two groups (algorithm function object) |
(C++11) |
determines if the range is partitioned by the given predicate (function template & algorithm function object) |
(C++20) |
|
| divides elements into two groups while preserving their relative order within each group (function template & algorithm function object) | |
(C++20) |