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".