nth_element
Partitioniert einen Bereich von Elementen und ordnungsgemäß ermittelt das n-te-Element der Sequenz im Bereich, sodass alle Elemente davor kleiner oder gleich ihn sind und alle Elemente, die es in der Sequenz folgen, größer oder gleich sie 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 behandelt, auf der Begrenzung 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 definiert durch aufeinander folgende Elemente in der Bestellung erfüllt werden Vergleichskriterium. Ein binärer Prädikat akzeptiert zwei Argumente und gibt bei Erfüllung true zurück und false, wenn es nicht erfüllt wird.
Hinweise
Der Bereich, auf den verwiesen wird, gültig sein; muss alle Zeiger müssen dereferenzierbar befinden der Sequenz ist die letzte Position der ersten von Zunahme erreichbar.
Der nth_element - Algorithmus nicht garantiert, dass die 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, schnellere und als Alternative zu partial_sort verwendet werden, wenn die Reihenfolge des unteren Bereich nicht erforderlich.
Elemente sind äquivalent, aber entsprechen nicht unbedingt, wenn nicht geringer als die andere.
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