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 );
Rearranges elements such that the range [first
; middle
) contains the sorted middle − first smallest elements in the range [first
; last
).
The order of equal elements is not guaranteed to be preserved. The order of the remaining elements in the range [middle
; last
) is unspecified.
-
(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. |
middle | Iterator defining the one-past-the-end iterator of the range to be sorted. |
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
RandomIt | ValueSwappable LegacyRandomAccessIterator |
Type of dereferenced RandomIt | MoveAssignable MoveConstructible |
Compare | Compare |
Return value
(none)
Complexity
Approximately (last - first) * log(middle - first)
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.
Possible implementation
partial_sort(1)
template<typename RandomIt>
// constexpr since C++20
void partial_sort(RandomIt first, RandomIt middle, RandomIt last)
{
typedef typename std::iterator_traits<RandomIt>::value_type VT;
std::partial_sort(first, middle, last, std::less<VT>());
}
partial_sort(2)
namespace impl {
template<typename RandomIt, typename Compare>
// constexpr
void sift_down(RandomIt first, RandomIt last, const Compare& comp)
{
// sift down element at 'first'
const auto length = static_cast<size_t>(last - first);
std::size_t current = 0;
std::size_t next = 2;
while (next < length)
{
if (comp(*(first + next), *(first + (next - 1))))
--next;
if (!comp(*(first + current), *(first + next)))
return;
std::iter_swap(first + current, first + next);
current = next;
next = 2 * current + 2;
}
--next;
if (next < length && comp(*(first + current), *(first + next)))
std::iter_swap(first + current, first + next);
}
template<typename RandomIt, typename Compare>
// constexpr
void heap_select(RandomIt first, RandomIt middle, RandomIt last, const Compare& comp)
{
std::make_heap(first, middle, comp);
for (auto i = middle; i != last; ++i)
{
if (comp(*i, *first))
{
std::iter_swap(first, i);
sift_down(first, middle, comp);
}
}
}
} // namespace impl
template<typename RandomIt, typename Compare>
// constexpr since C++20
void partial_sort(RandomIt first, RandomIt middle, RandomIt last, Compare comp)
{
impl::heap_select(first, middle, last, comp);
std::sort_heap(first, middle, comp);
}
Notes
The algorithm used is typically heap select to select the smallest elements, and heap sort to sort the selected elements in the heap in ascending order.
To select elements, a heap is used. For example, for operator<
as comparison function, max-heap is used to select middle − first
smallest elements.
Heap sort is used after selection to sort [first
; middle
) selected elements (see std::sort_heap
).
std::partial_sort
algorithms are intended to be used for small constant numbers of [first
; middle
) selected elements.
Examples
#include <algorithm>
#include <array>
#include <functional>
#include <iostream>
void print(auto const& s, int middle)
{
for (int a : s)
std::cout << a << ' ';
std::cout << '\n';
if (middle > 0)
{
while (middle-- > 0)
std::cout << "--";
std::cout << '^';
}
else if (middle < 0)
{
for (auto i = s.size() + middle; --i; std::cout << " ")
{ }
for (std::cout << '^'; middle++ < 0; std::cout << "--")
{ }
}
std::cout << '\n';
};
int main()
{
std::array<int, 10> s {5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
print(s, 0);
std::partial_sort(s.begin(), s.begin() + 3, s.end());
print(s, 3);
std::partial_sort(s.rbegin(), s.rbegin() + 4, s.rend());
print(s, -4);
std::partial_sort(s.rbegin(), s.rbegin() + 5, s.rend(), std::greater{});
print(s, -5);
}
5 7 4 2 8 6 1 9 0 3
0 1 2 7 8 6 5 9 4 3
------^
4 5 6 7 8 9 3 2 1 0
^--------
4 3 2 1 0 5 6 7 8 9
^----------
Hover to see the original license.