Пространства имён
Варианты
Действия

std::partition

Материал из cppreference.com
< cpp‎ | algorithm
 
 
Алгоритмы
Функции
Немодифицирующие линейные операции
Модифицирующие линейные операции
Разделение
is_partitioned(C++11)
partition
partition_copy(C++11)
Сортировка (на отсортированных промежутках)
Бинарный поиск (на отсортированных промежутках)
Множества (на отсортированных промежутках)
Куча
Минимум/максимум
Числовые операции
Библиотека C
 

Определено в заголовочном файле <algorithm>
(1)
template< class BidirIt, class UnaryPredicate >
BidirIt partition( BidirIt first, BidirIt last, UnaryPredicate p );
(до C++11)
template< class ForwardIt, class UnaryPredicate >
ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPredicate p );
(начиная с C++11)
template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate >
ForwardIt partition( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, UnaryPredicate p );
(2)
1) Переставляет элементы в диапазоне [first, last) так, чтобы все элементы, для которых предикат p возвращает true, предшествовали элементам, для которых предикат p возвращает false. Относительный порядок элементов не сохраняется.
2) То же, что и (1), но выполняется в соответствии с policy. Это определение участвует в перегрузке только если std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> определено как true.

Содержание

[править] Параметры

first, last - диапазон, к которому будет применена перестановка
policy - используемая политика выполнения (execution policy). См. execution policy.
p - унарный предикат, который возвращает​true для элементов, которые должны быть переставлены в первую группу.

Определение функции предиката должно быть эквивалентно следующему:

 bool pred(const Type &a);

Присутствие const & в определении не обязательно, но функция не должна модифицировать передаваемые ей объекты.
Тип Type должен быть таков, что объект типа ForwardIt может быть разыменован и затем неявно преобразован в Type. ​

Требования к типам
-
BidirIt должен соответствовать требованиям BidirectionalIterator.
-
ForwardIt должен соответствовать требованиям ValueSwappable и ForwardIterator. Операция более эффективна, если ForwardIt соответствует требованиям BidirectionalIterator.
-
UnaryPredicate должен соответствовать требованиям Predicate.

[править] Возвращаемое значение

Итератор, ссылающийся на первый элемент второй части.

[править] Сложность

Ровно std::distance(first,last) применений предиката, и не более std::distance(first,last) перестановок элементов. Если ForwardIt отвечает требованиям BidirectionalIterator, то количество перестановок не превышает std::distance(first,last)/2.

[править] Возможная реализация

template<class ForwardIt, class UnaryPredicate>
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPredicate p)
{
    first = std::find_if_not(first, last, p);
    if (first == last) return first;
 
    for(ForwardIt i = std::next(first); i != last; ++i){
        if(p(*i)){
            std::iter_swap(i, first);
            ++first;
        }
    }
    return first;
}

[править] Пример

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <forward_list>
 
template <class ForwardIt>
 void quicksort(ForwardIt first, ForwardIt last)
 {
    if(first == last) return;
    auto pivot = *std::next(first, std::distance(first,last)/2);
    ForwardIt middle1 = std::partition(first, last, 
                         [pivot](const auto& em){ return em < pivot; });
    ForwardIt middle2 = std::partition(middle1, last, 
                         [pivot](const auto& em){ return !(pivot < em); });
    quicksort(first, middle1);
    quicksort(middle2, last);
 }
 
int main()
{
    std::vector<int> v = {0,1,2,3,4,5,6,7,8,9};
    std::cout << "Original vector:\n    ";
    for (int elem : v) std::cout << elem << ' ';
 
    auto it = std::partition(v.begin(), v.end(), [](int i){return i % 2 == 0;});
 
    std::cout << "\nPartitioned vector:\n    ";
    std::copy(std::begin(v), it, std::ostream_iterator<int>(std::cout, " "));
    std::cout << " * ";
    std::copy(it, std::end(v), std::ostream_iterator<int>(std::cout, " "));
}

Вывод:

Original vector:
    0 1 2 3 4 5 6 7 8 9 
Partitioned vector:
    0 8 2 6 4  *  5 3 7 1 9

[править] См. также

определяет, разделен ли диапазон данным предикатом
(шаблон функции) [править]
делит диапазон на две группы, сохраняя относительный порядок элементов
(шаблон функции) [править]