std:: nth_element

nth_element ordnet Elemente in [ first , last ) so um, dass nach der Umordnung gilt:

• Das Element, auf das nth zeigt, wird zu dem Element geändert, das an dieser Position auftreten würde, wenn [ first , last ) sortiert wäre.
• Für jeden Iterator i in [ first , nth ) und jeden Iterator j in [ nth , last ) , ist die folgende Bedingung erfüllt:

Wenn eine der folgenden Bedingungen erfüllt ist, ist das Verhalten undefiniert:

• [ first , nth ) oder [ nth , last ) ist kein gültiger Bereich .

Parameter

Komplexität

Gegeben \(\scriptsize N\) N als last - first :

Ausnahmen

Die Überladungen mit einem Template-Parameter namens ExecutionPolicy melden Fehler wie folgt:

• Wenn die Ausführung einer als Teil des Algorithmus aufgerufenen Funktion eine Exception wirft und ExecutionPolicy einer der Standard-Policies ist, wird std::terminate aufgerufen. Für jede andere ExecutionPolicy ist das Verhalten implementierungsdefiniert.
• Wenn der Algorithmus keinen Speicher allozieren kann, wird std::bad_alloc geworfen.

Mögliche Implementierung

Siehe auch die Implementierungen in libstdc++ , libc++ , und MSVC STL .

Hinweise

Der verwendete Algorithmus ist typischerweise Introselect , obwohl auch andere Selection algorithm mit geeigneter Average-Case-Komplexität erlaubt sind.

Beispiel

#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <numeric>
#include <vector>
void printVec(const std::vector<int>& vec)
{
    std::cout << "v = {";
    for (char sep[]{0, ' ', 0}; const int i : vec)
        std::cout << sep << i, sep[0] = ',';
    std::cout << "};\n";
}
int main()
{
    std::vector<int> v{5, 10, 6, 4, 3, 2, 6, 7, 9, 3};
    printVec(v);
    auto m = v.begin() + v.size() / 2;
    std::nth_element(v.begin(), m, v.end());
    std::cout << "\nThe median is " << v[v.size() / 2] << '\n';
    // Die Konsequenz der Ungleichheit der Elemente vor/nach dem N-ten Element:
    assert(std::accumulate(v.begin(), m, 0) < std::accumulate(m, v.end(), 0));
    printVec(v);
    // Hinweis: Vergleichsfunktion wurde geändert
    std::nth_element(v.begin(), v.begin() + 1, v.end(), std::greater{});
    std::cout << "\nThe second largest element is " << v[1] << '\n';
    std::cout << "The largest element is " << v[0] << '\n';
    printVec(v);
}

v = {5, 10, 6, 4, 3, 2, 6, 7, 9, 3};
The median is 6
v = {3, 2, 3, 4, 5, 6, 10, 7, 9, 6};
The second largest element is 9
The largest element is 10
v = {10, 9, 6, 7, 6, 3, 5, 4, 3, 2};

Fehlerberichte

Die folgenden verhaltensändernden Fehlerberichte wurden rückwirkend auf zuvor veröffentlichte C++-Standards angewendet.

Siehe auch