partial_sort_copy

partial_sort_copy

template<class InIt, class RanIt>
    RanIt partial_sort_copy(InIt first1, InIt last1,
        RanIt first2, RanIt last2);
template<class InIt, class RanIt, class Pred>
    RanIt partial_sort_copy(InIt first1, InIt last1,
        RanIt first2, RanIt last2, Pred pr);

The first template function determines K, the number of elements to copy as the smaller of last1 - first1 and last2 - first2. It then copies and reorders K of the sequence designated by iterators in the range [first1, last1) such that the K elements copied to first2 are ordered byoperator<. Moreover, for each N in the range [0, K) and for each M in the range (0, last1 - first1) corresponding to an uncopied element, the predicate !(*(first2 + M) < *(first1 + N)) is true. Thus, the smallest K elements of the entire sequence designated by iterators in the range [first1, last1) are copied and sorted in ascending order to the range [first2, first2 + K).

The function evaluates the ordering predicate X < Y``ceil((last - first) * log(K)) times, at most.

The second template function behaves the same, except that it replaces operator<(X, Y) with pr(X, Y).

Sample programs: one and one (predicate version).