partial_sort_copy


类别: 算法	组件类型: 函数

原型

Partial_sort_copy是一个重载名称；实际上有两个partial_sort_copy函数。

template <class InputIterator, class RandomAccessIterator>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
                  RandomAccessIterator result_first,
                  RandomAccessIterator result_last);

template <class InputIterator, class RandomAccessIterator, 
          class StrictWeakOrdering>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
                  RandomAccessIterator result_first,
                  RandomAccessIterator result_last, Compare comp);

描述

Partial_sort_copy复制最小的N个元素从范围[first, last)到范围[result_first, result_first + N)，其中N是以下两者中较小的一个last - first和result_last - result_first。范围内的元素[result_first, result_first + N)将按升序排列。

这两个版本的partial_sort_copy在定义一个元素是否小于另一个元素的方式上有所不同。第一个版本使用operator<比较对象，第二个版本使用一个函数对象comp.

第一个版本的后续条件如下。如果partial_sort_copyij和是范围内的任何两个有效迭代器使得[result_first, result_first + N)在j之前是范围内的任何两个有效迭代器，则*j < *i将为false。第二个版本的相应后续条件是comp(*j, *i)将为false.

返回值为result_first + N.

定义

在标准头文件algorithm中定义，并在非标准向后兼容头文件algo.h中定义。

类型要求

对于第一个版本

InputIterator是输入迭代器的模型。
RandomAccessIterator是随机访问迭代器的模型。
RandomAccessIterator是可修改的。
的取值类型InputIterator和RandomAccessIterator是相同的。
RandomAccessIterator的取值类型是可小于比较的。
上的排序关系RandomAccessIterator的取值类型是严格弱排序，如可小于比较的要求中所定义。

对于第二个版本

InputIterator是输入迭代器的模型。
RandomAccessIterator是随机访问迭代器的模型。
RandomAccessIterator是可修改的。
的取值类型InputIterator和RandomAccessIterator是相同的。
StrictWeakOrdering是严格弱排序的模型。
RandomAccessIterator的取值类型可转换为StrictWeakOrdering的参数类型。

先决条件

[first, last)是一个有效的范围。
[result_first, result_last)是一个有效的范围。
[first, last)和[result_first, result_last)不重叠。

复杂度

大约(last - first) * log(N)次比较，其中N是以下两者中较小的一个last - first和result_last - result_first.

示例

int A[] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};
const int N = sizeof(A) / sizeof(int);

vector<int> V(4);
partial_sort_copy(A, A + N, V.begin(), V.end());
copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
// The printed result is "1 2 3 4".

注释

另请参阅

partial_sort, sort, stable_sort, binary_search, lower_bound, upper_bound, less<T>，严格弱排序，可小于比较的