// <algorithm> 
// 默认(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);

拷贝部分排序的结果。

该函数等价于:

template<class _InIt,
class _RanIt,
class _Diff,
class _Ty,
class _Pr> inline
_RanIt _Partial_sort_copy(_InIt _First1, _InIt _Last1,
    _RanIt _First2, _RanIt _Last2, _Pr _Pred, _Diff *, _Ty *)
{    // copy [_First1, _Last1) into [_First2, _Last2) using _Pred
    _RanIt _Mid2 = _First2;
    for (; _First1 != _Last1 && _Mid2 != _Last2; ++_First1, ++_Mid2)
        *_Mid2 = *_First1;    // copy min(_Last1 - _First1, _Last2 - _First2)
    _STD make_heap(_First2, _Mid2, _Pred);

    for (; _First1 != _Last1; ++_First1)
        if (_DEBUG_LT_PRED(_Pred, *_First1, *_First2))
            _Adjust_heap(_First2, _Diff(0), _Diff(_Mid2 - _First2),
                _Ty(*_First1), _Pred);    // replace top with new largest

    _STD sort_heap(_First2, _Mid2, _Pred);
    return (_Mid2);
}
  • firstlast

    分别指向被排序序列中初始及末尾位置的随机访问迭代器(Random-access Iterators)。这个范围即 [first,last) ,包括 first 到 last 间的所有元素,包括 first 指向的元素,但不包括 last 指向的元素。

    result_firstresult_last

    分别指向目标序列中初始及末尾位置的随机访问迭代器(Random-access Iterators)。这个范围即 [result_first,result_last) ,包括 result_first 到 result_last 间的所有元素,包括 result_first 指向的元素,但不包括 result_last 指向的元素。

    comp

    二元谓词(Binary)函数,以两个元素为参数,然后返回一个可转换成 bool 类型的值。

    其返回值表明按所指定的严格弱序排序(Strict weak ordering)时,第一个参数所传进来的元素是否在第二个参数所传进来的元素前面。

    该函数不能修改其参数。

    可以是函数指针(Function pointer)类型或函数对象(Function object)类型。

  • 返回一个迭代器,其指向结果序列中的某个位置,该位置位于最后一个写入到结果序列中的元素之后。

  • 更多例子可查询 std::sortstd::partial_sort

    例 1

    #include <iostream>
    #include <algorithm>
    #include <iterator>
    #include <vector>
    
    #define CLASSFOO_VECTOR(type, name, ...) \
    static const type name##_a[] = __VA_ARGS__; \
    std::vector<type> name(name##_a, name##_a + sizeof(name##_a) / sizeof(*name##_a))
    
    namespace ClassFoo{
        bool IsGreater(int m, int n) {
            return m > n;
        }
        struct _IsLess{
            bool operator()(int m, int n) {
                return m < n;
            }
        }IsLess;
        void PartialSortCopy_1() {
            // 初始化 vector 对象
            CLASSFOO_VECTOR(int, BigVector1, { 8, 23, -5, 7, 29, 0, 7, 7, -7, 1, -1 });
            // 创建一个目标容器
            std::vector<int> Target(5);
    
            // 使用 operator<
            std::partial_sort_copy(
                std::begin(BigVector1),
                std::end(BigVector1),
                std::begin(Target),
                std::end(Target)
                );
            // 输出结果
            std::copy(
                Target.begin(),
                Target.end(),
                std::ostream_iterator<int>(std::cout, " "));
            std::cout << std::endl;
    
            // 使用自定义函数
            std::partial_sort_copy(
                std::begin(BigVector1),
                std::end(BigVector1),
                std::begin(Target),
                std::end(Target),
                IsGreater
                );
            // 输出结果
            std::copy(
                Target.begin(),
                Target.end(),
                std::ostream_iterator<int>(std::cout, " "));
            std::cout << std::endl;
    
            // 使用函数对象
            std::partial_sort_copy(
                std::begin(BigVector1),
                std::end(BigVector1),
                std::begin(Target),
                std::end(Target),
                IsLess
                );
            // 输出结果
            std::copy(
                Target.begin(),
                Target.end(),
                std::ostream_iterator<int>(std::cout, " "));
            std::cout << std::endl;
        }
    }
    int main()
    {
        ClassFoo::PartialSortCopy_1();
        return 0;
    }

    -7 -5 -1 0 1
    29 23 8 7 7
    -7 -5 -1 0 1 

  • 复杂度

    O(n*log2(min(n,m)))n 为 last first.m 为 result_last - result_first

    数据争用相关

    范围 [first,last) 中的所有元素都被访问过。

    异常安全性相关

    如果元素比较(Compare)、元素赋值(Assign)、元素交换(Swap)、元素移动(Move)或操作某个迭代器抛异常,该函数才会抛异常。

    注意 无效参数将导致未定义行为(Undefined behavior)