std::partial_sort

From Cppreference

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

template< class InputIterator, class RandomAccessIterator >

RandomAccessIterator partial_sort_copy( InputIterator first,
                                        InputIterator last,
                                        RandomAccessIterator d_first,

                                        RandomAccessIterator d_last );
(1)
template< class InputIterator, class RandomAccessIterator, class Compare >

RandomAccessIterator partial_sort_copy( InputIterator first,
                                        InputIterator last,
                                        RandomAccessIterator d_first,
                                        RandomAccessIterator d_last,

                                        Compare comp );
(2)

Sorts some of the elements in the range [first, last) in ascending order. At most ​d_first - d_last​ of the elements are moved to the range [d_first, d_first + n) and then sorted. n is the number of elements to sort (​n = min(last - first, d_last - d_first)). The order of equal elements is guaranteed to be preserved. The first version uses ​operator< to compare the elements, the second version uses the given comparison function comp.

Contents

Parameters

first, last - the range of elements to sort
d_first, d_last - random access iterators defining the destination range
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

an iterator to the element defining the upper boundary of the sorted range, i.e. ​d_first + min(last - first, d_last - d_first).

Complexity

O(N*log(min(D-N)), where ​N = std::distance(first, last), ​D = std::distance(d_first, d_last) applications of cmp.

Example

See also

partial_sort
sorts the first N elements of a range
(function template)
sort
sorts a range into ascending order
(function template)
stable_sort
sorts a range of elements while preserving order between equal elements
(function template)
Personal tools
Namespaces
Variants
Actions
Navigation
Toolbox
In other languages