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

CKTIS / C++

std::nth_element — sélectionner un élément par rang

std::nth_element place un élément à la position qu’il occuperait après un tri complet, sans trier toute la plage. Il est utile pour trouver une médiane ou le k-ième plus petit élément.

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

Syntaxe

#include <algorithm>
std::nth_element(first, nth, last);
std::nth_element(first, nth, last, comp);

std::nth_element, déclaré dans <algorithm>, réorganise [first, last) et renvoie void. Si nth != last, *nth correspond à la position nth - first dans la plage triée ; les positions commencent à zéro. Aucun élément de [nth, last) ne précède, selon la comparaison, un élément de [first, nth). Les deux parties peuvent rester non triées.

Des itérateurs à accès aléatoire sont requis. Les éléments doivent pouvoir être échangés, construits par déplacement et affectés par déplacement. Les plages [first, nth) et [nth, last) doivent être valides. nth == last est autorisé, mais il ne faut alors pas déréférencer *nth.

La comparaison par défaut ordonne les nombres de façon croissante. Un comp personnalisé doit définir un ordre faible strict : n’utilisez pas <=. Pour les surcharges sans politique d’exécution, la complexité est linéaire en moyenne par rapport à last - first, mais une complexité linéaire n’est pas garantie dans le pire des cas.

L’exemple sélectionne la position 3, soit le quatrième plus petit élément : 6. Il affiche uniquement la valeur sélectionnée, car l’ordre complet du tableau n’est pas spécifié.

Exemples

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

int main() {
    std::array<int, 7> values{9, 1, 8, 2, 7, 3, 6};
    auto nth = values.begin() + 3;
    std::nth_element(values.begin(), nth, values.end());
    std::cout << *nth << '\n';
}

Résultat

6

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