nth_element

Статья
03/27/2013

Разделяет диапазон элементов, правильно поиск 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
Итератор с произвольным доступом final адресации позиция одно за элементом в диапазоне быть разделенным.
_Comp
Определяемый пользователем объект функции предиката, который задает критерий сравнения, которые удовлетворяют последовательные элементы в этом упорядочении.Binary предикат принимает 2 аргумента и возвращает true , когда выполняется и false, если не выполняется.

Заметки

Ссылочное диапазон должен быть допустимым; все указатели должны быть dereferenceable и в последовательности последняя позиция доступен из первого инкрементацией.

Алгоритм nth_element не гарантирует, что элементы сортируются в sub- диапазонах любая другая сторона 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 пространство имен:

См. также

Ссылки

nth_element (STL Samples)

Predicate Version of nth_element

Стандартная библиотека шаблонов

Поделиться через