Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / C++

std::nth_element — selecionar um elemento por ordem

std::nth_element coloca um elemento na posição que ocuparia após uma ordenação completa, sem ordenar todo o intervalo. É útil para encontrar a mediana ou o k-ésimo elemento mais pequeno.

Versão: C++23; repository compiler flag, production runtime not attested

Sintaxe

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

std::nth_element, declarado em <algorithm>, reorganiza [first, last) e devolve void. Se nth != last, *nth corresponde à posição nth - first no intervalo ordenado; as posições começam em zero. Nenhum elemento em [nth, last) precede, segundo a comparação, qualquer elemento em [first, nth). Ambas as partes podem permanecer por ordenar.

São necessários iteradores de acesso aleatório. Os elementos têm de permitir troca, construção por movimento e atribuição por movimento. Os intervalos [first, nth) e [nth, last) têm de ser válidos. nth == last é permitido, mas nesse caso não se deve desreferenciar *nth.

A comparação predefinida ordena os números por ordem crescente. Um comp personalizado tem de definir uma ordem fraca estrita: não uses <=. Para as sobrecargas sem política de execução, a complexidade é linear em média relativamente a last - first; não é garantida uma complexidade linear no pior caso.

O exemplo seleciona a posição 3, ou seja, o quarto elemento mais pequeno: 6. Apresenta apenas o valor selecionado, porque a disposição completa do array não é especificada.

Exemplos

#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

O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.

Fontes