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

CKTIS / C++

std::partition — partitionner une plage selon un prédicat

std::partition réorganise une plage afin que les éléments satisfaisant un prédicat précèdent les autres. La fonction renvoie l’itérateur marquant la frontière entre les groupes, sans garantir que l’ordre au sein de chacun d’eux soit conservé.

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

Syntaxe

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

std::partition, déclarée dans <algorithm>, modifie la plage [first, last) : les éléments pour lesquels pred renvoie true précèdent ceux pour lesquels il renvoie false. L’algorithme ne trie pas les valeurs et ne supprime aucun élément. Cette description concerne la surcharge sans politique d’exécution.

L’itérateur renvoyé boundary pointe sur le premier élément du deuxième groupe. La plage [first, boundary) satisfait le prédicat, tandis que [boundary, last) ne le satisfait pas. Si tous les éléments correspondent, le résultat est last ; si aucun ne correspond, c’est first. Pour une plage vide, ces itérateurs sont égaux.

Il faut au minimum des itérateurs avant ainsi que la possibilité d’échanger les valeurs référencées. Le prédicat ne doit pas modifier les éléments qu’il examine. L’ordre au sein de chaque groupe n’est pas garanti ; utilisez std::stable_partition si cet ordre doit être préservé.

Pour N éléments, l’algorithme effectue exactement N appels au prédicat et au plus N échanges, ou au plus N/2 échanges avec des itérateurs bidirectionnels. L’exemple affiche la taille des groupes et vérifie la partition avec std::is_partitioned, sans supposer un ordre particulier des valeurs.

Exemples

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

Résultat

matching: 3
other: 3
partitioned: true

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