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
backward-compatibility 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 Home