CKTIS / C++
std::nth_element — selezionare un elemento per rango
std::nth_element colloca un elemento nella posizione che occuperebbe dopo un ordinamento completo, senza ordinare l’intero intervallo. È utile per trovare la mediana o il k-esimo elemento più piccolo.
Versione: C++23; repository compiler flag, production runtime not attested
Sintassi
#include <algorithm>
std::nth_element(first, nth, last);
std::nth_element(first, nth, last, comp);std::nth_element, dichiarato in <algorithm>, riordina [first, last) e restituisce void. Se nth != last, *nth corrisponde alla posizione nth - first nell’intervallo ordinato; le posizioni partono da zero. Nessun elemento in [nth, last) precede, secondo il confronto, un elemento in [first, nth). Entrambe le parti possono restare non ordinate.
Sono richiesti iteratori ad accesso casuale. Gli elementi devono supportare lo scambio, la costruzione per spostamento e l’assegnazione per spostamento. Gli intervalli [first, nth) e [nth, last) devono essere validi. nth == last è consentito, ma in tal caso non si deve dereferenziare *nth.
Il confronto predefinito ordina i numeri in modo crescente. Un comp personalizzato deve definire un ordinamento debole stretto: non usare <=. Per gli overload senza una policy di esecuzione, la complessità è lineare in media rispetto a last - first; nel caso peggiore non è garantita una complessità lineare.
L’esempio seleziona la posizione 3, cioè il quarto elemento più piccolo: 6. Stampa solo il valore selezionato, perché l’ordinamento completo dell’array non è specificato.
Esempi
#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';
}
Risultato
6
Il codice mostrato e il risultato dichiarato sono stati verificati in un ambiente isolato con il metodo registrato nella prova di verifica di questa versione esatta.