std::partition
(on partitioned ranges)
<algorithm>
ForwardIt partition( ExecutionPolicy&& policy,
[
first,
last)
in such a way that all elements for which the predicate p returns true precede all elements for which predicate p returns false. Relative order of the elements is not preserved. std::is_execution_policy_v <std::decay_t <ExecutionPolicy>> is true.
(until C++20)std::is_execution_policy_v <std::remove_cvref_t <ExecutionPolicy>> is true.
(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.
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 ForwardIt
, 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(since C++11).
ForwardIt
must meet the requirements of LegacyForwardIterator.
UnaryPred
must meet the requirements of Predicate.
Iterator to the first element of the second group.
Given \(\scriptsize N\)N as std::distance (first, last):
ForwardIt
meets the requirements of LegacyBidirectionalIterator, and at most \(\scriptsize N\)N swaps otherwise.The overload with a template parameter named ExecutionPolicy
reports errors as follows:
ExecutionPolicy
is one of the standard policies, std::terminate is called. For any other ExecutionPolicy
, the behavior is implementation-defined.
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; }
#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
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 |