std::stable_partition

Определено в заголовке <algorithm>

Определено в заголовке `<algorithm>`
template< class BidirIt, class UnaryPredicate > BidirIt stable_partition( BidirIt first, BidirIt last, UnaryPredicate p );	(1)	(constexpr с C++26)
template< class ExecutionPolicy, class BidirIt, class UnaryPredicate > BidirIt stable_partition( ExecutionPolicy&& policy, BidirIt first, BidirIt last, UnaryPredicate p );	(2)	(с C++17)

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

(1)

(constexpr с C++26)

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

(2)

(с C++17)

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

2) То же, что и (1), но выполняется согласно policy. Этот перегруз не участвует в разрешении перегрузки, если

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>` является `true`.	(до C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>` является `true`.	(с C++20)

Параметры

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

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

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

Сложность

Дано \(\scriptsize N\)N как std::distance(first, last):

1) Ровно \(\scriptsize N\)N применений предиката и \(\scriptsize O(N)\)O(N) обменов, если есть достаточно дополнительной памяти. Если памяти недостаточно, не более \(\scriptsize N log(N)\)N log(N) обменов.

2) \(\scriptsize N log(N)\)N log(N) обменов и \(\scriptsize O(N)\)O(N) применений предиката.

Исключения

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

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

Примечания

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

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

Макрос проверки наличия функции	Значение	Стандарт	Функция
`__cpp_lib_constexpr_algorithms`	202306L		`constexpr` стабильная сортировка

Пример

#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

См. также

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

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