std::nth_element

template< class RandomIt >
void nth_element( RandomIt first, RandomIt nth, RandomIt last );

template< class ExecutionPolicy, class RandomIt >
void nth_element( ExecutionPolicy&& policy,
                  RandomIt first, RandomIt nth, RandomIt last );

template< class RandomIt, class Compare >
void nth_element( RandomIt first, RandomIt nth, RandomIt last,
                  Compare comp );

template< class ExecutionPolicy, class RandomIt, class Compare >
void nth_element( ExecutionPolicy&& policy,
                  RandomIt first, RandomIt nth, RandomIt last,
                  Compare comp );

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

• 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 im Rahmen des Algorithmus aufgerufenen Funktion eine Ausnahme auslöst und ExecutionPolicy eine der Standardrichtlinien ist, wird std::terminate aufgerufen. Für jede andere ExecutionPolicy ist das Verhalten implementierungsdefiniert.
• Wenn der Algorithmus keinen Speicher zuweisen kann, wird std::bad_alloc geworfen.

Mögliche Implementierung

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

Anmerkungen

Der verwendete Algorithmus ist typischerweise Introselect, obwohl andere Auswahlalgorithmen mit geeigneter durchschnittlicher 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';
    // The consequence of the inequality of elements before/after the Nth one:
    assert(std::accumulate(v.begin(), m, 0) < std::accumulate(m, v.end(), 0));
    printVec(v);
    
    // Note: comp function changed
    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