std::ranges::stable_partition
С сайта ru.cppreference.net
| Определено в заголовке <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.Сущности, подобные функциям, описанные на этой странице, являются объектами-функциями алгоритмов (неформально известными как niebloids), то есть:
- Явные списки аргументов шаблона не могут быть указаны при вызове любой из них.
- Ни одна из них не видна при поиске, зависящем от аргументов.
- Когда любая из них находится при обычном неквалифицированном поиске в качестве имени слева от оператора вызова функции, поиск, зависящий от аргументов, подавляется.
Параметры
| first, last | - | пара итератор-страж, определяющая диапазон элементов для переупорядочивания |
| r | - | диапазон элементов для переупорядочивания |
| pred | - | предикат для применения к проецируемым элементам |
| proj | - | проекция для применения к элементам |
Возвращаемое значение
1)
Объект, равный
{
pivot, last
}
, где
pivot
является итератором на первый элемент второй группы.
2)
То же, что и
(1)
если
r
является lvalue или имеет тип
borrowed_range
. В противном случае возвращает
std::ranges::dangling
.
Сложность
При N = ranges:: distance ( first, last ) сложность в худшем случае составляет N·log(N) обменов, и только 𝓞(N) обменов в случае использования дополнительного буфера памяти. Ровно N применений предиката pred и проекции proj .
Примечания
Эта функция пытается выделить временный буфер. Если выделение завершается неудачей, выбирается менее эффективный алгоритм.
| Макрос тестирования возможностей | Значение | Стандарт | Возможность |
|---|---|---|---|
__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) |
определяет, разделён ли диапазон заданным предикатом (алгоритмический функциональный объект) |
| разделяет элементы на две группы, сохраняя их относительный порядок внутри каждой группы (шаблон функции) |