std::partial_sort() algorithm
- od C++20
- od C++17
- do C++17
// (1)
template< class RandomIt >
constexpr void partial_sort( RandomIt first, RandomIt middle, RandomIt last );
// (2)
template< class RandomIt, class Compare >
constexpr void partial_sort( RandomIt first, RandomIt middle, RandomIt last, Compare comp );
// (3)
template< class ExecutionPolicy, class RandomIt >
void partial_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt middle, RandomIt last );
// (4)
template< class ExecutionPolicy, class RandomIt, class Compare >
void partial_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt middle, RandomIt last, Compare comp );
// (1)
template< class RandomIt >
void partial_sort( RandomIt first, RandomIt middle, RandomIt last );
// (2)
template< class RandomIt, class Compare >
void partial_sort( RandomIt first, RandomIt middle, RandomIt last, Compare comp );
// (3)
template< class ExecutionPolicy, class RandomIt >
void partial_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt middle, RandomIt last );
// (4)
template< class ExecutionPolicy, class RandomIt, class Compare >
void partial_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt middle, RandomIt last, Compare comp );
// (1)
template< class RandomIt >
void partial_sort( RandomIt first, RandomIt middle, RandomIt last );
// (2)
template< class RandomIt, class Compare >
void partial_sort( RandomIt first, RandomIt middle, RandomIt last,
Compare comp );
Sorts some of the elements in the range [first
; last
) in ascending order, storing the result in the range [d_first
; d_last
).
Given N
as min(last - first, d_last - d_first)
(the number of elements to sort):
At most d_last - d_first
of the elements are placed sorted to the range [d_first
; d_first + n
).
The order of equal elements is not guaranteed to be preserved.
-
(1) Elements are compared using
operator<
. -
(2) Elements are compared using the given binary comparison function
comp
. -
(3, 4) Same as (1) and (2), but executed according to policy.
Overload ResolutionThese overloads participate in overload resolution only if
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>
istrue
. (do C++20)std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>
istrue
. (od C++20)
Parameters
first last | The range of elements to sort partially. |
d_first d_last | The destination range. |
policy | The execution policy to use. See execution policy for details. |
cmp | Comparison function object (i.e. an object that satisfies the requirements of Compare). The signature of the comparison function should be equivalent to the following:
|
Type requirements
InputIt | LegacyInputIterator |
ForwardIt | LegacyForwardIterator |
RandomIt | ValueSwappable LegacyRandomAccessIterator |
Type of dereferenced RandomIt | MoveAssignable MoveConstructible |
Compare | Compare |
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)) applications of comp
.
Exceptions
The overloads with a template parameter named ExecutionPolicy
report errors as follows:
- If execution of a function invoked as part of the algorithm throws an exception and
ExecutionPolicy
is one of the standard policies,std::terminate
is called. For any otherExecutionPolicy
, the behavior is implementation-defined. - If the algorithm fails to allocate memory,
std::bad_alloc
is thrown.
Examples
#include <algorithm>
#include <functional>
#include <iostream>
#include <string_view>
#include <type_traits>
#include <vector>
void println(std::string_view rem, auto const& v)
{
std::cout << rem;
if constexpr (std::is_scalar_v<std::decay_t<decltype(v)>>)
std::cout << v;
else
for (int e : v)
std::cout << e << ' ';
std::cout << '\n';
}
int main()
{
const auto 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());
println("Writing to the smaller vector in ascending order gives: ", v1);
if (it == v1.end())
println("The return value is the end iterator", ' ');
it = std::partial_sort_copy(v0.begin(), v0.end(), v2.begin(), v2.end(),
std::greater<int>());
println("Writing to the larger vector in descending order gives: ", v2);
println("The return value is the iterator to ", *it);
}
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
Hover to see the original license.