std::nth_element

預設 (1)	template <class RandomAccessIterator> void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
自定義 (2)	template <class RandomAccessIterator, class Compare> void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);

預設 (1)

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

自定義 (2)

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

Sort element in range

Rearranges the elements in the range [first,last), in such a way that the element at the nth position is the element that would be in that position in a sorted sequence.

The other elements are left without any specific order, except that none of the elements preceding nth are greater than it, and none of the elements following it are less.

元素使用第一個版本的 operator< 進行比較，第二個版本使用 comp 進行比較。

引數

first, last: Random-access iterators to the initial and final positions of the sequence to be used. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
Notice that in this function, these are not consecutive parameters, but the first and the third.
nth: Random-access iterator pointing to the location within the range [first,last) that will contain the sorted element.
Notice that the value of the element pointed by nth before the call is not relevant.

Random-access iterator pointing to the location within the range [first,last] that will contain the sorted element.
If this points to last, the function call has no effect.
Notice that the value of the element pointed by nth before the call is not relevant.
comp: Binary function that accepts two elements in the range as arguments, and returns a value convertible to bool. The value returned indicates whether the element passed as first argument is considered to go before the second in the specific strict weak ordering it defines.
該函式不得修改其任何引數。
This can either be a function pointer or a function object.

返回值

無

示例

// nth_element example
#include <iostream>     // std::cout
#include <algorithm>    // std::nth_element, std::random_shuffle
#include <vector>       // std::vector

bool myfunction (int i,int j) { return (i<j); }

int main () {
  std::vector<int> myvector;

  // set some values:
  for (int i=1; i<10; i++) myvector.push_back(i);   // 1 2 3 4 5 6 7 8 9

  std::random_shuffle (myvector.begin(), myvector.end());

  // using default comparison (operator <):
  std::nth_element (myvector.begin(), myvector.begin()+5, myvector.end());

  // using function as comp
  std::nth_element (myvector.begin(), myvector.begin()+5, myvector.end(),myfunction);

  // print out content:
  std::cout << "myvector contains:";
  for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

可能的輸出

myvector contains: 3 1 4 2 5 6 9 7 8

複雜度

On average, linear in the distance between first and last: Compares elements, and possibly swaps (or moves) them, until the elements are properly rearranged.

資料競爭

範圍[first,last)內的物件將被修改。

異常

如果任何元素比較、元素交換（或移動）或迭代器操作丟擲異常，則會丟擲異常。
請注意，無效引數會導致未定義行為。

另見

sort: 對範圍中的元素進行排序（函式模板）

partial_sort: 對範圍中的元素進行部分排序（函式模板）

partition: 將範圍劃分為兩部分（函式模板）

find_if: 在範圍中查詢元素（函式模板）