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 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 backward-compatibility 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, " "));
// 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, LessThanComparable