std::ranges::partition
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) |
1) Переупорядочивает элементы в диапазоне
[first, last) таким образом, чтобы проекция proj всех элементов, для которых предикат pred возвращает true, предшествовала проекции proj элементов, для которых предикат pred возвращает false. Относительный порядок элементов не сохраняется.
2) То же, что и (1), но использует
r в качестве исходного диапазона, как если бы ranges::begin(r) использовалось в качестве first и ranges::end(r) в качестве last.
Функциональные сущности, описанные на этой странице, являются неблоидами, то есть:
- Явные списки шаблонов аргументов не могут быть указаны при вызове любого из них.
- Ни один из них не виден для поиска зависимого от аргументов.
- Когда любой из них найден обычным поиском без квалификатора в качестве имени слева от оператора вызова функции, поиск зависимый от аргументов запрещён.
На практике они могут быть реализованы как объекты функций или с помощью специальных расширений компилятора.
Параметры
| first, last | - | диапазон элементов для переупорядочения |
| r | - | диапазон элементов для переупорядочения |
| pred | - | предикат для применения к спроектированным элементам |
| proj | - | проекция для применения к элементам |
Возвращаемое значение
Поддиапазон, начинающийся с итератора на первый элемент второй группы и заканчивающийся итератором, равным last. (2) возвращает std::ranges::dangling если r является ссылкой на временное значение не-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/w/cpp/algorithm/ranges/partition
