Standard Template Library Programmer's Guide

template

void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);

template

void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, StrictWeakOrdering comp);

Nth_element is similar to partial_sort , in that it partially orders a range of elements: it arranges the range [first, last) such that the element pointed to by the iterator nth is the same as the element that would be in that position if the entire range [first, last) had been sorted. Additionally, none of the elements in the range [nth, last) is less than any of the elements in the range [first, nth) . [1]

The two versions of nth_element 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 nth_element is as follows. There exists no iterator i in the range [first, nth) such that *nth < *i , and there exists no iterator j in the range [nth + 1, last) such that *j < *nth .

The postcondition for the second version of nth_element is as follows. There exists no iterator i in the range [first, nth) such that comp(*nth, *i) is true , and there exists no iterator j in the range [nth + 1, last) such that comp(*j, *nth) is true .

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

For the first version, the one that takes three arguments:

• RandomAccessIterator is a model of Random Access Iterator.

• RandomAccessIterator is mutable.

• 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, the one that takes four arguments:

• RandomAccessIterator is a model of Random Access Iterator.

• RandomAccessIterator is mutable.

• StrictWeakOrdering is a model of Strict Weak Ordering.

• RandomAccessIterator 's value type is convertible to StrictWeakOrdering 's argument type.

• [first, nth) is a valid range.

• [nth, last) is a valid range. (It follows from these two conditions that [first, last) is a valid range.)

On average, linear in last – first . [2]

int A[] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};

const int N = sizeof(A) / sizeof(int);

nth_element(A, A + 6, A + N);

copy(A, A + N, ostream_iterator(cout, " "));

// The printed result is "5 2 6 1 4 3 7 8 9 10 11 12".

[1] The way in which this differs from partial_sort is that neither the range [first, nth) nor the range [nth, last) is be sorted: it is simply guaranteed that none of the elements in [nth, last) is less than any of the elements in [first, nth) . In that sense, nth_element is more similar to partition than to sort . Nth_element does less work than partial_sort , so, reasonably enough, it is faster. That's the main reason to use nth_element instead of partial_sort .

[2] Note that this is significantly less than the run-time complexity of partial_sort .

partial_sort , partition , sort , StrictWeakOrdering, LessThan Comparable

Category: algorithms

Component type: function

Lower_bound is an overloaded name; there are actually two lower_bound functions.

template

ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const LessThanComparable& value);

template

ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp);

Lower_bound is a version of binary search: it attempts to find the element value in an ordered range [first, last) [1]. Specifically, it returns the first position where value could be inserted without violating the ordering. [2] The first version of lower_bound uses operator< for comparison, and the second uses the function object comp .

The first version of lower_bound returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i) , *j < value .

The second version of lower_bound returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i) , comp(*j, value) is true .

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

For the first version:

• ForwardIterator is a model of Forward Iterator.

• LessThanComparable is a model of LessThan Comparable.

• The ordering on objects of type LessThanComparable is a strict weak ordering , as defined in the LessThan Comparable requirements.

• ForwardIterator 's value type is the same type as LessThanComparable .

For the second version:

• ForwardIterator is a model of Forward Iterator.

• StrictWeakOrdering is a model of Strict Weak Ordering.

• ForwardIterator 's value type is the same type as T .

• ForwardIterator 's value type is convertible to StrictWeakOrdering 's argument type.

For the first version:

• [first, last) is a valid range.

• [first, last) is ordered in ascending order according to operator< . That is, for every pair of iterators i and j in [first, last) such that i precedes j , *j < *i is false .

For the second version:

• [first, last) is a valid range.

• [first, last) is ordered in ascending order according to the function object comp . That is, for every pair of iterators i and j in [first, last) such that i precedes j , comp(*j, *i) is false .