std::partial_sort_copy
Defined in header
<algorithm>
|
||
template< class InputIt, class RandomIt >
RandomIt partial_sort_copy( InputIt first, InputIt last, |
(1) | |
template< class InputIt, class RandomIt, class Compare >
RandomIt partial_sort_copy( InputIt first, InputIt last, |
(2) | |
Sorts some of the elements in the range [first, last)
in ascending order, storing the result in the range [d_first, d_last)
.
At most d_last - d_first 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 not guaranteed to be preserved. The first version uses operator< to compare the elements, the second version uses the given comparison function comp
.
Contents |
[edit] Parameters
first, last | - | the range of elements to sort |
d_first, d_last | - | random access iterators defining the destination range |
comp | - | comparison function object (i.e. an object that satisfies the requirements of Compare ) which returns true if the first argument is less than (i.e. is ordered before) 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 object must not modify the objects passed to it. |
Type requirements | ||
-
InputIt must meet the requirements of InputIterator .
|
||
-
RandomIt must meet the requirements of ValueSwappable and RandomAccessIterator .
|
||
-The type of dereferenced RandomIt must meet the requirements of MoveAssignable and MoveConstructible .
|
[edit] 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).
[edit] Complexity
O(N·log(min(D,N)), where N = std::distance(first, last), D = std::distance(d_first, d_last) applications of cmp
.
[edit] Example
The following code sorts an vector of integers and copies them into a smaller and a larger vector.
#include <algorithm> #include <vector> #include <functional> #include <iostream> int main() { std::vector<int> v0{4, 2, 5, 1, 3}; std::vector<int> v1{10, 11, 12}; std::vector<int> v2{10, 11, 12, 13, 14, 15, 16}; std::vector<int>::iterator it; it = std::partial_sort_copy(v0.begin(), v0.end(), v1.begin(), v1.end()); std::cout << "Writing to the smaller vector in ascending order gives: "; for (int a : v1) { std::cout << a << " "; } std::cout << '\n'; if(it == v1.end()) std::cout << "The return value is the end iterator\n"; it = std::partial_sort_copy(v0.begin(), v0.end(), v2.begin(), v2.end(), std::greater<int>()); std::cout << "Writing to the larger vector in descending order gives: "; for (int a : v2) { std::cout << a << " "; } std::cout << '\n' << "The return value is the iterator to " << *it << '\n'; }
Output:
Writing to the smaller vector in ascending order gives: 1 2 3 The return value is the end iterator Writing to the larger vector in descending order gives: 5 4 3 2 1 15 16 The return value is the iterator to 15
[edit] See also
sorts the first N elements of a range (function template) |
|
sorts a range into ascending order (function template) |
|
sorts a range of elements while preserving order between equal elements (function template) |
|
(parallelism TS)
|
parallelized version of std::partial_sort_copy (function template) |