 

Category: algorithms   Component type: function 
Prototype
Partial_sort_copy
is an overloaded name; there are actually two partial_sort_copy
functions.
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);
Description
Partial_sort_copy
copies the smallest N
elements from the range [first, last)
to the range [result_first, result_first + N)
, where N
is the smaller of last  first
and result_last  result_first
. The elements in [result_first, result_first + N)
will be in ascending order.
The two versions of partial_sort_copy
differ in how they define whether one element is less than another. The first version compares objects using operator<
, and the second compares objects using a functors comp
.
The postcondition for the first version of partial_sort_copy
is as follows. If i
and j
are any two valid iterators in the range [result_first, result_first + N)
such that i
precedes j
, then *j < *i
will be false
. The corresponding postcondition for the second version is that comp(*j, *i)
will be false
.
The return value is result_first + N
.
Definition
Defined in the standard header algorithm, and in the nonstandard backwardcompatibility header algo.h.
Requirements on types
For the first version:

InputIterator
is a model of InputIterator.

RandomAccessIterator
is a model of RandomAccessIterator.

RandomAccessIterator
is mutable.

The value types of
InputIterator
and RandomAccessIterator
are the same.

RandomAccessIterator
's value type is LessThanComparable.

The ordering relation on
RandomAccessIterator
's value type is a strict weak ordering, as defined in the LessThanComparable requirements.
For the second version:

InputIterator
is a model of InputIterator.

RandomAccessIterator
is a model of RandomAccessIterator.

RandomAccessIterator
is mutable.

The value types of
InputIterator
and RandomAccessIterator
are the same.

StrictWeakOrdering
is a model of StrictWeakOrdering.

RandomAccessIterator
's value type is convertible to StrictWeakOrdering
's argument type.
Preconditions

[first, last)
is a valid range.

[result_first, result_last)
is a valid range.

[first, last)
and [result_first, result_last)
do not overlap.
Complexity
Approximately (last  first) * log(N)
comparisons, where N
is the smaller of last  first
and result_last  result_first
.
Example
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, " "));
Notes
See also
partial_sort
, sort
, stable_sort
, binary_search
, lower_bound
, upper_bound
, less<T>
, StrictWeakOrdering, LessThanComparable