Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / C++

std::partition — particionar um intervalo segundo um predicado

std::partition reorganiza um intervalo para que os elementos que satisfazem um predicado precedam os restantes. Devolve o iterador que marca a fronteira entre os grupos, mas não garante que a ordem dentro de cada grupo seja preservada.

Versão: C++23; repository compiler flag, production runtime not attested

Sintaxe

#include <algorithm>
std::partition(first, last, pred)

std::partition, declarada em <algorithm>, modifica o intervalo [first, last): os elementos para os quais pred devolve true ficam antes dos elementos para os quais devolve false. Não ordena os valores nem remove elementos. Esta descrição refere-se à sobrecarga sem política de execução.

O iterador devolvido boundary aponta para o primeiro elemento do segundo grupo. O intervalo [first, boundary) satisfaz o predicado e [boundary, last) não o satisfaz. Se todos os elementos corresponderem, o resultado é last; se nenhum corresponder, é first. Num intervalo vazio, estes iteradores são iguais.

São necessários, pelo menos, iteradores forward e a possibilidade de trocar os valores referenciados. O predicado não pode modificar os elementos que examina. A ordem dentro de cada grupo não é garantida; utiliza std::stable_partition se for necessário preservá-la.

Para N elementos, o algoritmo faz exatamente N chamadas ao predicado e, no máximo, N trocas; com iteradores bidirecionais, faz no máximo N/2 trocas. O exemplo apresenta as dimensões dos grupos e verifica a partição com std::is_partitioned, em vez de assumir uma ordem específica dos valores.

Exemplos

#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>

int main() {
    std::array<int, 6> values{1, 2, 3, 4, 5, 6};
    const auto is_even = [](int value) { return value % 2 == 0; };

    const auto boundary = std::partition(values.begin(), values.end(), is_even);

    std::cout << "matching: " << std::distance(values.begin(), boundary) << '\n';
    std::cout << "other: " << std::distance(boundary, values.end()) << '\n';
    std::cout << "partitioned: " << std::boolalpha
              << std::is_partitioned(values.begin(), values.end(), is_even) << '\n';
}

Resultado

matching: 3
other: 3
partitioned: true

O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.

Fontes