nth_element
Разделы диапазон элементов, правильно находя nth элемент последовательности в диапазоне, чтобы все элементы перед ней будут меньше или приравнивают к нему и все элементы, которые используют ее в последовательности больше или приравнивают на него.
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
);
Параметры
_First
Произвольно-доступный итератор слишком позицию первого элемента в диапазоне разделять._Nth
Произвольно-доступный итератор слишком положение элемента быть правильно приказанным на границе раздела._Last
Произвольно-доступный итератор слишком положение за одно окончательное элементом в диапазоне разделять._Comp
Определяемый пользователем объект функции предиката, который определяет критерии сравнения, которые будут соответствовать идущие подряд элементы в заказ. Двоичный предикат принимает два аргумента и возвращает true , если он удовлетворяется, и false, если не удовлетворяется.
Заметки
Указанный диапазон должен быть допустимым; все указатели должны быть dereferenceable и внутри последовательности последнего положения доступен из первого инкрементацией.
Алгоритм nth_element не гарантирует, что элементы сортируются в группах любая часть сторона nth элемента. Таким образом, он меньше, чем следующим partial_sort, упорядочивает элементы в диапазоне под определенным выбранным элементом и может использоваться в качестве более высокая альтернативы partial_sort, если порядок низкого диапазона не требуется.
Соответствующие элементы, но не обязательно приравнивают, если ни одно меньше другой.
Среднее значение сложности сортировки линейное по отношению к _Last — _First.
Пример
// 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;
}
Пример результатов выполнения
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 )
Требования
Заголовок: <algorithm>
Пространство имен: std