std::stable_partition
| Определено в заголовочном файле <algorithm>
|
||
template< class BidirIt, class UnaryPredicate > BidirIt stable_partition( BidirIt first, BidirIt last, UnaryPredicate p ); |
||
Переупорядочивает элементы в диапазоне [first, last) таким образом, чтобы сначала шли те элементы, для которых p возвращает true, а затем — те, для которых p возвращает false. Относительный порядок элементов сохраняется.
Параметры
| first, last | — | полуоткрытый диапазон элементов, которые надо упорядочить |
| p | — | унарный предикат, который возвращаетtrue для элементов, которые надо переместить в начало. Определение функции предиката должно быть эквивалентно следующему:
Присутствие |
| Требования к типам | ||
-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';
}
Вывод:
3 2 4 5 7 0 0 0 0
См. также
| делит диапазон элементов на две группы (шаблон функции) |
