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) |
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 | - | проекция для применения к элементам |
Возвращаемое значение
1) Объект, равный
{pivot, last}, где pivot — итератор на первый элемент второй группы.
2) То же, что и (1), если
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) перестановок в случае использования дополнительного буфера памяти. Ровно \(\scriptsize N\)N применений предиката pred и проекции proj.
Примечания
Эта функция пытается выделить временной буфер. Если выделение памяти завершается ошибкой, выбирается менее эффективный алгоритм.
| Макросы проверки функций | Значение | Стандарт | Функция |
|---|---|---|---|
__cpp_lib_constexpr_algorithms |
202306L | 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/w/cpp/algorithm/ranges/stable_partition
