C++ In a Nutshell

Name

partial_sort_copy function template — Sorts and copies the first part of a range

Synopsis

template<typename InIter, typename RandIter>
  RandIter partial_sort_copy(InIter first, InIter last, RandIter result_first,
                             RandIter result_last);
template<typename InIter, typename RandIter, typename Compare> 
  RandIter partial_sort_copy(InIter first, InIter last, RandIter result_first,
                             RandIter result_last, Compare comp);

The partial_sort_copy function template copies and sorts elements from the range [first, last) into the range [result_first, result_last). The number of items copied (N) is the smaller of last - first and result_last - result_first. If the source range is smaller than the result range, the sorted elements are taken from the entire source range [first, last) and copied into the first N positions of the result range, starting at result_first. If the source range is larger, it is copied and sorted into the first N positions of the result range, leaving the elements in [result_first + N, result_last) unmodified. The return value is result_first + N.

The first form compares values using the < operator. The second form calls comp(*iter1, *iter2).

Technical Notes

Let n = min(last - first, result_last - result_first).

Postcondition: for all i in [result_first, result_first + n - 1), *(i + 1) < *i is false.

Complexity is logarithmic, taking about (last - first) × log n comparisons.

See Also

nth_element function template, partial_sort_copy function template, partition function template,