std::stable_partition

Определён в заголовочном файле <algorithm>

Определён в заголовочном файле `<algorithm>`
template< class BidirIt, class UnaryPred > BidirIt stable_partition( BidirIt first, BidirIt last, UnaryPred p );	(1)	(constexpr начиная с C++26)
template< class ExecutionPolicy, class BidirIt, class UnaryPred > BidirIt stable_partition( ExecutionPolicy&& policy, BidirIt first, BidirIt last, UnaryPred p );	(2)	(начиная с C++17)

template< class BidirIt, class UnaryPred >
BidirIt stable_partition( BidirIt first, BidirIt last, UnaryPred p );

(1)

(constexpr начиная с C++26)

template< class ExecutionPolicy, class BidirIt, class UnaryPred >
BidirIt stable_partition( ExecutionPolicy&& policy,
                          BidirIt first, BidirIt last, UnaryPred p );

(2)

(начиная с C++17)

1) Переставляет элементы в диапазоне [first, last) так, чтобы все элементы, для которых предикат p возвращает true, находились перед элементами, для которых предикат p возвращает false. Относительный порядок элементов сохраняется.

2) То же, что и (1), но выполняется согласно policy.

Эта перегрузка участвует в разрешении перегрузки, только если значение следующего выражения равно true:

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(до C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(начиная с C++20)

Если выполняется любое из следующих условий, поведение не определено:

Тип `*first` не удовлетворяет требованиям Swappable.	(до C++11)
`BidirIt` не удовлетворяет требованиям ValueSwappable. Тип `first` не удовлетворяет требованиям MoveConstructible. Тип `first` не удовлетворяет требованиям MoveAssignable.	(начиная с C++11)

Параметры

first, last	-	пара итераторов, задающих диапазон элементов для перестановки
policy	-	политика выполнения
p	-	унарный предикат, возвращающий `true`, если элемент должен находиться перед другими элементами. Выражение `p(v)` должно быть преобразуемо в `bool` для каждого аргумента `v` типа (возможно, const) `VT`, где `VT` — тип значения `BidirIt`, независимо от категории значения, и не должно изменять `v`. Следовательно, тип параметра `VT&`не допускается, как и `VT`, если для `VT` перемещение не эквивалентно копированию(начиная с C++11).
Требования к типам
-`BidirIt` должен удовлетворять требованиям LegacyBidirectionalIterator.
-`UnaryPred` должен удовлетворять требованиям Predicate.

Возвращаемое значение

Итератор на первый элемент второй группы.

Сложность

Пусть \(\scriptsize N\)N — std::distance(first, last):

1) Ровно \(\scriptsize N\)N применений p.

\(\scriptsize O(N)\)O(N) обменов при наличии достаточного объёма дополнительной памяти, иначе не более \(\scriptsize N \cdot log_{2}(N)\)N⋅log₂(N) обменов.

2) \(\scriptsize O(N)\)O(N) применений p.

\(\scriptsize N \cdot log(N)\)N⋅log(N) обменов.

Исключения

Перегрузка с параметром шаблона с именем ExecutionPolicy сообщает об ошибках следующим образом:

Если выполнение функции, вызванной в составе алгоритма, приводит к выбросу исключения и ExecutionPolicy является одной из стандартных политик, вызывается std::terminate. Для любого другого ExecutionPolicy поведение определяется реализацией.
Если алгоритму не удаётся выделить память, выбрасывается std::bad_alloc.

Примечания

Эта функция пытается выделить временный буфер. Если выделение памяти не удаётся, выбирается менее эффективный алгоритм.

Реализации в libc++ и libstdc++ также принимают диапазоны, задаваемые LegacyForwardIterators, в качестве расширения.

Макрос проверки поддержки возможностей	Значение	Стандарт	Возможность
`__cpp_lib_constexpr_algorithms`	`202306L`	(C++26)	constexpr стабильная сортировка (1)

Пример

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v{0, 0, 3, -1, 2, 4, 5, 0, 7};
    std::stable_partition(v.begin(), v.end(), [](int n) { return n > 0; });
    for (int n : v)
        std::cout << n << ' ';
    std::cout << '\n';
}

Вывод:

3 2 4 5 7 0 0 -1 0

Отчёты об ошибках

Следующие отчёты об ошибках, изменяющие поведение, были применены ретроспективно к ранее опубликованным стандартам C++.

DR	Применён к	Опубликованное поведение	Правильное поведение
LWG 2150	C++98	`std::stable_partition` требовалось лишь поместить один элемент, удовлетворяющий `p`, перед одним элементом, не удовлетворяющим `p`	требование исправлено

См. также

partition	разделяет диапазон элементов на две группы (шаблон функции и функциональный объект-алгоритм)
ranges::partition (C++20)
ranges::stable_partition (C++20)	разделяет элементы на две группы, сохраняя их относительный порядок внутри каждой группы (функциональный объект-алгоритм)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/algorithm/stable_partition