C++

参考

<algorithm>

函数模板
<algorithm>

std::partial_sort_copy

默认 (1)
template <class InputIterator, class RandomAccessIterator>  RandomAccessIterator    partial_sort_copy (InputIterator first,InputIterator last,                       RandomAccessIterator result_first,                       RandomAccessIterator result_last);
自定义 (2)
template <class InputIterator, class RandomAccessIterator, class Compare>  RandomAccessIterator    partial_sort_copy (InputIterator first,InputIterator last,                       RandomAccessIterator result_first,                       RandomAccessIterator result_last, Compare comp);
复制并部分排序范围
将范围 [first,last) 中的最小元素复制到 [result_first,result_last)，并对复制的元素进行排序。复制的元素数量与 result_first 和 result_last 之间的 距离 相同（除非此数量大于 [first,last) 中的元素数量）。

范围 [first,last) 不会被修改。

元素使用第一个版本的 operator< 进行比较，第二个版本使用 comp 进行比较。

参数

first, last
输入迭代器，指向要从中复制的序列的起始和结束位置。使用的范围是 [first,last)，它包含 first 和 last 之间的所有元素，包括 first 指向的元素，但不包括 last 指向的元素。
InputIterator 应指向一个 可赋值 于 RandomAccessIterator 所指向的元素类型的类型。
result_first, result_last
随机访问迭代器，指向目标序列的起始和结束位置。使用的范围是 [result_first,result_last)。
RandomAccessIterator 应指向一个为其定义了 swap，并且同时是 可移动构造 和 可移动赋值 的类型。
comp
二进制函数，接受结果范围中的两个元素作为参数，并返回一个可转换为 bool 的值。返回的值指示传递给第一个参数的元素是否被认为在其定义的特定 严格弱序 中排在第二个元素之前。
该函数不得修改其任何参数。
这可以是指向函数的指针，也可以是函数对象。

返回值

一个指向结果序列中最后一个写入元素的下一个元素的迭代器。

示例

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_copy example
#include <iostream>     // std::cout
#include <algorithm>    // std::partial_sort_copy
#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 (5);

  // using default comparison (operator <):
  std::partial_sort_copy (myints, myints+9, myvector.begin(), myvector.end());

  // using function as comp
  std::partial_sort_copy (myints, myints+9, myvector.begin(), 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


复杂度

平均而言，比 first 和 last 之间的 距离 的对数复杂度略高：执行大约 N*log(min(N,M)) 次元素比较（其中 N 是该距离，M 是 result_first 和 result_last 之间的 距离）。它还执行高达此数量的元素交换（或移动）以及 min(N,M) 次范围之间的赋值。

数据竞争

范围[first,last)内的对象将被修改。

异常

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

另见

partial_sort
对范围中的元素进行部分排序 （函数模板）
sort
对范围中的元素进行排序 （函数模板）
copy
复制元素范围 （函数模板）
remove_copy_if
复制范围并移除值 （函数模板）