std::nth_element

From Cppreference

Jump to: navigation, search
Defined in header <algorithm>

template< class RandomAccessIterator >

void nth_element( RandomAccessIterator first,
                  RandomAccessIterator nth,

                  RandomAccessIterator last );
(1)
template< class RandomAccessIterator, class Compare >

void nth_element( RandomAccessIterator first,
                  RandomAccessIterator nth,

                  RandomAccessIterator last, Compare comp );
(2)

Partially sorts the range [first, last) in ascending order so that all elements in the range [first, nth) are less than those in the range [nth, last). The first version uses ​operator< to compare the elements, the second version uses the given comparison function comp.

Contents

Parameters

first, last - random access iterators defining the range sort
nth - random access iterator defining the sort partition point
comp - comparison function which returns ​true if the first argument is less than the second.

The signature of the comparison function should be equivalent to the following:

bool cmp(const Type1 &a, const Type2 &b);

The signature does not need to have const &, but the function must not modify the objects passed to it.
The types ​Type1​ and ​Type2​ must be such that an object of type ​RandomAccessIterator​ can be dereferenced and then implicitly converted to both of them.

Return value

(none)

Complexity

Linear in std::distance(first, last) on average.

Example

See also

partial_sort_copy
copies and partially sorts a range of elements
(function template)
stable_sort
sorts a range of elements while preserving order between equal elements
(function template)
sort
sorts a range into ascending order
(function template)
Personal tools
Namespaces
Variants
Actions
Navigation
Toolbox
In other languages