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 для элементов, которые надо переместить в начало. Определение функции предиката должно быть эквивалентно следующему: bool pred(const Type &a); Присутствие const & в определении не обязательно, но функция не должна модифицировать передаваемые ей объекты. |
| Требования к типам | ||
-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
[править] См. также
| делит диапазон элементов на две группы (шаблон функции) |
