std::ranges::partition
Определён в заголовочном файле <algorithm> | ||
|---|---|---|
| Сигнатура вызова | ||
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) | (начиная с 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) | (начиная с C++20) |
[first, last) таким образом, что проекция proj всех элементов, для которых предикат pred возвращает true, располагается перед проекцией proj элементов, для которых предикат pred возвращает false. Относительный порядок элементов не сохраняется.r в качестве исходного диапазона, как если бы ranges::begin(r) использовался в качестве first, а ranges::end(r) — в качестве last.Описанные на этой странице функциональные объекты — это объекты-функции алгоритмов (неформально известные как niebloids
Параметры
first, last - пара итератора и сентинела, задающая диапазон элементов для изменения порядка
r - диапазон элементов для изменения порядка
pred - предикат, применяемый к спроецированным элементам
proj - проекция, применяемая к элементам
Возвращаемое значение
Поддиапазон, начинающийся с итератора на первый элемент второй группы и заканчивающийся итератором, равным last. (2) возвращает std::ranges::dangling, если r является rvalue неклассифицируемого как borrowed_range типа.
Сложность
Для N = ranges::distance(first, last) выполняется ровно N применений предиката и проекции. Не более N / 2 обменов, если I моделирует ranges::bidirectional_iterator, и не более N обменов в противном случае.
Возможная реализация
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::end(r),
std::ref(pred), std::ref(proj));
}
};
inline constexpr partition_fn partition;
|
Пример
#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: \t";
ranges::copy(v, cout);
auto tail = ranges::partition(v, [](int i) { return i % 2 == 0; });
std::cout << "\nPartitioned vector: \t";
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: \t\t";
ranges::copy(fl, cout);
quicksort(ranges::begin(fl), ranges::end(fl), ranges::greater {});
std::cout << "\nQuick-sorted list: \t";
ranges::copy(fl, cout);
std::cout << '\n';
}
Возможный вывод:
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 Quick-sorted list: 92 64 30 6 5 3 2 1 1 1 -4 -4 -5 -8
См. также
|
(C++20) | копирует диапазон, разделяя элементы на две группы (объект-функция алгоритма) |
|
(C++20) | определяет, разделён ли диапазон согласно заданному предикату (объект-функция алгоритма) |
|
(C++20) | разделяет элементы на две группы, сохраняя их относительный порядок внутри каждой группы (объект-функция алгоритма) |
| разделяет диапазон элементов на две группы (шаблон функции) |
© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/algorithm/ranges/partition
