std::ranges::partition
From cppreference.com
| Defined in header <algorithm>
|
||
| Call signature |
||
template< std::permutable I, std::sentinel_for<I> S, class Proj = std::identity,
std::indirect_unary_predicate<std::projected<I, Proj>> Pred >
constexpr ranges::subrange<I>
partition( I first, S last, Pred pred, Proj proj = {} );
|
(1) | (since C++20) |
template< ranges::forward_range R, class Proj = std::identity,
std::indirect_unary_predicate
<std::projected<ranges::iterator_t<R>, Proj>> Pred >
requires std::permutable<ranges::iterator_t<R>>
constexpr ranges::borrowed_subrange_t<R>
partition( R&& r, Pred pred, Proj proj = {} );
|
(2) | (since C++20) |
template< /*execution-policy*/ Ep,
std::random_access_iterator I, std::sized_sentinel_for<I> S,
class Proj = std::identity,
std::indirect_unary_predicate<std::projected<I, Proj>> Pred >
requires std::permutable<I>
ranges::subrange<I>
partition( Ep&& policy, I first, S last, Pred pred, Proj proj = {} );
|
(3) | (since C++26) |
template< /*execution-policy*/ Ep,
/*sized-random-access-range*/ R, class Proj = std::identity,
std::indirect_unary_predicate
<std::projected<ranges::iterator_t<R>, Proj>> Pred >
requires std::permutable<ranges::iterator_t<R>>
ranges::borrowed_subrange_t<R>
partition( Ep&& policy, R&& r, Pred pred, Proj proj = {} );
|
(4) | (since C++26) |
For the definition of /*execution-policy*/, see this page; for the definition of /*sized-random-access-range*/, see this page.
1,2) Partitions the elements
e in the target range [first, last) or r with respect to the expression bool(std::invoke(pred, std::invoke(proj, e))): all elements (projected by proj) satisfy pred appear before all elements that do not.3,4) Same as (1,2), but executed according to
policy.The function-like entities described on this page are algorithm function objects (informally known as niebloids), that is:
- Explicit template argument lists cannot be specified when calling any of them.
- None of them are visible to argument-dependent lookup.
- When any of them are found by normal unqualified lookup as the name to the left of the function-call operator, argument-dependent lookup is inhibited.
Parameters
| first, last | - | the iterator-sentinel pair defining the target range |
| r | - | the target range |
| pred | - | the predicate to be applied to the (projected) elements |
| proj | - | the projection to be applied to the elements |
| policy | - | the execution policy to use |
Return value
A subrange from the partition point to the end of the target range. All elements outside the subrange satisfy p, while all elements in the subrange do not.
Complexity
Given \(\scriptsize N\)N as ranges::distance(first, last) or ranges::distance(r):
1,2) At most \(\scriptsize N\)N swaps (or only at most \(\scriptsize \frac N2\)
swaps if
| N |
| 2 |
I or ranges::iterator_t<R> models bidirectional_iterator), and exactly \(\scriptsize N\)N applications of pred and proj.3,4) \(\scriptsize \mathcal{O}(N \cdot \log(N))\)(Nlog(N)) swaps, and \(\scriptsize \mathcal{O}(N)\)(N) applications of
pred and proj.Exceptions
3,4) 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).
Notes
| Feature-test macro | Value | Std | Feature |
|---|---|---|---|
__cpp_lib_parallel_algorithm |
202506L |
(C++26) | Parallel range algorithms, overloads (3,4) |
Possible implementation
struct partition_fn
{
template<std::permutable I, std::sentinel_for<I> S, class Proj = std::identity,
std::indirect_unary_predicate<std::projected<I, Proj>> Pred>
constexpr ranges::subrange<I>
operator()(I first, S last, Pred pred, Proj proj = {}) const
{
first = ranges::find_if_not(first, last, std::ref(pred), std::ref(proj));
if (first == last)
return {first, first};
for (auto i = ranges::next(first); i != last; ++i)
{
if (std::invoke(pred, std::invoke(proj, *i)))
{
ranges::iter_swap(i, first);
++first;
}
}
return {std::move(first), std::move(last)};
}
template<ranges::forward_range R, class Proj = std::identity,
std::indirect_unary_predicate
<std::projected<ranges::iterator_t<R>, Proj>> Pred>
requires std::permutable<ranges::iterator_t<R>>
constexpr ranges::borrowed_subrange_t<R>
operator()(R&& r, Pred pred, Proj proj = {}) const
{
return (*this)(ranges::begin(r),
ranges::next(ranges::begin(r), ranges::end(r)),
std::ref(pred), std::ref(proj));
}
};
inline constexpr partition_fn partition;
|
Example
Run this code
#include <algorithm>
#include <forward_list>
#include <functional>
#include <iostream>
#include <iterator>
#include <ranges>
#include <vector>
namespace ranges = std::ranges;
template<class I, std::sentinel_for<I> S, class Cmp = ranges::less>
requires std::sortable<I, Cmp>
void quicksort(I first, S last, Cmp cmp = Cmp {})
{
using reference = std::iter_reference_t<I>;
if (first == last)
return;
auto size = ranges::distance(first, last);
auto pivot = ranges::next(first, size - 1);
ranges::iter_swap(pivot, ranges::next(first, size / 2));
auto tail = ranges::partition(first, pivot, [=](reference em)
{
return std::invoke(cmp, em, *pivot); // em < pivot
});
ranges::iter_swap(pivot, tail.begin());
quicksort(first, tail.begin(), std::ref(cmp));
quicksort(ranges::next(tail.begin()), last, std::ref(cmp));
}
int main()
{
std::ostream_iterator<int> cout{std::cout, " "};
std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
std::cout << "Original vector: ";
ranges::copy(v, cout);
auto tail = ranges::partition(v, [](int i) { return i % 2 == 0; });
std::cout << "\nPartitioned vector: ";
ranges::copy(ranges::begin(v), ranges::begin(tail), cout);
std::cout << " ";
ranges::copy(tail, cout);
std::forward_list<int> fl{1, 30, -4, 3, 5, -4, 1, 6, -8, 2, -5, 64, 1, 92};
std::cout << "\nUnsorted list: ";
ranges::copy(fl, cout);
quicksort(ranges::begin(fl), ranges::end(fl), ranges::greater{});
std::cout << "\nSorted using quicksort: ";
ranges::copy(fl, cout);
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: 92 64 30 6 5 3 2 1 1 1 -4 -4 -5 -8
See also
| divides a range of elements into two groups (function template) | |
(C++20) |
copies a range dividing the elements into two groups (algorithm function object) |
(C++20) |
determines if the range is partitioned by the given predicate (algorithm function object) |
(C++20) |
divides elements into two groups while preserving their relative order within each group (algorithm function object) |