Книга: Standard Template Library Programmer

partial_sort_copy

partial_sort_copy

Category: algorithms

Component type: function

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);

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.

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.

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.

• [first, last) is a valid range.

• [result_first, result_last) is a valid range.

• [first, last) and [result_first, result_last) do not overlap.

Approximately (last – first) * log(N) comparisons, where N is the smaller of last – first and result_last – result_first.

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

partial_sort, sort, stable_sort, binary_search, lower_bound, upper_bound, less<T>, StrictWeakOrdering, LessThan Comparable

Оглавление книги