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 N as ranges::distance(first, last) or ranges::distance(r):
1,2) At most N swaps (or only at most
swaps if
| N |
| 2 |
I or ranges::iterator_t<R> models bidirectional_iterator), and exactly N applications of pred and proj.3,4) 𝓞(N·log(N)) swaps, and 𝓞(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).
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