• 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'.
See also partial_sort, sort, stable_sort, binary_search, lower_bound, upper_bound, less<T>, StrictWeakOrdering, LessThan Comparable
Category: algorithms
Component type: function
Prototype Is_sorted is an overloaded name; there are actually two is_sorted functions.
template <class ForwardIterator>
bool is_sorted(ForwardIterator first, ForwardIterator last)
template <class ForwardIterator, class StrictWeakOrdering>
bool is_sorted(ForwardIterator first, ForwardIterator last, StrictWeakOrdering comp)
Description Is_sorted returns true if the range [first, last) is sorted in ascending order, and false otherwise.
The two versions of is_sorted 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 the function object comp. The first version of is_sorted returns true if and only if, for every iterator i in the range [first, last – 1), *(i + 1) < *i is false. The second version returns true if and only if, for every iterator i in the range [first, last – 1), comp(*(i + 1), *i) is false.
Definition Defined in algo.h.
Requirements on types For the first version:
• ForwardIterator is a model of Forward Iterator.
• ForwardIterator's value type is a model of LessThan Comparable.
• The ordering on objects of ForwardIterator's value type is a strict weak ordering, as defined in the LessThan Comparable requirements.
For the second version:
• ForwardIterator is a model of Forward Iterator.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• ForwardIterator's value type is convertible to StrictWeakOrdering's argument type.
Preconditions • [first, last) is a valid range.
Complexity Linear. Zero comparisons if [first, last) is an empty range, otherwise at most (last – first) – 1 comparisons.
Example int A[] = {1, 4, 2, 8, 5, 7};
const int N = sizeof(A) / sizeof(int);
assert(!is_sorted(A, A + N));
sort(A, A + N);
assert(is_sorted(A, A + N));
See also sort, stable_sort, partial_sort, partial_sort_copy, sort_heap, binary_search, lower_bound, upper_bound, less<T>, StrictWeakOrdering, LessThan Comparable
