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.