Svenska städer

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