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)内的对象将被修改。

异常

如果任何元素比较、元素交换(或移动)或迭代器操作抛出异常,则会抛出异常。
请注意,无效参数会导致未定义行为

另见