function template
<algorithm>

std::partial_sort

預設 (1)
template <class RandomAccessIterator>  void partial_sort (RandomAccessIterator first, RandomAccessIterator middle,                     RandomAccessIterator last);
自定義 (2)
template <class RandomAccessIterator, class Compare>  void partial_sort (RandomAccessIterator first, RandomAccessIterator middle,                     RandomAccessIterator last, Compare comp);
部分排序範圍內的元素
以某種方式重排範圍 [first,last) 中的元素,使得 middle 前面的元素是整個範圍內最小的元素,並且按升序排序,而其餘元素保持無特定順序。

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

引數

first, last
隨機訪問迭代器,指向要部分排序的序列的初始和最終位置。使用的範圍是 [first,last),它包含 firstlast 之間的所有元素,包括 first 指向的元素,但不包括 last 指向的元素。
請注意,在此函式中,這些不是連續的引數,而是第一個和第三個引數。
middle
隨機訪問迭代器,指向範圍 [first,last) 中用於完全排序元素上限邊界的元素。
comp
二元函式,它接受範圍內的兩個元素作為引數,並返回一個可轉換為 bool 的值。返回值表示作為第一個引數傳遞的元素在它定義的特定嚴格弱序中是否被認為排在第二個元素之前。
該函式不得修改其任何引數。
這可以是一個函式指標或一個函式物件。

RandomAccessIterator 應指向一個已正確定義 swap 並且同時是可移動構造可移動賦值的型別。

返回值



示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// partial_sort example
#include <iostream>     // std::cout
#include <algorithm>    // std::partial_sort
#include <vector>       // std::vector

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

int main () {
  int myints[] = {9,8,7,6,5,4,3,2,1};
  std::vector<int> myvector (myints, myints+9);

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

  // using function as comp
  std::partial_sort (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: 1 2 3 4 5 9 8 7 6


複雜度

平均而言,其複雜度小於 firstlast 之間距離的對數線性:執行大約 N*log(M) 次元素比較(其中 N 是此距離,Mfirstmiddle 之間的距離)。它還執行多達相同次數的元素交換(或移動)。

資料競爭

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

異常

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

另見