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

CKTIS / C++

std::stable_partition — particionamento estável de um intervalo

std::stable_partition reorganiza um intervalo para que os elementos que satisfazem um predicado fiquem antes dos restantes. Preserva a ordem relativa em ambos os grupos e devolve um iterador para o limite da partição.

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

Sintaxe

#include <algorithm>

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

// Usage:
auto boundary = std::stable_partition(first, last, pred);

std::stable_partition, declarado em <algorithm>, modifica [first, last): os elementos para os quais pred devolve true ficam antes dos restantes. A ordem relativa é preservada separadamente em ambos os grupos. Isto não é uma ordenação; std::partition não garante esta estabilidade.

O iterador devolvido boundary aponta para o primeiro elemento do segundo grupo. É igual a last quando todos os elementos satisfazem o predicado e a first quando nenhum o satisfaz. Se o intervalo estiver vazio, a função devolve first; nesse caso, verifica-se first == last. São necessários iteradores bidirecionais e elementos permutáveis, construíveis por movimentação e atribuíveis por movimentação. O predicado não pode modificar os elementos que examina.

Para a sobrecarga ilustrada, sem política de execução, um intervalo com N elementos requer exatamente N aplicações do predicado. Há, no máximo, N log₂ N permutas, reduzidas a O(N) com memória adicional suficiente. Reorganizar o intervalo existente não garante, portanto, memória auxiliar constante.

O exemplo preserva a ordem dos números pares 2, 4, 6 e ímpares 5, 7, 1; a segunda linha do resultado é o tamanho do primeiro grupo. A declaração apresentada destina-se a C++23. A fonte é um projeto de norma em evolução que inclui também alterações posteriores; as suas anotações constexpr não devem ser aplicadas automaticamente a C++23.

Exemplos

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

int main() {
    std::vector<int> values{5, 2, 7, 4, 1, 6};
    const auto boundary = std::stable_partition(
        values.begin(), values.end(),
        [](int value) { return value % 2 == 0; });

    for (auto it = values.begin(); it != values.end(); ++it) {
        if (it != values.begin()) {
            std::cout << ' ';
        }
        std::cout << *it;
    }
    std::cout << '\n' << std::distance(values.begin(), boundary) << '\n';
}

Resultado

2 4 6 5 7 1
3

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