Руководство по стандартной библиотеке шаблонов STL


Разделить (Partitions)


template <class BidirectionalIterator, class Predicate> BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);

     partition помещает все элементы в диапазоне [first, last), которые удовлетворяют pred, перед всеми элементами, которые не удовлетворяют. Возвращается итератор i такой, что для любого итератора j в диапазоне [first, i) будет pred (*j) == true, а для любого итератора k в диапазоне [i, last) будет pred(*k) == false. Делается максимально (last - first)/2 перестановок. Предикат применяется точно last - first раз.

template <class BidirectionalIterator, class Predicate> BidirectionalIterator stable_partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);

     stable_partition помещает все элементы в диапазоне [first, last), которые удовлетворяют pred, перед всеми элементами, которые не удовлетворяют. Возвращается итератор i такой, что для любого итератора j в диапазоне [first, i) будет pred(*j) == true, а для любого итератора k в диапазоне [i, last) будет pred(*k) == false. Относительный порядок элементов в обеих группах сохраняется. Делается максимально (last - first) * log(last - first) перестановок, но только линейное число перестановок, если имеется достаточная дополнительная память. Предикат применяется точно last - first раз.






Начало  Назад  Вперед