CKTIS / C++
std::nth_element — seleccionar un elemento por rango
std::nth_element coloca un elemento en la posición que ocuparía tras ordenar todo el rango, pero sin ordenar el rango completo. Resulta útil para encontrar la mediana o el k-ésimo elemento más pequeño.
Versión: C++23; repository compiler flag, production runtime not attested
Sintaxis
#include <algorithm>
std::nth_element(first, nth, last);
std::nth_element(first, nth, last, comp);std::nth_element, declarado en <algorithm>, reorganiza [first, last) y devuelve void. Si nth != last, *nth corresponde a la posición nth - first del rango ordenado; las posiciones empiezan en cero. Ningún elemento de [nth, last) va antes, según la comparación, de ningún elemento de [first, nth). Ambas partes pueden quedar sin ordenar.
Se requieren iteradores de acceso aleatorio. Los elementos deben admitir intercambio, construcción por movimiento y asignación por movimiento. Los rangos [first, nth) y [nth, last) deben ser válidos. Se permite nth == last, pero en ese caso no se debe desreferenciar *nth.
La comparación predeterminada ordena los números de forma ascendente. Un comp personalizado debe definir un orden débil estricto: no uses <=. Para las sobrecargas sin política de ejecución, la complejidad es lineal en promedio con respecto a last - first; no se garantiza que sea lineal en el peor caso.
El ejemplo selecciona la posición 3, es decir, el cuarto elemento más pequeño: 6. Solo imprime el valor seleccionado, porque no se especifica la disposición completa del array.
Ejemplos
#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';
}
Resultado
6
El código mostrado y el resultado declarado se verificaron en un entorno aislado mediante el método registrado en la evidencia de verificación de esta versión exacta.