Base de connaissancesCentre d’examen
FRFrançais
Choisir la langue13

CKTIS / C++

std::stable_partition — partition stable d’une plage

std::stable_partition réorganise une plage afin que les éléments qui satisfont un prédicat précèdent les autres. L’ordre relatif est conservé dans chacun des deux groupes et un itérateur vers la frontière de partition est renvoyé.

Version : C++23; repository compiler flag, production runtime not attested

Syntaxe

#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, déclaré dans <algorithm>, modifie [first, last) : les éléments pour lesquels pred renvoie true précèdent les autres. L’ordre relatif est conservé séparément dans les deux groupes. Il ne s’agit pas d’un tri ; std::partition ne garantit pas cette stabilité.

L’itérateur renvoyé boundary désigne le premier élément du second groupe. Il est égal à last si tous les éléments satisfont le prédicat, et à first si aucun ne le satisfait. Pour une plage vide, la fonction renvoie first ; dans ce cas, on a first == last. Des itérateurs bidirectionnels sont requis, ainsi que des éléments échangeables, constructibles par déplacement et assignables par déplacement. Le prédicat ne doit pas modifier les éléments qu’il examine.

Pour la surcharge illustrée, sans politique d’exécution, une plage de N éléments entraîne exactement N applications du prédicat. Il y a au plus N log₂ N échanges, et O(N) avec suffisamment de mémoire supplémentaire. Réorganiser la plage existante ne garantit donc pas une mémoire auxiliaire constante.

L’exemple conserve l’ordre des nombres pairs 2, 4, 6 et impairs 5, 7, 1 ; la deuxième ligne de sortie indique la taille du premier groupe. La déclaration affichée vise C++23. La source est un projet de norme évolutif qui comprend aussi des modifications ultérieures ; ses annotations constexpr ne doivent pas être automatiquement appliquées à C++23.

Exemples

#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';
}

Résultat

2 4 6 5 7 1
3

Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.

Sources