std::ranges::stable_partition
Определено в заголовочном файле <algorithm> | ||
|---|---|---|
| Сигнатура вызова | ||
template< std::bidirectional_iterator I, std::sentinel_for<I> S,
class Proj = std::identity,
std::indirect_unary_predicate<std::projected<I, Proj>> Pred >
requires std::permutable<I>
ranges::subrange<I>
stable_partition( I first, S last, Pred pred, Proj proj = {} );
| (1) |
(начиная с C++20) (constexpr начиная с C++26) |
template< ranges::bidirectional_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>
stable_partition( R&& r, Pred pred, Proj proj = {} );
| (2) |
(начиная с C++20) (constexpr начиная с C++26) |
[first, last) таким образом, что проекция proj всех элементов, для которых предикат pred возвращает true, предшествует проекции proj элементов, для которых предикат pred возвращает false. Алгоритм является стабильным, то есть относительный порядок элементов сохраняется.r, как если бы в качестве first использовался ranges::begin(r), а в качестве last — ranges::end(r).Описанные на этой странице функциональные объекты представляют собой функциональные объекты алгоритмов (неформально известные как небиоиды
Параметры
first, last - пара итератора и сентинела, задающая диапазон переставляемых элементов
r - диапазон переставляемых элементов
pred - предикат, применяемый к спроецированным элементам
proj - проекция, применяемая к элементам
Возвращаемое значение
{pivot, last}, где pivot — итератор на первый элемент второй группы.r является lvalue или имеет тип borrowed_range. В противном случае возвращает std::ranges::dangling.Сложность
Для N = ranges::distance(first, last) сложность составляет не более \(\scriptsize N\cdot\log{(N)}\)N·log(N) обменов; при использовании дополнительного буфера памяти требуется лишь \(\scriptsize \mathcal{O}(N)\)𝓞(N) обменов. Предикат pred и проекция proj применяются ровно \(\scriptsize N\)N раз.
Примечания
Эта функция пытается выделить временный буфер. Если выделение не удаётся, выбирается менее эффективный алгоритм.
| Макрос проверки возможностей | Значение | Стандарт | Возможность |
|---|---|---|---|
__cpp_lib_constexpr_algorithms | 202306L | (C++26) | constexpr стабильная сортировка |
Возможная реализация
Эта реализация не использует дополнительный буфер памяти и поэтому может быть менее эффективной. См. также реализации в MSVC STL и libstdc++.
struct stable_partition_fn
{
template<std::bidirectional_iterator I, std::sentinel_for<I> S,
class Proj = std::identity,
std::indirect_unary_predicate<std::projected<I, Proj>> Pred>
requires std::permutable<I>
constexpr ranges::subrange<I>
operator()(I first, S last, Pred pred, Proj proj = {}) const
{
first = ranges::find_if_not(first, last, pred, proj);
I mid = first;
while (mid != last)
{
mid = ranges::find_if(mid, last, pred, proj);
if (mid == last)
break;
I last2 = ranges::find_if_not(mid, last, pred, proj);
ranges::rotate(first, mid, last2);
first = ranges::next(first, ranges::distance(mid, last2));
mid = last2;
}
return {std::move(first), std::move(mid)};
}
template<ranges::bidirectional_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::move(pred), std::move(proj));
}
};
inline constexpr stable_partition_fn stable_partition {};
|
Пример
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
namespace rng = std::ranges;
template<std::permutable I, std::sentinel_for<I> S>
constexpr void stable_sort(I first, S last)
{
if (first == last)
return;
auto pivot = *rng::next(first, rng::distance(first, last) / 2, last);
auto left = [pivot](const auto& em) { return em < pivot; };
auto tail1 = rng::stable_partition(first, last, left);
auto right = [pivot](const auto& em) { return !(pivot < em); };
auto tail2 = rng::stable_partition(tail1, right);
stable_sort(first, tail1.begin());
stable_sort(tail2.begin(), tail2.end());
}
void print(const auto rem, auto first, auto last, bool end = true)
{
std::cout << rem;
for (; first != last; ++first)
std::cout << *first << ' ';
std::cout << (end ? "\n" : "");
}
int main()
{
const auto original = {9, 6, 5, 2, 3, 1, 7, 8};
std::vector<int> vi {};
auto even = [](int x) { return 0 == (x % 2); };
print("Original vector:\t", original.begin(), original.end(), "\n");
vi = original;
const auto ret1 = rng::stable_partition(vi, even);
print("Stable partitioned:\t", vi.begin(), ret1.begin(), 0);
print("│ ", ret1.begin(), ret1.end());
vi = original;
const auto ret2 = rng::partition(vi, even);
print("Partitioned:\t\t", vi.begin(), ret2.begin(), 0);
print("│ ", ret2.begin(), ret2.end());
vi = {16, 30, 44, 30, 15, 24, 10, 18, 12, 35};
print("Unsorted vector: ", vi.begin(), vi.end());
stable_sort(rng::begin(vi), rng::end(vi));
print("Sorted vector: ", vi.begin(), vi.end());
}
Возможный вывод:
Original vector: 9 6 5 2 3 1 7 8 Stable partitioned: 6 2 8 │ 9 5 3 1 7 Partitioned: 8 6 2 │ 5 3 1 7 9 Unsorted vector: 16 30 44 30 15 24 10 18 12 35 Sorted vector: 10 12 15 16 18 24 30 30 35 44
См. также
|
(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/stable_partition
