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.