partial_sort_copy


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 function object 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 Random Access Iterator.

RandomAccessIterator is mutable.

The value types of InputIterator and RandomAccessIterator
are the same.

RandomAccessIterator's value type is LessThan Comparable.

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

InputIterator is a model of InputIterator.

RandomAccessIterator is a model of Random Access Iterator.

RandomAccessIterator is mutable.

The value types of InputIterator and RandomAccessIterator
are the same.

StrictWeakOrdering is a model of Strict Weak Ordering.

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, " "));
// The printed result is "1 2 3 4".
Notes
See also
partial_sort,
sort,
stable_sort,
binary_search,
lower_bound,
upper_bound,
less<T>,
StrictWeakOrdering,
LessThan Comparable
STL Main Page