Standard Template Library Programmer's Guide

partial_sort_copy , sort , stable_sort , binary_search , lower_bound , upper_bound , less , StrictWeakOrdering, LessThan Comparable

Category: algorithms

Component type: function

Partial_sort_copy is an overloaded name; there are actually two partial_sort_copy functions.

template

RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last);

template

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

vectorV(4);

partial_sort_copy(A, A + N, V.begin(), V.end());

copy(V.begin(), V.end(), ostream_iterator(cout, " "));

// The printed result is "1 2 3 4".

partial_sort , sort , stable_sort , binary_search , lower_bound , upper_bound , less , StrictWeakOrdering, LessThan Comparable

Category: algorithms

Component type: function

Is_sorted is an overloaded name; there are actually two is_sorted functions.

template

bool is_sorted(ForwardIterator first, ForwardIterator last)

template

bool is_sorted(ForwardIterator first, ForwardIterator last, StrictWeakOrdering comp)

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.

Defined in algo.h.

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.

• [first, last) is a valid range.

Linear. Zero comparisons if [first, last) is an empty range, otherwise at most (last – first) – 1 comparisons.

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

sort , stable_sort , partial_sort , partial_sort_copy , sort_heap , binary_search , lower_bound , upper_bound , less , StrictWeakOrdering, LessThan Comparable

Category: algorithms

Component type: function

Nth_element is an overloaded name; there are actually two nth_element functions.