stlab.adobe.com Adobe Systems Incorporated

partial_sort_copy

algorithms.gif
function.gif
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

Copyright © 2006-2007 Adobe Systems Incorporated.

Use of this website signifies your agreement to the Terms of Use and Online Privacy Policy.

Search powered by Google