std::partition - cppreference.com

De cppreference.com

Definido no cabeçalho `<algorithm>`

`template< class BidirIt, class UnaryPredicate > BidirectionalIterator partition( BidirIt first, BidirIt last, UnaryPredicate p ); template< class ForwardIt, class UnaryPredicate > ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPredicate p );`		(até C++11) (desde C++11)

Reordena os elementos na [first, last) faixa, de tal modo que todos os elementos para os quais o predicado p retornos true precedem os elementos para os quais predicado p retornos false. Ordem relativa dos elementos não é preservada.

Original:

Reorders the elements in the range [first, last) in such a way that all elements for which the predicate p returns true precede the elements for which predicate p returns false. Relative order of the elements is not preserved.

The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

Parâmetros

first, last	-	a gama de elementos para reordenar Original: the range of elements to reorder The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions.
p	-	unary predicate which returns `true` se o elemento deve ser solicitado antes de outros elementos Original: if the element should be ordered before other elements The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. . The signature of the predicate function should be equivalent to the following: `bool pred(const Type &a);` The signature does not need to have `const &`, but the function must not modify the objects passed to it. The type `Type` must be such that an object of type `ForwardIt` can be dereferenced and then implicitly converted to `Type`.
Type requirements
-`BidirIt` must meet the requirements of `BidirectionalIterator`.
-`ForwardIt` must meet the requirements of `ValueSwappable` and `ForwardIterator`. However, the operation is more efficient if `ForwardIt` also satisfies the requirements of `BidirectionalIterator`

Valor de retorno

Iterador para o primeiro elemento do segundo grupo.

Original:

Iterator to the first element of the second group.

The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

Complexidade

Exatamente last-first aplicações do predicado e em swaps maioria last-first. Se ForwardIt cumpre os requisitos da BidirectionalIterator em swaps maioria (last-first)/2 são feitas.

Original:

Exactly last-first applications of the predicate and at most last-first swaps. If ForwardIt meets the requirements of BidirectionalIterator at most (last-first)/2 swaps are done.

The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

Possível implementação

template<class BidirIt, class UnaryPredicate>
BidirIt partition(BidirIt first, BidirIt last, UnaryPredicate p)
{
    while (1) {
        while ((first != last) && p(*first)) {
            ++first;
        }
        if (first == last--) break;
        while ((first != last) && !p(*last)) {
            --last;
        }
        if (first == last) break;
        std::swap(*first++, *last);
    }
    return first;
}

Exemplo

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>

bool is_even(int i) { return i % 2 == 0; }

int main()
{
    std::vector<int> v;
    for (int i = 0; i < 10; ++i) v.push_back(i);
    
    std::cout << "Original vector:\n    ";
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    
    // Partition the vector
    std::vector<int>::iterator p =
        std::partition(v.begin(), v.end(), std::ptr_fun(is_even));
    
    std::cout << "\nPartitioned vector:\n    ";
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\nBefore partition:\n    ";
    std::copy(v.begin(), p,       std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\nAfter partition:\n    ";
    std::copy(p,         v.end(), std::ostream_iterator<int>(std::cout, " "));
}

Potencial saída:

Original vector:
    0 1 2 3 4 5 6 7 8 9 
Partitioned vector:
    0 8 2 6 4 5 3 7 1 9 
Before partition:
    0 8 2 6 4 
After partition:
    5 3 7 1 9

Veja também


	determina se o intervalo é dividido pelo predicado dado Original: determines if the range is partitioned by the given predicate The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. (modelo de função) [edit]

	divide os elementos em dois grupos, preservando sua ordem relativa Original: divides elements into two groups while preserving their relative order The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. (modelo de função) [edit]