std::stable_partition — cppreference.com

Материал из cppreference.com


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

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

Параметры

first, last	—	полуоткрытый диапазон элементов, которые надо упорядочить
p	—	унарный предикат, который возвращает`true` для элементов, которые надо переместить в начало. Определение функции предиката должно быть эквивалентно следующему: `bool pred(const Type &a);` Присутствие `const &` в определении не обязательно, но функция не должна модифицировать передаваемые ей объекты. Тип `Type` должен быть таков, что объект типа `BidirIt` может быть разыменован и затем неявно преобразован в `Type`.
Требования к типам
-`BidirIt` должен соответствовать требованиям `ValueSwappable` и `BidirectionalIterator`.
-The type of dereferenced `BidirIt` must meet the requirements of `MoveAssignable` and `MoveConstructible`.

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

Итератор на первый элемент второй группы (другими словами, на первый элемент, для которого p ложен).

Сложность

Ровно last-first применений предиката и максимум (last-first)*log(last-first) обменов, если недостаточно памяти. Если памяти достаточно, количество обменов снижается до линейного.

Пример

#include <iostream>
#include <algorithm>

int main()
{
    std::vector<int> v{0, 0, 3, 0, 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';
}

Вывод:

См. также

Категории: