nth_element
Partitioniert einen Bereich von Elementen und ordnungsgemäß sucht das n-te-Element der Sequenz im Bereich, damit alle Elemente davor kleiner oder gleich ihn sind und alle Elemente, die Sie in der Sequenz folgen, sie größer oder gleich sind.
template<class RandomAccessIterator>
void nth_element(
RandomAccessIterator _First,
RandomAccessIterator _Nth,
RandomAccessIterator _Last
);
template<class RandomAccessIterator, class BinaryPredicate>
void nth_element(
RandomAccessIterator _First,
RandomAccessIterator _Nth,
RandomAccessIterator _Last,
BinaryPredicate _Comp
);
Parameter
_First
Ein Iterator mit wahlfreier Zugriff, der die Position des ersten Elements im Bereich behandelt partitioniert werden._Nth
Ein Iterator mit wahlfreier Zugriff, der die Position des Elements abweicht, auf der Begrenzung der Partition ordnungsgemäß sortiert werden._Last
Ein Iterator mit wahlfreier Zugriff, der die Position eine hinter dem letzten Element im Bereich behandelt partitioniert werden._Comp
Benutzerdefiniertes Prädikatfunktionsobjekt, das das durch aufeinander folgende definiert Elemente in der Reihenfolge erfüllt werden Vergleichskriterium.Ein binäres Prädikat verwendet zwei Argumente und gibt zurück, wenn true erfüllt und false, wenn nicht erfüllt wird.
Hinweise
Der Bereich, der verweist, muss gültig sein; alle Zeiger müssen dereferenzierbar sein und in der Sequenz ist die letzte Position von der ersten durch Zunahme erreichbar.
Der nth_element Algorithmus garantiert nicht, dass Elemente in den SubBereichen jede Seite des N-ten-Elements sortiert werden.Es macht daher weniger Garantien als partial_sort, der die Elemente im Bereich unterhalb eines ausgewählten Elements sortiert, und wird als schnellere Alternative zu partial_sort verwendet werden, wenn die Reihenfolge des unteren Bereichs nicht erforderlich ist.
Elemente sind äquivalent, aber nicht notwendigerweise entsprechen, wenn kein kleiner als das andere ist.
Der Durchschnitt einer Sortierungskomplexität ist in Bezug auf _Last - _First linear.
Beispiel
// alg_nth_elem.cpp
// compile with: /EHsc
#include <vector>
#include <algorithm>
#include <functional> // For greater<int>( )
#include <iostream>
// Return whether first element is greater than the second
bool UDgreater ( int elem1, int elem2 ) {
return elem1 > elem2;
}
int main() {
using namespace std;
vector <int> v1;
vector <int>::iterator Iter1;
int i;
for ( i = 0 ; i <= 5 ; i++ )
v1.push_back( 3 * i );
int ii;
for ( ii = 0 ; ii <= 5 ; ii++ )
v1.push_back( 3 * ii + 1 );
int iii;
for ( iii = 0 ; iii <= 5 ; iii++ )
v1.push_back( 3 * iii +2 );
cout << "Original vector:\n v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;
nth_element(v1.begin( ), v1.begin( ) + 3, v1.end( ) );
cout << "Position 3 partitioned vector:\n v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;
// To sort in descending order, specify binary predicate
nth_element( v1.begin( ), v1.begin( ) + 4, v1.end( ),
greater<int>( ) );
cout << "Position 4 partitioned (greater) vector:\n v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;
random_shuffle( v1.begin( ), v1.end( ) );
cout << "Shuffled vector:\n v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;
// A user-defined (UD) binary predicate can also be used
nth_element( v1.begin( ), v1.begin( ) + 5, v1.end( ), UDgreater );
cout << "Position 5 partitioned (UDgreater) vector:\n v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;
}
Beispielausgabe
Original vector:
v1 = ( 0 3 6 9 12 15 1 4 7 10 13 16 2 5 8 11 14 17 )
Position 3 partitioned vector:
v1 = ( 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 )
Position 4 partitioned (greater) vector:
v1 = ( 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 )
Shuffled vector:
v1 = ( 5 16 8 15 17 6 10 0 13 2 9 12 3 4 7 1 11 14 )
Position 5 partitioned (UDgreater) vector:
v1 = ( 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 )
Anforderungen
Header: <algorithm>
Namespace: std